华师本科生数据结构课件 第6章 二叉树和树

1、树型结构是一类重要的非线性结构。树型结构是结点之间有分支,并且具有层次关系的结构,它非常类似于自然界中的树。树结构在客观世界中是大量存在的。例如家谱、行政组织机构都可用树形象地表示。 树结构在计算机领域中也有着广泛的应用,例如在编译程序中,用树结构来表示源程序的语法结构；在数据库系统中,可用树结构来组织信息；在分析算法的行为时,可用树结构来描述其执行过程等等。,华中师范大学,课前导学 6.1 二叉树 6.2 遍历二叉树和线索二叉树 6.3 树和森林 6.4 树的应用,第六章 二叉树和树,【学习目标】,领会树和二叉树的类型定义，理解树和二叉树的结构差别。 熟记二叉树的主要特性，并掌握它们的证明

2、熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。 理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。 熟练掌握二叉树和树的各种存储结构及其建立的算法。 学会编写实现树的各种操作的算法。 了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。,【重点和难点】,重点：二叉树和树的遍历及其应用 难点：编写实现二叉树和树的各种 操作的递归算法 知识点 树的类型定义 二叉树的类型定义 二叉树的存储表示 二叉树的遍历以及其它操作的实现 线索二叉树 树和森林的存储表示 树和森林的遍历以及其它操作的实现 最优树和赫夫曼编码,【学习指南】,本章是整个课程的第三个学习重

3、点，也是整个课程中的一大难点。在本章的学习过程中主要应该学会如何根据二叉树和树的结构及其操作的递归定义编写递归算法。 本章必须完成的算法设计题为: 6.1, 6.3, 6.4, 6.5, 6.6, 6.7, 6.8, 6.9, 6.10, 6.11, 6.12, 6.14, 6.16, 6.17, 6.18, 6.20, 6.21, 6.24, 6.25, 6.26,6.1 二叉树,二、二叉树的基本性质,一、二叉树的定义和基本术语,三、二叉树的存储结构,一、二叉树的定义和基本术语,1、二叉树的定义 2、二叉树的基本术语 3、二叉树的应用举例 4、二叉树的基本操作,1、 二叉树定义,二叉树T是n

4、个结点的有限集合，其中n0,当n=0时，为空树，否则，其中有一个结点为根结点，其余结点划分为两个互不相交的子集TL、TR，并且TL、TR分别构成叫作左、右子树的二叉树。,二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,E,F,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,二叉树的注意点,二叉树每个结点的孩子都有左右之分，每个结点都有左右两个子树。,三个节点的二叉树（五棵）,每个结点最多只有两棵子树(不存在度大于2的结点)； 左子树和右子树次序不能颠倒(有序

5、树)。,2、基本术语,结点(node)表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree)结点拥有的子树数 叶子(leaf)度为0的结点 孩子(child)结点子树的根称为该结点的孩子 双亲(parents)孩子结点的上层结点叫该结点的双亲 深度树中结点的最大层次数 结点的层次从根结点算起，根为第一层，它的孩子为第二层，,即根结点(没有前驱) 即上层的那个结点(直接前驱) 即下层结点的子树的根(直接后继) 同一双亲下的同层结点（孩子之间互称兄弟） 即双亲位于同一层的结点（但并非同一双亲） 即从根到该结点所经分支的所有结点 即该结点下层子树中的任一结点,根 双亲 孩子 兄弟

