1、第第6 6章章 树与二叉树树与二叉树校长校长一一系系二二系系三三系系六六系系教教务务处处科科研研处处总总务务处处601 602教教务务科科603A B CD张张三三李李四四王王五五例例1工工厂厂(根目录) f1f2f3fnd1d2dm例例2f11f12f1kd11d12 例例31 树的基本概念树的基本概念2 树的存储结构树的存储结构3 二叉树二叉树4 二叉树的存储结构二叉树的存储结构5 二叉树的遍历二叉树的遍历6 线索二叉树线索二叉树 6.1 树的基本概念树的基本概念 树树是由是由n 0 个结点组成的有穷集合个结点组成的有穷集合( (不妨用不妨用D表示表示) )以及结点之间关系组成的集合构成的
2、结构。以及结点之间关系组成的集合构成的结构。 当当n=0 时，称该树为空树；时，称该树为空树； 在任何一棵非空的树中，有一个特殊的结点在任何一棵非空的树中，有一个特殊的结点t D，称之为该树的根结点；其余结点称之为该树的根结点；其余结点Dt被分割成被分割成m0个个不相交的子集不相交的子集D1, D2, ,Dm, ,其中每一个子集其中每一个子集Di又为一棵又为一棵树，分别称之为树，分别称之为t 的的子树子树。递归定义递归定义一一. . 树的定义树的定义JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树二二. . 树树( (逻辑上逻辑上) )的特点的特点1. . 有且仅有一个结点没有前
3、驱结点有且仅有一个结点没有前驱结点, ,该结点为树的根结点。该结点为树的根结点。2. . 除了根结点外除了根结点外, ,每个结点有且仅有一个直接前驱结点。每个结点有且仅有一个直接前驱结点。3. . 包括根结点在内，每个结点可以有多个后继结点。包括根结点在内，每个结点可以有多个后继结点。JIHGFEACXB4. 树形表示法树形表示法 借助自然界中一棵倒置的树的形状来表示数借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。据元素之间层次关系的方法。1. 结点的度：结点的度：2. 树的度：树的度：3. 叶结点：叶结点：4. 分支结点分支结点: :5. 层次的定义层次的定义: :JIHG
4、FEACXB该结点拥有的子树的数目。该结点拥有的子树的数目。树中结点度的最大值树中结点度的最大值。度为度为0 的结点的结点. .度非度非0 的结点的结点. . 根结点为第一层根结点为第一层, ,若某结点在第若某结点在第i 层层, , 则其孩子结点则其孩子结点( (若存在若存在) )为第为第i+1层层. .四四. . 基本名词术语基本名词术语第第1层层第第2层层第第3层层7. 树林树林( (森林森林): ): m 0 棵不相交的树组成的树的集合棵不相交的树组成的树的集合. .8. 树的有序性树的有序性: :6. 树的深度树的深度: :树中结点所处的最大层次数树中结点所处的最大层次数. 若树中结点
5、的子树的相对位置不能若树中结点的子树的相对位置不能 随意改变随意改变, , 则称该树为则称该树为有序树有序树，否，否 则称该树为则称该树为无序树无序树。JIHGFEACXB深度为深度为3的树的树二叉树的基本形态：二叉树的基本形态：(空空)根根根根左左子子树树根根右右子子树树根根左左子子树树右右子子树树 6.2 二叉树二叉树二二. . 两种特殊形态的二叉树两种特殊形态的二叉树 若一棵二叉树中的结点若一棵二叉树中的结点, ,或者为叶结点，或者为叶结点， 或者具有两或者具有两棵非空子树棵非空子树, ,并且叶结点都集并且叶结点都集中在二叉树的最下面一层中在二叉树的最下面一层. .这这样的二叉树为满二叉
6、树样的二叉树为满二叉树. .1. . 满二叉树满二叉树 若一棵二叉树中只有最下若一棵二叉树中只有最下面两层的结点的度可以小于面两层的结点的度可以小于2, ,并且最下面一层的结点并且最下面一层的结点( (叶结叶结点点) )都依次排列在该层从左至都依次排列在该层从左至右的位置上。这样的二叉树为右的位置上。这样的二叉树为完全二叉树完全二叉树. .2. .完全二叉树完全二叉树1. . 一棵非空二叉树的第一棵非空二叉树的第i 层最多有层最多有2i1个结点个结点( (i 1) )。三三. . 二叉树的性质二叉树的性质2. . 深度为深度为h 的非空二叉树最多有的非空二叉树最多有2h -1-1个结点个结点.
7、 .3. . 若非空二叉树有若非空二叉树有n0个叶结点个叶结点, ,有有n2个度为个度为2的结点的结点, , 则则 n0=n2+1 4. . 具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度h= log2n +1. . 二叉树的存储结构二叉树的存储结构一一. .二叉树的顺序存储结构二叉树的顺序存储结构12345678910ABCDEFGHIJBT1:151 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E F G H I J 根据完全二叉树的性质根据完全二叉树的性质 , ,对于深度为对于深度为h 的完全二叉树的完全二叉树, , 将树中所有结点的数据
8、信息按照编号的顺序依次存储到一将树中所有结点的数据信息按照编号的顺序依次存储到一维数组维数组BT1:2h-1中中, ,由于编号与数组的下标一一对应由于编号与数组的下标一一对应, 该该数组就是该完全二叉树的顺序存储结构数组就是该完全二叉树的顺序存储结构. . 1. 完全二叉树的顺序存储结构完全二叉树的顺序存储结构12345678910ABCDEFGHIJ111213BT1:151 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E F G H J IABCDEFGHIJ 2. . 一般二叉树的顺序存储结构一般二叉树的顺序存储结构 对于一般二叉树对于一般二叉树,
9、只须在二叉树中只须在二叉树中“添加添加”一些实际一些实际上上二叉树中并不存在的二叉树中并不存在的“虚结点虚结点” ( 可以认为这些结点的数可以认为这些结点的数据据信息为空信息为空), 使其在形式上成为一棵使其在形式上成为一棵“完全二叉树完全二叉树”, 然然后后按照完全二叉树的顺序存储结构的构造方法将所有结点的按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组数据信息依次存放于数组BT1: 2h -1中。中。二二. .二叉树的链式存储结构二叉树的链式存储结构( (二叉链表二叉链表) )链结点的构造为链结点的构造为lchilddatarchild 其中其中, data 为数据
10、域为数据域 lchild 与与rchild 分别为指向左、右子树的指针域分别为指向左、右子树的指针域.ABCDEFGIJABCDEFGJIT6.3.3 二叉树的遍历二叉树的遍历二二. .前序遍历前序遍历三三. .中序遍历中序遍历四四. .后序遍历后序遍历ABCDKFGIJEH前序遍历序列前序遍历序列: : A, B, D, K, J, G, C, F, I, E, H中序遍历序列中序遍历序列: : D, B, G, J, K, A, F, I, E, C, H后序遍历序列后序遍历序列: : D, G, J, K, B, E, I, F, H, C, A按层次遍历序列按层次遍历序列: : A,
11、B, C, D, K, F, H, J, I, G, E例例6.3.2 6.3.2 线索二叉树线索二叉树1.1.何谓线索二叉树？何谓线索二叉树？ 遍历结果是求得结点的一个线性序列。指向遍历结果是求得结点的一个线性序列。指向该线性序列该线性序列“前驱前驱”和和“后继后继”的指针，称的指针，称“线线索索”；包含；包含“线索线索”的存储结构，称为的存储结构，称为“线索链线索链表表”；与其相应的二叉树，称为；与其相应的二叉树，称为“线索二叉树线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为的过程，称为“线索化线索化”。2.2.线索链表中结点
12、的结构线索链表中结点的结构标志域标志域lchildLTagdataRTag rchild其中：其中：LTag =LTag =0 lchild 0 lchild 域指示结点的左孩子域指示结点的左孩子1 lchild 1 lchild 域指示结点的前驱域指示结点的前驱RTag =RTag =0 rchild 0 rchild 域指示结点的右孩子域指示结点的右孩子1 rchild 1 rchild 域指示结点的后继域指示结点的后继二叉树二叉线索存储表示二叉树二叉线索存储表示typedef enum Link, Thread PointerThr; typedef enum Link, Thread
13、PointerThr; / Link=0:/ Link=0:指针，指针，Thread=1:Thread=1:线索线索typedef struct BiThrNodetypedef struct BiThrNode TElemType data; TElemType data; Struct BiThrNode Struct BiThrNode * *lchild, lchild, * *rchild;rchild; / / 左右孩子指针左右孩子指针 PointerThr LTag, RTag; PointerThr LTag, RTag; / / 左右标志左右标志 BiThrNode, BiT
14、hrNode, * *BiThrTree;BiThrTree;3.3.线索二叉树图例线索二叉树图例 线索二叉树及其存储结构线索二叉树及其存储结构 （a a）中序线索二叉树）中序线索二叉树 （b b）中序线索链表）中序线索链表12345670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1如何在线索树中找结点的后继？如何在线索树中找结点的后继？结合中序线索树结合中序线索树 若其右标志为若其右标志为“1 1”，右链是线索，右链直接指，右链是线索，右链直接指示了结点的后继；示了结点的后继； 若其右标志为若其右标志为“0 0”，右链是指针，其后继为右，右链是指针，其后
15、继为右子树中最左下的结点。子树中最左下的结点。1234567如何在线索树中找结点的前驱？如何在线索树中找结点的前驱？结合中序线索树结合中序线索树 若其左标志为若其左标志为“1 1”，左链为线索，直接指示，左链为线索，直接指示其前驱；其前驱； 若其左标志为若其左标志为“0 0”，左子树中最右下的结点，左子树中最右下的结点为其前驱。为其前驱。1234567线索链表的中序遍历算法线索链表的中序遍历算法Status IOTraver_T( BiThrTree T,Status (Status IOTraver_T( BiThrTree T,Status (* *Visit)(TElemType e)
16、)Visit)(TElemType e) ) /T/T指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点，中序遍历指向根结点，中序遍历 /二叉线索树二叉线索树T T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数VisitVisit。 p = T-lchild; p = T-lchild; /p/p指向根结点指向根结点 while (p != T) while (p != T) /空树或遍历结束时，空树或遍历结束时，p = = Tp = = T while (p-LTag while (p-LTag=Link) p = p-lchild;
17、 Link) p = p-lchild; if (!Visit(p-data) return ERROR; if (!Visit(p-data) return ERROR; /访问其左子树为空的结点访问其左子树为空的结点 while (p-RTagwhile (p-RTag=Thread & p-rchild!=T) Thread & p-rchild!=T) p = p-rchild; Visit(p-data); p = p-rchild; Visit(p-data); /访问后继结点访问后继结点 p = p-rchild; p = p-rchild; return OK; return
18、OK; / IOTraver_T/ IOTraver_T0 1 00 2 01 3 11 4 10 5 01 6 11 7 1T0 1 16.4.2 6.4.2 森林和二叉树的转换森林和二叉树的转换1. 1. 树和二叉树的对应关系树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。间的一个对应关系。树转换为二叉树方法：树转换为二叉树方法：1 1）对每个孩子进行从左到右的排序；）对每个孩子进行从左到右的排序；2 2）在兄弟之间加一条连线；）在兄弟之间
19、加一条连线；3 3）对每个结点，除了左孩子外，去除其与其余）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；孩子之间的联系； 4 4）以根结点为轴心，将整个树顺时针转）以根结点为轴心，将整个树顺时针转4545。ABCDEGHFIa aABCDEGHFIb bABCDEGHFIc cABCDEGHFId d2. 2. 森林和二叉树的对应关系森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其和树对应的二叉树，其右子树必空右子树必空。 若把森林中第二棵树的根结点看成是第一棵若把森林中第二棵树的根结点看成是第一棵树的根结点的兄
20、弟，则同样可导出森林和二叉树树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。的对应关系。BCDEGHFIa aBCDEGHFIb bBCDEGHFIc cBCDEGHFId d已知条件：森林和二叉树的对应关系设已知条件：森林和二叉树的对应关系设 森森 林林 F = ( TF = ( T1 1, T, T2 2, , , T, Tn n ); ); T T1 1 = (root = (root，t t1111, t, t1212, , , t, t1m1m); ); 二叉树二叉树 B =( LBT, Node(root), RBT );B =( LBT, Node(root), RBT )
21、;由森林转换成二叉树的转换规则为由森林转换成二叉树的转换规则为: :若若 F = F = ，则，则 B = ;B = ;否则，由否则，由 Root( TRoot( T1 1 ) ) 对应得到对应得到 Node(root);Node(root); 由由 (t(t1111, t, t1212, , , t, t1m1m ) ) 对应得到对应得到 LBT;LBT; 由由 (T(T2 2, T, T3 3, , T, Tn n ) ) 对应得到对应得到 RBTRBT。由二叉树转换为森林的转换规则为由二叉树转换为森林的转换规则为: :若若 B = , B = , 则则 F = ;F = ;否则，由否则，
22、由 Node(root) Node(root) 对应得到对应得到 Root( TRoot( T1 1 ); ); 由由LBT LBT 对应得到对应得到 ( t( t1111, t, t1212, , ，t t1m1m);T);T1 1除根以外所除根以外所 构成的森林构成的森林 由由RBT RBT 对应得到对应得到 (T(T2 2, T, T3 3, , , T, Tn n) )；除；除T T1 1之外的森林之外的森林6.4.3 6.4.3 树和森林的遍历树和森林的遍历1. 1. 树的遍历树的遍历：有三条搜索路径：有三条搜索路径先根先根( (序序) )遍历：遍历：若树不空，则先访问根结点，若树不
23、空，则先访问根结点， 然后依次先根遍历各棵子树。然后依次先根遍历各棵子树。后根后根( (序序) )遍历：遍历：若树不空，则先依次后根遍历若树不空，则先依次后根遍历 各棵子树，然后访问根结点。各棵子树，然后访问根结点。按层次遍历：按层次遍历： 若树不空，则自上而下自左至若树不空，则自上而下自左至 右访问树中每个结点。右访问树中每个结点。例例对树进行先根遍历，获得的先根序列是：对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：对树进行后根遍历，获得的后根序列是：ABCDEGHFIA B E F C D G H IA B E F C D G H IE F B C G H I D
24、 AE F B C G H I D A2.2.森林的遍历森林的遍历先序遍历先序遍历( (对森林中的每一棵树进行先根遍历对森林中的每一棵树进行先根遍历) ) 1 1）若森林不空，访问森林中第一棵树的根结点若森林不空，访问森林中第一棵树的根结点； 2 2）先序遍历森林中第一棵树的子树森林先序遍历森林中第一棵树的子树森林； 3 3）先序遍历森林中先序遍历森林中( (除第一棵树外除第一棵树外) )其余树构成的森林其余树构成的森林。后序遍历后序遍历( (对森林中的每一棵树进行后根遍历对森林中的每一棵树进行后根遍历) ) 1 1）若森林不空，后序遍历森林中第一棵树的子树森林若森林不空，后序遍历森林中第一棵树的子树森林； 2 2）访问森林中第一棵树的根结点访问森林中第一棵树的根结点； 3 3）后序遍历森林中后序遍历森林中( (除第一棵树外除第一棵树外) )其余树构成的森林其余树构成的森林。例：例：对森林进行先序遍历，获得的先序序列是：对森林进行先序遍历，获得的先序序列是：对森林进行后序遍历，获得的后序序列是：对森林进行后序遍历，获得的后序序列是：BCDEGHFIB E F C D G H IB E F C D G H IE F B C G H I DE F B C G H I D