6、 堂兄弟 祖先 子孙,结点A的度：3 结点B的度：2 结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D 结点B的孩子：E，F,结点I的双亲：D 结点L的双亲：E,结点B，C，D为兄弟 结点K，L为兄弟,树的度：3,结点A的层次：1 结点M的层次：4,树的深度：4,结点F，G为堂兄弟 结点A是结点F，G的祖先,3、二叉树的应用举例,国际Morse码,变色力缺陷遗传图 （隔代遗传）,InitBiTree(,二叉树的基本操作,查 找 类,插 入 类,删 除 类,二、二叉树的基本性质,1、层与结点数 2、深度与结点数 3、叶子与结点数 4、完全二叉树与深度 5、完全二叉树与结

7、点序号,1.一棵非空二叉树的第i 层最多有2i1个结点(i1)。,证明(采用归纳法) (1).当i=1时,结论显然正确。非空二叉树的第1层有且仅有一个结点,即树的根结点.,(2).假设对于第j层(1ji1)结论也正确,即第j层最多有2j-1个结点.,(3).有定义可知, 二叉树中每个结点最多只能有两个孩子结点。若第i1层的每个结点都有两棵非空子树,则第i层的结点数目达到最大. 而第i1层最多有2i2个结点已由假设证明,于是,应有22i2 = 2i1,证毕.,讨论1：第i层的结点数至多是多少？ （利用二进制性质可轻松求出）,提问：第i层上至少有 个结点？,2.深度为h 的非空二叉树最多有2h -

8、1个结点.,证明:,由性质1可知,若深度为h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。即有 20+21+22+2i-1+ +2h-1 = 2h-1,证毕.,讨论2：深度为k的二叉树，至多有多少个结点？ （利用二进制性质可轻松求出）,提问：深度为k时至少有 个结点？,3. 若非空二叉树有n0个叶结点,有n2个度为2的结点, 则 n0=n2+1,证明: 设该二叉树有n1个度为1的结点,结点总数为n,有 n=n0+n1+n2 -(1),设二叉树的分支数目为B,有 B=n-1 -(2),这些分支来自度于为1的结点与度度为2结点,即 B=n1+2n2 -(3),

9、联列关系(1),(2)与(3),可得到 n0=n2+1,证毕.,推论： n0=n2+2n3+3n4+ +(m-1)nm +1,讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？,实际意义：叶子数2度结点数1,4. 具有n个结点的完全二叉树的深度h=log2n+1.,证明:,设 完全二叉树的深度为 k,则根据第二条性质得 2k-1 n 2k,即 k-1 log2 n k,因为 k 只能是整数，因此， k =log2n + 1,证毕.,对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：,5. 若对具有n个结点的完全二叉树按照层次从上到下,每层从 左到右的顺序进行编号, 则

10、编号为i 的结点具有以下性质: (1) 当i=1, 则编号为i的结点为二叉树的根结点; 若i1, 则编号为i 的结点的双亲结点的编号为i/2. (2) 若2in, 则编号为i 的结点无左子树; 若2in, 则编号为i 的结点的左子树的根的编号为2i. (3) 若2i+1n, 则编号为i 的结点无右子树; 若2i+1n, 则编号为i 的结点的右子树的根的编号为2i+1.,两种特殊形态的二叉树,解释：完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。 这其实是顺序二叉树的含义。在图论概念中的“完全二叉树”是指n1=0的情况。,为何要研究这两种特殊形式？ 因为它们在顺序存储方式下可以复原

11、!,（特点：每层都“充满”了结点）,三、二叉树的存储结构,1、顺序存储结构 2、链式存储结构,1）完全二叉树的顺序存储结构,1、二叉树的顺序存储结构,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,A B C D E,缺点：浪费空间；插入、删除不便,1、二叉树的顺序存储结构,2）一般二叉树的顺序存储结构,1、二叉树的顺序存储结构,例如,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点 SqBiTre

12、e bt;,1、二叉树的顺序存储结构,用二叉链表即可方便表示。,二叉树结点数据类型定义： typedef struct node *tree_pointer; typedef struct Binode TElemType data; struct BiNode *lchild, *rchild; BiTNode， *BiTree;,一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,存储结点值的数据域data,指向右孩子结点的指针,指向左孩子结点的指针,2、二叉树的链式存储结构,2、二叉

13、树的链式存储结构,例：,2、二叉树的链式存储结构,二叉树的链式存储结构(二叉链表),2、二叉树的链式存储结构,空指针个数： 2*n0+1*n1+0*n2 =2n0+n1 =n0+n1+n0 =n0+n1+n2+1 =n+1,在n个结点的二叉链表中，有n+1个空指针域,6.2 二叉树的遍历,二、遍历算法,一、二叉树的遍历,四、线索二叉树,三、遍历应用举例,一. 二叉树的遍历,例如：,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,1、先序遍历,前序序列:,A,B,D,E,J,C,F,I,G,-,*,A

14、,B,C,先序遍历 - * A B C,1、前序遍历,中序序列:,D,B,J,E,A,F,I,C,G,2、中序遍历,-,*,A,B,C,中序遍历 A * B - C,2、中序遍历,后序序列:,D,J,E,B,I,F,G,C,A,3、后序遍历,-,*,A,B,C,后序遍历 A B * C -,3、后序遍历,先序遍历：,中序遍历：,后序遍历：,层次遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,例：用二叉树表示算术表达式,先序遍历 + * * / A B C D

15、E 前缀表示 中序遍历 A / B * C * D + E 中缀表示 后序遍历 A B / C * D * E + 后缀表示 层序遍历 + * E * D / C A B,例：用二叉树表示算术表达式,三、遍历算法,1、先序遍历 2、中序遍历 3、后序遍历 4、无递归中序遍历,按层次遍历,按层次遍历序列: A, B, C, D, E, F, G, J, I,void pre( BiTree T，void(*visit)( BiTree ) ) if (T) visit(T); pre( T-lchild, visit ); pre( T-rchild, visit ); ,返回,返回,返回,返回

16、,A,C,B,D,返回,先序序列：A B D C,遍历算法的执行过程-例题说明,模拟算法对如图所示二叉树的中序遍历的执行过程。,输出序列 CBEDFAHG,4、非递归算法,typedef enum Travel, Visit TaskType; / Travel = 1:遍历， / Visit = 0:访问 typedef struct BiTree ptr; / 指向根结点的指针 TaskType task; / 任务性质 ElemType;,“遍历左子树”,“遍历右子树”,“访问根结点”,4、中序遍历算法的非递归描述,在写算法之前首先需定义栈的元素类型。,void InOrder_iter

17、( BiTree BT ) / 利用栈实现中序遍历二叉树，T为指向二叉树的根结点的头指针 InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); / 布置初始任务 while(!StackEmpty(S) Pop(S,e); / 每次处理一项任务 if (e.task=Visit) visit(e.ptr); / 处理访问任务 else if ( !e.ptr ) / 处理非空树的遍历任务 p=e.ptr; e.ptr=p-rchild; Push(S,e); / 最不迫切任务进栈 e.ptr=p; e.task=Visit; Pus

18、h(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); /if /while /InOrder_iter,e.ptr=BT; e.task=Travel; if(BT) Push(S, e);,e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) P

19、ush(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Pu

20、sh(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,void In

21、Order_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,输出 B,if(e.task=Visit) v

22、isit(e.ptr);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,输出

23、B,e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild;

24、 Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,输出 B,e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEm

25、pty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,输出 B,输出 E,if(e.task=Visit) visit(e.ptr);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) P

26、ush(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,输出 D,输出 BE,if(e.task=Visit) visit(e.ptr);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=B

27、T; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,输出 A,输出 BED,if(e.task=Visit) visit(e.ptr);,void InOrder_iter( BiTree

28、 BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,输出 BEDA,e.ptr=p-rchild; Push(S,e); e.ptr=

29、p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit;

30、Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,输出 BEDA,输出 C,if(e.task=Visit) visit(e.ptr);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S

31、,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,输出 BEDAC,OVER,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e

32、); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,四、遍历算法的应用举例,2、求二叉树的深度(后序遍历),1、建立二叉树的存储结构,4、计算表达式的值,3、复制二叉树(后序遍历),1、建立二叉树的存储结构,不同的定义方法相应有不同的存储结构的建立算法,(1) 以字符串的形式“根-左子树-右子树”定义一棵二叉树,例如:,按先序遍历序列建立二叉树的二叉链表. 已知先序序列为： A B C D E G F ,Status CreateBiTree(BiTree / CreateBiTree,

33、A B C D,A,B,C,D,void CreatebiTree(BiTree / 递归建(遍历)右子树 /else /CreateBiTree,2、求二叉树的深度(后序遍历),算法基本思想:首先分析二叉树的深度和它的左、右子树深度之间的关系。,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中访问结点的操作为:求得左、右子树深度的最大值，然后加1 。,int Depth (BiTree T ) / 返回二叉树的深度 if (!T) depthval = 0; else depthLeft = Depth( T-lchild );

34、 depthRight= Depth( T-rchild ); depthval = 1+(depthLeftdepthRight?depthLeft:depthRight); return depthval; ,void Depth(BiTree T , int level, int /调用之前 level 的初值为 1, dval 的初值为 0.,void BiTreeDepth(BiTree T, int h, int /BiTreeDepth 主函数调用： d=0 BiTreeDepth(r,1,d),int BiTreeDepth(BiTree T) / 后序遍历求T所指二叉树的深度

35、 if (!T) return 0; else hL=BiTreeDepth(T-lchild); hR=BiTreeDepth(T-rchild); if (hL=hR) return hL+1; else return hR+1; /BiTreeDepth,例如，下列二叉树的复制过程如下：,newT,3、复制二叉树(后序遍历),BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = new BiTNode) exit(1); T- data = item; T- lchild = lptr

36、; T- rchild = rptr; return T; ,生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr),BiTNode *CopyTree(BiTNode *T) if (!T) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild); /复制左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild); /复制右子树 else newrptr = NULL; newT = GetTreeNode(T-data, new

37、lptr, newrptr); return newT; / CopyTree,4、计算表达式的值 (a+b*(c-d)-e/f,3.1 4.2 2.4 3.8 7.2 2.4,abcd-*+ef/- （后缀表达式）,opnd,0 1 2 3 4 5,数据结构的表示,a+b,(a+b)c d/e,a+bc,表达式的二叉树的表示:,a,b,+,a,b,c,+,a,b,c,+,(a+b)c,a,b,c,d,e,-,+,/,特点： 操作数为叶子结点 运算符为分支结点,例右图所示的二叉树表达式 (a+b*(c-d)-e/f 若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为： -+a

38、*b-cd/ef （前缀表达式） 按中序遍历,其中序序列为： a+b*c-d-e/f （中缀表达式） 按后序遍历,其后序序列为： abcd-*+ef/- （后缀表达式）,double value(BiTree T, float opnd) / 对以T为根指针的二叉树表示的算术表达式求值， / 操作数的数值存放在一维数组opnd中 if (!T) return 0; / 空树的值为0 if (T-data=0) return opndT-data; Lv = value(T-lchild,opnd); / 遍历左子树求第一操作数 Rv = value(T-rchild,opnd); / 遍历右子

39、树求第二操作数 switch (T-data) case PLUS: v = Lv + Rv; case MINUS: v = Lv - Rv; case ASTERISK: v = LV * Rv; case SLANT: v = Lv / Rv; default: ERROR(不合法的运算符); /switch return v; /value,习题讨论：,1. 求二叉树深度，或从x结点开始的子树深度。 算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。 技巧：递归时应当从叶子开始向上计数，层深者保留。否则不易确定层数。 2. 按层次输出二叉树

40、中所有结点。 算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。 技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，由此便可产生按层次输出的效果。,3 中序遍历的非递归(迭代)算法 算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。 4.判别给定二叉树是否为完全二叉树（即顺序二叉树）。 算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。 技巧:按层序遍历方式，先把所有结点（不管当前结点是否有

41、左右孩子）都入队列.若为完全二叉树,则层序遍历时得到的肯定是一个连续的不包含空指针的序列.如果序列中出现了空指针，则说明不是完全二叉树。,三、线索二叉树,1、何谓线索二叉树？ 2、线索链表的遍历算法 3、如何建立线索链表？,1）什么是线索二叉树,2）线索二叉树的构造,1、何谓线索二叉树？,线索二叉树（Threaded Binary Tree）的理解,普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。 若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。,存放前驱指针,存放后继指针,如何预存这类信息？,例如中序遍历结

42、果：B D C E A F H G，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！,可能是根、或最左（右）叶子,指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索”,与其相应的二叉树，称作 “线索二叉树”,包含 “线索” 的存储结构，称作 “线索链表”,A B C D E F G H K, D ,C , B,E ,规 定：,1）若结点有左子树，则lchild指向其左孩子； 否则，lchild指向其直接前驱(即线索)；,2）若结点有右子树，则rchild指向其右孩子； 否则，rchild指向其直接后继(即线索) 。,为了避免混淆，增加两个标志域，如下图所示：,约定:,当Tag

43、域为0时,表示正常情况;,当Tag域为1时,表示线索情况.,注：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。,线索链表：用前页结点结构所构成的二叉链表 线索：指向结点前驱和后继的指针 线索二叉树：加上线索的二叉树（图形式样） 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程,A,G,E,I,D,J,H,C,F,B,例：带了两个标志的某先序遍历结果如表所示，请画出对应二叉树。,悬空？,悬空？,解：该二叉树中序遍历结果为:H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行：,例：画出以下二叉树对应的中

44、序线索二叉树。,为避免悬空态，应增设一个头结点,typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,3）线索链表的类型描述,typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索,对应的中序线索二叉树存储结构如图所示：,注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G,中序遍历的第一个

45、结点?,在中序线索化链表中结点的后继?,左子树上处于“最左下”（没有左子树）的结点,若无右子树，则为后继线索所指结点,否则为对其右子树进行中序遍历时访问的第一个结点,2、线索二叉树的遍历,按中序线索化二叉树 遍历中序线索二叉树,在中序线索二叉树中找结点后继的方法： （1）若rt=1, 则rc域直接指向其后继 （2）若rt=0, 则结点的后继应是其右子树的左链尾（lt=1)的结点,void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根结点 while (p != T) / 空树或遍

46、历结束时，p=T while (p-LTag=Link) p = p-lchild; / 第一个结点 while (p-RTag=Thread / p进至其右子树根 / InOrderTraverse_Thr,3、线索二叉树的生成,线索化过程就是在遍历过程中修改空指针的过程： 将空的lchild改为结点的直接前驱； 将空的rchild改为结点的直接后继。,非空指针呢？仍然指向孩子结点（称为“正常情况”）,目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。,注解：为方便添加结点的前驱或后继，需要设置两个指针： p指针当前结点之指针； pre指针前驱结点之指针。,技巧：当结点p的左/右域为

47、空时，只改写它的左域(装入前驱pre), 而其右域（后继）留给下一结点来填写。 或者说，当前结点的指针p应当送到前驱结点的空右域中。,若p-lchildNULL,则p-Ltag=1;p-lchildpre; /p的前驱结点指针pre存入左空域 若pre-rchildNULL, 则pre-Rtag1;pre-rchild=p; /p存入其前驱结点pre的右空域,线索二叉树的生成算法,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,void InOrderThreading

48、(BiThrTree ,void InThreading(BiThrTree p, BiThrTree ,6.3 树和森林,一、树和森林的定义 二、树和森林的存储结构 三、树和森林的的遍历,一、树和森林的定义,1、树的定义 2、森林的定义 3、对树和森林的操作,1、树的基本概念,注1：过去许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。 注2：树的定义具有递归性，即树中还有树。,1. 有且仅有一个结点没有前驱结点,该结点为树的根结点。,2. 除了根结点外,每个结点有且仅有一个直接前驱结点。,3. 包括根结点在内，每个结点可以有多个后继结点。,根,子树,任何一棵非空树

49、是一个二元组 Tree = （root，F） 其中：root 被称为根结点， F 被称为子树森林,2、森林,是 m（m0）棵互 不相交的树的集合,A,root,F,3、树的表示法,图形表示法 嵌套集合表示法 广义表表示法 目录表示法 左孩子右兄弟表示法,1）图形表示法,华中师范大学,叶子,根,子树,2）广义表表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为由子树森林组成的表的名字写在表的左边,麻烦问题：应当开设多少个链域?,A( ),树根,B(E, F(K, L),C(G),D(H, I, J(M),例如:,3）

50、左孩子右兄弟表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ),Root(T) / 求树的根结点,查找类：,Value(T, cur_e) / 求当前结点的元素值,Parent(T, cur_e) / 求当前结点的双亲结点,LeftChild(T, cur_e) / 求当前结点的最左孩子,RightSibling(T, cur_e) / 求当前结点的右兄弟,TreeEmpty(T) / 判定树是否为空树,TreeDepth(T) / 求树的深度,TraverseTree( T, Visit() ) / 遍历,4、树的操

51、作,InitTree( int parent; / 双亲位置域 PTNode; 树结构: typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;,思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（n个结点要设立n个链表）； 再将n个表头用数组存放起来，这样就形成一个混合结构。,例如：,2、孩子链表表示法,C语言的类型描述:,孩子结点结构 typedef struct CTNode int child; struct CTNode *next; *ChildPtr; 双亲结点结构 typ

52、edef struct Elem data; ChildPtr firstchild; / 孩子链的头指针 CTBox; 树结构 typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;,思路：用二叉链表来表示树，但链表中的两个指针域含义不同。 左指针指向该结点的第一个孩子； 右指针指向该结点的下一个兄弟结点。,3、用孩子兄弟表示法来存储,指向左孩子,指向右兄弟,root,3、树的二叉链表 (孩子-兄弟）表示法,root,C语言的类型描述,结点结构 typedef struct CSNode Elem data

53、; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree,1）森林到二叉树的转换-方法,如果森林用有序表T=(T1，T2，Tm)来表示，则将森林T转换为对应的二叉树BT的形式化描述如下： 如果m=0，则BT为空；否则依次作如下操作： 将T1的根作为BT的根； 将T1的子树森林转换为BT的左子树； 将(T2，T3，Tm)转换为BT的右子树。,4、森林、树和二叉树的转换,1）森林转二叉树,兄弟相连 长兄为父 孩子靠左 头根为根,A,将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋

54、转，构成二叉树型结构,2）二叉树到森林的转换,将二叉树BT转换为森林T(T1，T2Tm)的形式化描述如下： 若BT不空，则依次执行如下操作： 将BT的根转换为T1的根； 将BT的左子树转换为T1的子树森林； 将BT的右子树转换为（T2，Tm）,2）二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树,3）将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,4）将二叉

55、树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构,树与二叉树转换,三、树和森林的遍历,1、树的遍历 2、森林的遍历 3、树的遍历举例,树和森林的遍历,先序遍历 访问根结点； 依次先序遍历根结点的每棵子树。,1、树的遍历,例如：,先序序列：,后序序列：,a b c d e,b d c e a,后序遍历 依次后序遍历根结点的每棵子树； 访问根结点。,树没有中序遍历（因子树不分左右）,按层次遍历: 若树不空，则自上而下自左至右访问树中每个结点。,

56、层次遍历时顶点的访问次序：,先根遍历时顶点的访问次序：,A B E F C D G H I J K,后根遍历时顶点的访问次序：,E F B C I J K H G D A,A B C D E F G H I J K,1）树（森林）的遍历-先序遍历,先序遍历森林T=(T1，T2Tm)的描述如下： 若T不空，则依次执行如下操作： 访问T1的根； 先序遍历T1的子树森林； 先序遍历森林（T2，T3Tm）； void preorder(Tnode *t) /先序遍历森林 if (t!=NULL) visite(t); /访问结点 preorder(t-firstson); /先序遍历t的子树森林 pr

57、eorder(t-nextbrother); /先序遍历t的兄弟森林 ,2）树（森林）的遍历-后序遍历,后序遍历森林T=(T1，T2Tm)的方法描述如下： 如果T不空，则依次执行如下操作： 后序遍历T1的子树森林； 访问T1的根； 后序遍历森林（T2，T3Tm）； void postorder(Tnode *t) if (t!=NULL) postorder(t-firstson); /后序遍历树t的子树森林 visite(t); /访问树t的根结点 postorder(t-nextbrother); /后序遍历t的后续兄弟森林 ,讨论：若采用先转换后遍历方式，结果是否一样？,d e c b a,a b c d e,b d c e a,1. 树的先序遍历二法相同； 2. 树的后序遍历相当于对应二叉树的中序遍历； 3. 树没有中序遍历，因为子树无左右之分。,结论：