树和二叉树PPT课件

1、1,数据结构 6树和二叉树,2,树的类型定义 二叉树的类型定义 二叉树的存储结构 遍历二叉树和线索二叉树 树和森林 赫夫曼树,主要内容,3,社会的组织结构 家族的族谱 计算机中的目录组织,描述层次结构，是一种一对多的逻辑关系,树型结构实例,4,1.树的类型定义,树的定义(Tree) 树是由n(n0)个结点组成的有限集合 如果n=0，称为空树 如果n0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱 除根以外的其它结点划分为m(m=0)个互不相交的有限集合T0,T1,Tm-1，每个集合又是一棵树，并且称之为根的子树,递归定义,5,A,B,C,D,E,F,G,H,I,J

2、,K,L,M,根,子树,树(逻辑上)的特点,每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继,6,A,B,C,D,E,F,G,H,I,J,K,L,M,树的基本概念,结点,分支结点,叶子结点,根结点,内部结点,结点,度不为0的结点,度为0的结点,7,树的基本概念,结点的度和树的度,结点的度即结点拥有的子树个数。 树的度是树内各结点的度的最大值,A,B,C,D,E,F,G,H,I,J,K,L,M,3,2,1,3,2,0,0,1,0,0,0,0,0,8,树的基本概念,结点的层次和树的深度(高度,结点的层次从根开始定义。根位于第1层，根的孩子位于第2层，余则类推。 树的深度即树中结点的

3、最大层次,第1层,第2层,第3层,第4层,9,树的基本概念,孩子、双亲、兄弟,结点的子树的根称为结点的孩子。 该结点称为其孩子的双亲。 同一双亲的孩子间互称兄弟,A,B,C,D,E,F,G,H,I,J,K,L,M,孩子,双亲,10,树的基本概念,祖先、子孙,结点的祖先是从根到该结点所经分支上的所有结点,以某结点为根的子树中的任一结点都称该结点的子孙,A,B,C,D,E,F,G,H,I,J,K,L,M,A,B,C,D,E,F,G,H,I,J,K,L,M,11,树的基本概念,森林：m(m=0)棵互不相交的树的集合,12,树的有序性：若树中结点的子树的相对位置不能随意改变，则称该树为有序树，否则称该

4、树为无序树,树的基本概念,有序树,无序树,13,有序树中最左边的子树的根称其第一个孩子，最右边的子树的根称其最后一个孩子,老大,老二,老三,有序树的第一个孩子和最后一个孩子,树的基本概念,14,树的常用表示法,凹入表示,嵌套集合,广义表,A(B(E,F),C,D(G(J),H,I,15,为何要重点研究每结点最多只有两个“叉” 的树？ 树太一般，子树的个数无限制，表示困难 二叉树的结构最简单，规律性最强 可以证明，所有树都能转为唯一对应的二叉树，不失一般性,2.二叉树,16,二叉树的基本定义,二叉树的定义 是n0个结点的有穷集合 该集合或者为空、或者由一个根结点和两个分别称为左子树和右子树的互不

5、相交的二叉树组成。 当集合为空时，称该二叉树为空二叉树。 逻辑结构：一对二(1:2) 基本特征: 树的一种 每个结点最多有2棵子树(即度=2,17,二叉树与树的区别,树至少应有一个结点，而二叉树可以为空； 树的孩子结点没有限制，而二叉树中的每个结点最多有2个孩子结点； 树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树,18,二叉树的五种基本形态,2.只有树根,1.空树,3.只有左子树,4.只有右子树,5.左右子树都有,19,问：具有3个结点的二叉树可能有几种不同形态,有5种,二叉树的基本形态,20,1.度为2的树是二叉树,2.

6、度为2的有序树是二叉树,3.具有三个结点的树可以有以下五种形态,21,二叉树的性质,性质1： 在二叉树的第i层最多有2i-1个结点(i=1) 证明： 当i=1时，显然成立 假设当i=k时，也成立，即第k层最多2k-1个结点 当i=k+1时，由于二叉树的每个结点最多有2个孩子，所以第k+1层最多有2*2k-1=2(k+1)-1个结点 故对于任意i(i=1)，二叉树的第i层最多有2i-1个结点,提问：第i层上至少有 个结点,1,22,二叉树的性质,性质2： 深度为k的二叉树最多有2k-1个结点(k=1) 证明： 由性质1可知：第i层最多有2i-1个结点 所以总的结点数最多为,23,二叉树的性质,性

7、质3： 对任何一棵二叉树T，若叶子结点数(即度为0的结点数)为n0，度为2的结点数为n2，则n0=n2+1 证明： 总结点数n=n0+n1+n2 设分支数为B，则n=B+1 又B=n1+2n2,结点无外乎度为0、1、2三种情况,五个手指四个叉” 除了树根，其余每个结点”上方”都有一个分支,度为2的结点“下方”有2个分支 度为1的结点“下方”有1个分支 度为0的结点“下方”有0个分支,解方程组： 得：n0=n2+1,24,树的叶子数与其它结点数的关系,设度为m的树中度为0,1,2,m的结点数分别为n0,n1,n2,nm，结点总数为n，分支数为B，则下面二式成立 n=n0+n1+n2+nm (1)

8、 n=B+1=n1+2n2+mnm+1 (2) 由(1)和(2)得叶子结点数 n0=1+n2+2n3+(m-1)nm,25,满二叉树(Full Binary Tree) 深度为k，结点数为2k-1 即结点数达到最大值,特殊形态的二叉树,完全二叉树(Complete Binary Tree) 树中每个结点的编号（从上到下，从左到右）都与一个同深度的满二叉树的结点一一对应 叶子结点只可能在层次最大的两层上出现,完全二叉树和和满二叉树相比，就是最底层最右边连续缺少一些结点,26,特殊形态的二叉树,2h-1,结论： 深度为h且具有2h-1个结点的二叉树为满二叉树,思考：深度为h的完全二叉树至少有多少个

9、结点,27,二叉树的性质,性质4： 具有n个结点的非空完全二叉树的深度为 证明： 设深度为k，则：2k-1-1 n =2k-1 由此推出：2k-1 = n 2k 两边求对数：k-1 = log2n k 所以,28,二叉树的性质,性质5： 若将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号： (1)若i=1，则结点i是树根，无双亲 若i1，则其双亲是结点 i/2 (2)若2in，则结点i无左孩子(即i为叶结点)，否则其左孩子为2i (3)若2i+1n，则结点i无右孩子，否则其右孩子为2i+1 由(2)(3)可以推导出(1,理解： 结点i如果有左孩子的话，其编号应该为2i 如果2

10、in，则左孩子不存在,29,二叉树的性质,性质6： 具有n个结点的非空二叉树共有n-1个分支。 证明： 除了根结点以外，每个结点有且仅有一个双亲结点，即每个结点与其双亲结点之间仅有一个分支存在，因此，具有n个结点的非空二叉树的分支总数为n-1,30,1.n(n0)个结点的树的高度最低是多少？最高是多少？ 2.n(n0)个结点的二叉树的高度最低是多少？最高是多少,推论 n个结点的树：高最多为n，最低为2。 n个结点的二叉树： 高最多为n(单支树)，最低为log2n+1(完全二叉树,自测题,31,自测题,3.有关二叉树下列说法正确的是( ) A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二

11、叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2,4.已知一棵完全二叉树的第6层(设根是第1层)有8个叶结点，则该完全二叉树的结点个数最多是( ) A. 39 B. 52 C. 111 D. 119,32,完全二叉树性质的推论,n个结点的完全二叉树中： 度为1的结点数为(n+1)%2 度为0的结点数为(n+1)/2 度为2的结点数为(n+1)/2-1 编号最大的分支结点是n/2 编号最小的叶子结点是n/2+1 具有n0个叶子结点的完全二叉树中共有2n0个结点或2n0-1个结点,33,一棵完全二叉树有1000个结点，则它必 有 个叶子结点； 有 个度为2的结点； 有 个结点只有非

12、空左子树； 有 个结点只有非空右子树,1000+1)/2 =500,叶子总数-1=499,1,0,因为最后一个结点坐标是偶数，所以必为左子树。有1个结点只有非空左子树，有0个结点只有非空右子树,自测题,34,自测题,5.一棵124个叶结点的完全二叉树，最多有( )个结点。 A.247 B.248 C.249 D.250 E.251,6.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。 A.311 B.312 C.313 D.314 E.其他,35,自测题,7.一个具有1025个结点的二叉树的高h为( ) 。 A.11 B.10 C.11至1025之间 D.10至1024之间,8

13、.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点,12,36,二叉树,本节小结 二叉树的概念和类型定义 注意和树的类型定义的对比 二叉树的性质 要求自己能推导、应用、推广,37,3.二叉树的存储结构,二叉树的顺序存储结构,用一维数组来表示 #define MAX_TREE_SIZE 100 typedef datatype SqBiTreeMAX_TREE_SIZE; SqBiTree Bt; 按照满二叉树的顺序存放,38,完全二叉树的顺序存储结构,根据完全二叉树的性质5，对于深度为h的完全二叉树，将树中所有结点的数据信息按编号顺序一次存储到数组

14、BT12h-1中，由于编号与数组下标一一对应，该数组就是该完全二叉树的顺序存储结构,下标,BT3的双亲为3/2=1，即在BT1中； 其左孩子在BT2i=BT6中； 其右孩子在BT2i+1=BT7中,39,一般二叉树的顺序存储结构,BT5的双亲为5/2=2，即在BT2中，与实际矛盾！ 其左孩子在BT2i=BT10中，实际应在BT9中,对于一般二叉树，需要在二叉树中“增添”一些实际上并不存在的“虚结点”(可以认为这些结点的数据信息为空)，使其在形式上成为一棵“完全二叉树”； 然后按照完全二叉树的顺序存储结构的构造方法将所有结点的信息依次存放到数组BT1.2h-1中,40,BT6的双亲为6/2=3，

15、即在BT3中！ 其左孩子在BT2i=BT12中； 其右孩子在BT2i+1=BT13中，而BT130，表示无右孩子,41,一般二叉树的顺序存储结构,极端情形：单支树 深度为k的二叉树，最少只有k个结点 却需要2k-1个存储单元,10,增加1倍之多,42,二叉树的链式存储结构 二叉链表 data为数据域； lchild与rchild分别为指向左、右子树的指针域,3.二叉树的存储结构,43,二叉链表示例,说明： 一个二叉链表由根指针T唯一确定。 若二叉树为空，则T=NULL；若结点的某个孩子不存在，则相应的指针为空。 具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩

16、子，其余的n+1个指针域为空,44,二叉树的链式存储结构 三叉链表 比二叉链表的链结点多增加了一个指向双亲结点的指针域parent,3.二叉树的存储结构,45,三叉链表示例,46,二叉链表结点结构的定义 typedef int datatype; typedef struct node datatype data; struct node *lchild,*rchild; bitree,二叉树的链表表示,47,二叉树的存储结构,本节小结 各种存储结构 注意各自的优缺点 比如顺序存储空间浪费大 二叉链表不能直接找到父结点,48,练习1,已知非空二叉树采用广义表形式作为输入，请写一算法，建立该二叉

17、树的二叉链表存储结构,49,关于广义表形式表示二叉树的说明,1.约定表中的一个字母代表一个结点的数据信息。 2.每个根结点作为由子树构成的表的名字放在表的前面。 3.每个结点的左子树和右子树之间用逗号分开，若只有右子树而无左子树，则逗号不能省略。 4.在整个广义表的末尾加一个特殊符号（如）作为结束标志,50,二叉树的广义表表示方法,二叉树,51,大写字母,二叉树,二叉树的广义表表示方法,52,大写字母,二叉树,二叉树,二叉树,defi=“A(B,C(D,E,二叉树的广义表表示方法,53,1.若取到的元素为字母，则如下建立一个新结点， 若该结点为根结点，则将该结点的地址送T。 若该结点不是二叉树

18、的根结点，则将该结点作为左孩子（若标志为1）或者右孩子（若标志为2）链接到其双亲结点上（双亲结点的地址在栈顶）。 2.若取到的元素为左括号（，则表明一个子表开始，将标志置为1，同时将前面那个结点的地址进栈。 3.若取到的元素为右括号），则表明一个子表结束，作退栈操作。 4.若取到的元素为逗号，则表明以左孩子为根的子树处理完毕，接着应该处理以右孩子为根的子树，将标志置为2。 如此处理广义表中每一个元素，直到取到结束符号为止,54,练习2,已知具有n个结点的非空完全二叉树采用顺序存储结构，结点的数据信息依次存放于数组BT1.n中。请写出由此产生该二叉树二叉链表结构的算法,55,建立根结点,以BT的

19、第2个元素开始取一个元素,建立一个新结点,保存新结点的地址,找到新结点的双亲结点的地址,确定新结点是双亲结点的左（或右）孩子,将新结点插入二叉链表中,保存在一个数组中,利用二叉树的性质5,56,设置一个一维数组PTR存放结点所在链结点的地址 建立根结点，并将根结点的地址保存在数组PTR中 从数组BT的第2个元素开始依次取结点的信息BTi，每取得一个结点做如下操作,1.建立一个新结点，并将结点地址保存在PTRi中； 2.建立新结点的双亲结点的位置(地址,3.确定新结点是其双亲结点的左孩子或右孩子,4.将新结点作为双亲结点的左孩子或右孩子插入二叉链表中,若i%2=0，则新结点是其双亲结点的左孩子；

20、 当i%2 !=0，则新结点是其双亲结点的右孩子,57,j=i/2,当i%2=0时，i是j的左孩子 当i%2 !=0时，i是j的右孩子,58,define MaxNode 100 /*MaxNode=n*/ bitree *BUILDBTREE(datatype BT,int n) bitree *T,*PTRMaxNode; int i,j; PTR1=(bitree *)malloc(sizeof(bitree); PTR1-data=BT1; PTR1-lchild=NULL; PTR1-rchild=NULL; T=PTR1; /*建立根结点*,59,for(i=2;idata=BTi

21、; PTRi-lchild=NULL; PTRi-rchild=NULL,j=i/2; /*计算双亲结点的位置j*/ if(i%2=0) PTRj-lchild=PTRi; /*BTi是双亲的左孩子*/ else PTRj-rchild=PTRi; /*BTi是双亲的右孩子*/ return T;,60,已知非空二叉树采用顺序存储结构，结点的数据信息依次存放于数组BT1.n中。请写出由此产生该二叉树二叉链表结构的算法,练习3,61,一、二叉树的遍历,按照一定的顺序(原则)对二叉树中每一个结点都访问一次(仅访问一次)，得到一个由该二叉树的所有结点组成的序列，这一过程称为二叉树的遍历。 访问的含义

22、包括查询、打印、计算、修改等对结点的操作,4.二叉树的遍历,62,常用的遍历方法： 1. 前 (先)序遍历 DLR 2. 中 序遍历 LDR 3. 后 序遍历 LRD 4. 按 层次遍历,遍历规则,注：指访问的结点D是先于子树出现还是后于子树出现,以根结点为参照系,63,原则 若被遍历的二叉树为空，则空操作 否则 1.访问根结点 2.以前序遍历原则遍历根结点的左子树 3.以前序遍历原则遍历根结点的右子树,二、前序遍历(Preorder Traversal,递归,64,A,遍历序列,B,C,F,D,E,G,H,1)访问根结点； (2)前序遍历左子树； (3)前序遍历右子树,二、前序遍历(Preo

23、rder Traversal,65,三、中序遍历(Inorder Traversal,原则 若被遍历的二叉树为空，则空操作 否则 1.以中序遍历原则遍历根结点的左子树 2.访问根结点 3.以中序遍历原则遍历根结点的右子树,递归,66,遍历序列,1)中序遍历左子树； (2)访问根结点； (3)中序遍历右子树,A,B,C,F,D,E,G,H,三、中序遍历(Inorder Traversal,67,四、后序遍历(Postorder Traversal,原则 若被遍历的二叉树为空，则空操作 否则 1.以后序遍历原则遍历根结点的左子树 2.以后序遍历原则遍历根结点的右子树 3.访问根结点,递归,68,遍

24、历序列,1)后序遍历左子树； (2)后序遍历右子树； (3)访问根结点,A,B,C,F,D,E,G,H,四、后序遍历(Postorder Traversal,69,二叉树的其它操作：广度优先遍历,A,遍历序列,B,C,F,D,E,G,H,广度优先遍历(也叫层次遍历,1)按结点所在层次，由低层向高层依次遍历； (2)同层按自左向右次序遍历,70,二叉树的其它操作：广度优先遍历,二叉树的层序遍历算法： (1)初始化设置一个队列； (2)把根结点指针入队列； (3)当队列非空时，循环执行步骤(a)到步骤(c): (a)出队列取得一个结点指针，访问该结点；(b)若该结点的左子树非空，则将该结点的左子树

25、指针入队列；(c)若该结点的右子树非空，则将该结点的右子树指针入队列； (4)结束,71,1)从根开始：若二叉树非空，则根入队； (2)队头出队，并访问,遍历序列,思路,A,B,C,3)若当前结点有左子树，则其左子树的根入队； (4)若当前结点有右子树，则其右子树的根入队； (5)重复(2)(4,D,E,F,G,H,直至队空,72,算法： Status LevelOrderTraverse (biTree *T) InitQueue(Q); AddQueue(Q,T); /树根入队 while(!QueueEmpty(Q) /只要队列非空 DeleteQueue(Q,p); /出队一个结点 i

26、f(!Visit(p-data) return ERROR; /访问之 if(p-lchild) AddQueue(Q,p-lchild); /左孩子入队 if(p-rchild) AddQueue(Q,p-rchild); /右孩子入队 return OK;,73,二叉树的遍历:算法,回忆一下递归算法的适用情况 (1)问题本身直接用递归定义的 (2)问题的规律有递归的特点 二叉树及其遍历是用递归定义的 用递归算法肯定可以解决 如果不用递归呢,74,二叉树的前序遍历递归算法,若二叉树为空，则算法结束；否则： (1)访问根结点； (2)前序遍历根结点的左子树； (3)前序遍历根结点的右子树,vo

27、id PreOrderTraverse(bitree *T) if(T) 二叉树非空 printf(t%cn,T-data); 访问根结点 PreOrderTraverse(T-lchild); 前序遍历左子树 PreOrderTraverse(T-rchild); 前序遍历右子树,75,二叉树的中序遍历递归算法,若二叉树为空，则算法结束；否则： (1)中序遍历根结点的左子树； (2)访问根结点； (3)中序遍历根结点的右子树,void InOrderTraverse(bitree *T) if(T) InOrderTraverse(T-lchild); printf(t%cn,T-data)

28、; InOrderTraverse(T-rchild);,76,二叉树的后序遍历递归算法,若二叉树为空，则算法结束；否则： (1)后序遍历根结点的左子树； (2)后序遍历根结点的右子树； (3)访问根结点,void PostOrderTraverse(bitree *T) if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(t%cn,T-data);,77,1.递归算法的优点 (1)问题的数学模型或算法设计方法本身就是递归的，采用递归算法来描述它们非常自然； (2)描述直观，结构清晰、简洁；正确性证明比非

29、递归算法容易,2.递归算法的不足 (1)算法的执行时间与空间开销往往比非递归算法要大，当问题规模较大时尤为明显； (2)对算法进行优化比较困难； (3)分析跟踪算法的执行过程比较麻烦； (4)描述算法的语言不具有递归功能时，算法无法描述,谨慎使用递归，因为它的简洁可能会掩盖它的低效率,五、递归问题的非递归算法的设计,78,五、递归问题的非递归算法的设计,回顾遍历的过程(以中序为例) 1 先走到最左 2 往回访问父结点 3 往右访问右子树 3.1 走到最左 3.2 回访父结点 3.3 访问右子树,A,B,C,D,E,F,G,79,二叉树的遍历：非递归算法,A,B,C,D,E,F,G,当向左/右走

30、到底时怎么办？ 需要返回到祖先 哪个祖先？ 路过的却未访问的最近的祖先 这就需要一种机制能记录访问的“历史信息”:路过却未访问的结点，以便能够回溯回去 这就需要一个栈存放来这些祖先,80,E,H,二叉树的遍历：非递归算法,1)非空树从根开始； (2)若当前结点存在， 则暂存，p下到左子树； 否则回退 访问当前结点 p下到右子树,中序遍历非递归思路,A,B,D,遍历序列,D,B,G,G,E,H,A,C,C,F,F,3)重复(2)直到p空且栈空,81,Stack0.M-1-保存遍历过程中结点的地址； top-栈顶指针，初始为-1； p-遍历过程中使用的指针变量，初始时指向根结点,用自然语言表达的算

31、法,1.若p指向的结点非空，则将p指的结点的地址进栈，然后，将p指向左子树的根； 2.若p指向的结点为空，则从栈中退出栈顶元素送p，访问该结点，然后，将p指向右子树的根； 重复上述过程，直到p为空，并且栈也为空,82,二叉树的中序遍历：非递归算法,int InOrderT (bitree *T) bitree *p=T; SqStack *S; InitStack(S); /建栈 while (p|!StackEmpty(s) /还有未访问的 if (p) /一直向左走到底，路过的所有的根入栈 Push(S, p); p = p-lchild; /遍历左子树 else /p为NULL，说明走到

32、了底 Pop(S, p); Visit(p-data); /弹出一个还没访问的结点，访问之 p = p-rchild; /遍历右子树 return OK;,p走到了底，再依次弹出刚才路过却没有访问的结点，访问之，然后p向右走,83,时间复杂度 n个结点，每一个都要访问一次 显然时间复杂度为O(n)(这里n为结点数) 空间复杂度 不论是递归还是非递归算法都要用到栈 栈的最大深度 = 树的深度 所有空间复杂度为O(n)(这里n为树的深度,二叉树的遍历：算法效率,84,二叉树的初始化,算法的基本思想:创建二叉树的头结点。 程序实现： void Initiate(bitree *root) *root

33、 = (bitree *)malloc(sizeof(bitree); (*root)-lchild=NULL; (*root)-rchild=NULL;,root是指向根指针的指针,85,按前序构造二叉链表,例1：按下列次序输入字符 (表示空格): ABCDEGF,例2：HGFM,86,按前序构造二叉链表的算法,void CreateBT(bitree *P) char ch; ch=getchar(); /*从键盘上输入一个字符*/ if (ch= ) *P=NULL; else *P=(bitree *)malloc(sizeof(bitree); (*P)-data=ch; Creat

34、eBT(,P是指向根指针的指针，*P的值发生变化后可以返回,87,前序遍历序列： 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,B,C,D,K,F,H,J,I,G,E,88,89,前序序列： 中序序列： 后序序列,ABIFCGDEH FIBCGADEH FIGCBHEDA,90,利用前序序列和中序序列恢复二叉树,利用中序序列和后序序列恢复二叉树,利用前序序列和后序序列恢复二叉树,前序序列：A,B,D,C 后序序列：D,B,C,A,91,六、由遍历序列恢复二

35、叉树,前序序列： A,B,D,E,J,C,F,I,G 中序序列： D,B,J,E,A,F,I,C,G,92,已知前序序列和中序序列，恢复二叉树 在前序序列中寻找根； 到中序序列中分左右,规律,已知中序序列和后序序列，恢复二叉树 在后序序列中寻找根； 到中序序列中分左右,93,例:已知结点的前序序列和中序序列分别为： 前序序列：ABDEGHCF 中序序列：DBGEHACF 求此二叉树,六、由遍历序列恢复二叉树,94,由已知的前序序列和中序序列构造二叉树的方法,A,六、由遍历序列恢复二叉树,95,A,由已知的前序序列和中序序列构造二叉树的方法,六、由遍历序列恢复二叉树,96,A,B,D,前序,E,

36、G,H,C,F,D,B,G,中序,E,H,A,C,F,B,A,D,由已知的前序序列和中序序列构造二叉树的方法,六、由遍历序列恢复二叉树,97,A,B,D,前序,E,G,H,C,F,D,B,G,中序,E,H,A,C,F,B,A,D,E,G,H,由已知的前序序列和中序序列构造二叉树的方法,六、由遍历序列恢复二叉树,98,1)由前序序列得根； (2)在中序序列中查找根，并确定左子树中结点个数； (3)分别确定左、右子树的前序序列和中序序列； (4)分别构造左、右子树,六、由遍历序列恢复二叉树,由已知的前序序列和中序序列构造二叉树的方法,99,已知二叉树的 1.前序序列ABDFCEHG 中序序列DBF

37、AHECG 请构造该二叉树,2.后序序列DMFBHELGCA 中序序列DBMFAHECGL 请构造该二叉树,自测题,100,一棵二叉树的前序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。 前序序列为：_ _ C D E _ G H I _ K 中序序列为：C B _ _ F A _ J K I G 后序序列为： _ E F D B _ J I H _ A,自测题,101,试找出满足下列条件的二叉树 1)前序序列与后序序列相同 2)中序序列与后序序列相同 3)前序序列与中序序列相同 4)前序、中序、后序序列均相同 5)中序序列与层次遍历序列相同,自测题,102,一棵二叉树的前序遍历序

38、列为ABCDEFG，它的中序遍历序列可能是( )。 A. CABDEFG B. ABCDEFG C. DACEFBG D. ADCFEGB,自测题,103,一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足( )。 A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶子结点 D. 其中度为2的结点最多为一个 E. 空或只有一个结点 F. 高度等于其结点数,自测题,104,注意： 一个二叉树的遍历序列不能决定一棵二叉树，但前序（或后序）和中序遍历序列的组合可以唯一确定一棵二叉树。而前序和后序遍历则不能,口诀： DLR前序遍历，即先根再左再右 LD

39、R中序遍历，即先左再根再右 LRD后序遍历，即先左再右再根,105,例6.1 给二叉树中某个指定结点插入一个左结点,算法思想: 若当前结点(假设为curr)非空，在curr的左子树插入元素值为x的新结点，原curr所指结点的左子树成为新插入结点的左子树。若插入成功返回新插入结点的指针，否则返回空指针,二叉树操作举例,106,bitree *InsertLeftNode(bitree *curr,datatype x) bitree *s, *t; if(curr=NULL) return NULL; t=curr-lchild; s=(bitree *)malloc(sizeof(bitree

40、); s-data=x; s-lchild=t; s-rchild=NULL; curr-lchild=s; return curr-lchild;,107,算法思想: 若curr非空，删除curr所指结点的左子树。若删除成功，返回删除结点的双亲结点指针，否则返回空指针,例6.2 删除二叉树中指定结点的左子树,bitree *DeleteLeftTree(bitree *curr) if(curr=NULL|curr-lchild=NULL) return NULL; free(curr-lchild); curr-lchild=NULL; return curr;,108,例6.3 求二叉树

41、深度,算法思想: 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，并将所得的左、右子树深度的最大值加1,109,int BTreeDepth(bitree *BT) int leftdep,rightdep; if(BT=NULL) return(0); /空二叉树 else leftdep=BTreeDepth(BT-lchild); rightdep=BTreeDepth(BT-rchild); if(leftdeprightdep) return(leftdep+1); else return(rightdep+1);,110,例

42、6.4 统计叶子结点数（1,算法思想: 中序(或前序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将遍历算法中“访问结点”的操作改为：若是叶子，则计数器增1,111,int num=0; /全局变量 void LeafCount(bitree *BT) if(BT) LeafCount(BT-lchild); /中序遍历左子树 if(!BT-lchild /中序遍历右子树,112,例6.4 统计叶子结点数（2,int leafcount(bitree *BT) if (!BT) return (0); /空树没有叶子 else /只有根结点

43、 if(!BT-lchild,113,例6.5 交换所有结点的左右子树,void Subtree_Revolute (bitree *T) bitree *p; if (T) p=T-lchild; T-lchild=T-rchild; T-rchild=p; Subtree_Revolute(T-lchild); Subtree_Revolute(T-rchild);,114,例6.6 求二叉树的结点个数,int nodecount(bitree *BT) if(BT=NULL) return(0); /空二叉树 else return(nodecount(BT-lchild) +nodec

44、ount(BT-rchild)+1);,115,例6.7 求二叉树的非叶子结点个数,int notleafcount(bitree *BT) if (!BT) return (0); /空二叉树 else /只有根结点 if (!BT-lchild,116,例6.8 设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre1.n和mid1.n中，试遍写算法建立该二叉树的二叉链表,117,1.由前序序列得根,2.若序列中多于1个元素，则在中序序列中查找根（定位根在字符串中第一次出现的位置），并确定左子树中结点个数,makeT(pre,mid,118,4.分别构造左、右子树

45、 r.lchild=makeT(lpre,lmid); r.rchild=makeT(rpre,rmid,3.分别确定左、右子树的前序序列和中序序列 lpre=pre(1,i-1); rpre=pre(i,n); lmid=mid(0,i-1); rmid=mid(i,m,119,已知具有n个结点的完全二叉树采用顺序存储结构，结点的数据信息依次存放于一维数组BT1.n中，写出中序遍历二叉树的非递归算法,120,BT1.6,中序序列：DBEAFC,121,Stack0.M-1-保存遍历过程中结点的位置； top-栈顶指针，初始为-1； i-遍历过程中使用的位置变量，初始时指向根结点,i=1,BT

46、1,1.若i指向的结点非空，则将i进栈，然后，将i指向左子树的根； 2.若i指向的结点为空，则从堆栈中退出栈顶元素送i，访问该结点，然后，将i指向右子树的根； 重复上述过程，直到i为空，并且堆栈也为空,i=2*i,i=2*i+1,122,define MaxN 100 void INORDER(datatype BT,int n) int StackMaxN,i=1,top=-1; if(n=0) do while(i=0);,123,二叉树的其它操作,建议思考以下问题： 求二叉树中只有一个孩子的结点个数 求二叉树中有两个孩子的结点个数 复制一棵二叉树 交换一棵二叉树的所有左右子树,124,二

47、叉树的操作,本节小结 深度优先遍历（包括前、中、后序） 手工能写出前、中、后序遍历的结果 要求能够写出递归和非递归的算法 广度优先遍历 了解其算法：为什么要用队列 其它操作 能把握大致方向：借助深度优先遍历、递归、广度优先遍历等,125,5.线索二叉树,一、线索二叉树的提出,二叉树的任何一种遍历，其实质均为对非线性结构的线性化。若将遍历序列中所体现的结点间的线性关系，保存在二叉树的存储结构中，则称线索二叉树,126,5.线索二叉树,例】设二叉树如图，则其中序遍历序列为：,问题】 如何保存结点在遍历序列中的线性关系,127,方案一,在二叉链表中每个结点上增加两个指针域，分别用以指向该结点在遍历序

48、列中的直接前驱和直接后继,5.线索二叉树,二叉树的中序遍历序列为,128,方案二,5.线索二叉树,利用二叉链表中的空链域保存结点间的线性关系：若结点的lchild域为空，则保存指向其直接前驱的指针；若结点的rchild域为空，则用于保存指向其直接后继的指针。 为此，每个结点还需另设两个标志域，用以指明该结点的lchild域(rchild域)中所保存的指针是指向其左(右)孩子的，还是指向其直接前驱(直接后继)的,129,二叉树的中序遍历序列为,5.线索二叉树,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,130,二、什么是线索二叉树,利用二叉链表中空的指针域指出结点在某

49、种遍历序列中的直接前驱和直接后继。指向前驱和后继的指针称为线索，加了线索的二叉树称为线索二叉树,三、线索二叉树的构造,利用链结点的空的左指针域存放该结点的直接前驱的地址，空的右指针域存放该结点的直接后继的地址；而非空的指针域仍然存放结点的左孩子或右孩子的地址,131,对下图按照中序遍历进行线索化 中序遍历的结果为：a+b*c-d-e/f 称作中序线索二叉树,NULL,NULL,132,对下图按照前序遍历进行线索化 前序遍历的结果为：-+a*b-cd/ef 称作前序线索二叉树,133,对下图按照后序遍历进行线索化 后序遍历的结果为：abcd-*+ef/- 称作后序线索二叉树,NULL,134,线

50、索二叉树：结点的结构,现在lchild有2个功能 (1)指向左孩子 (2)指向前驱结点 如何区别呢？ 增加一个标记ltag说明其当前的功能 当ltag=0时：指向左孩子，是指针 当ltag=1时：指向前驱结点，是线索 rchild类似处理,135,线索二叉树：结点类型定义,typedef int datatype; typedef struct node datatype data; struct node *lchild,*rchild; int ltag,rtag; bithptr,136,例：带了两个标志的某前序遍历结果如下表所示，请画出对应的二叉树,A,A,G,E,I,D,J,H,C,

51、F,B,Tag=1表示线索: Ltag=1表示前驱 Rtag=1表示后继,137,中序线索二叉树: a+b*c-d-e/f,138,头结点,139,线索二叉树：中序线索二叉树的遍历,线索化二叉树的目的就在于方便遍历 增加头结点 lchild是指针：指向树根 rchild是线索：指向中序遍历序列的尾结点 同时 中序遍历序列中的首结点的lchild和尾结点的rchild都是一个线索：都指向头结点 这样就能方便的进行中序和逆向中序遍历了,140,例：在中序线索二叉树中查找结点p的后继结点,二叉树中序遍历序列: a+b*c-d,当rtag=1时，后继就是p-rchild； 当rtag=0时，说明p有右

52、子树，必须沿着p的右子树的根的左子树方向查找，直到某结点的lchild域为线索(即，p右子树中最左下角的结点)，此结点就是p结点的后继,四、线索二叉链表的应用,141,中序线索二叉树查找结点p的后继结点算法,bithptr *InOrderNext(bithptr *p) bithptr *q; if (p-rtag=1) return (p-rchild); else q=p-rchild; while (q-ltag=0) q=q-lchild; return (q);,回顾二叉树的中序遍历：非递归算法,int InOrderT (bitree *T) bitree *p=T; SqSta

53、ck *S; InitStack(S); 建栈 while (p|!StackEmpty(s) if (p) Push(S,p); 二叉树非空，根结点进栈 p = p-lchild; 遍历左子树 else Pop(S,p); Visit(p-data); p = p-rchild; 遍历右子树 return OK;,143,中序线索二叉树的遍历(顺后继进行,基本思想 第一个访问的结点应该是最左下角的结点(假设为p) 然后p的后继是谁？ 若p-rchild是指针(0)，说明p有右子树，下一个结点应该是p右子树中最左下角的结点 若p-rchild是线索(1)，直接访问p-rchild 如此循环往复

54、,144,中序线索二叉树的遍历算法,int InOrderTraverse_Thr (bithptr *T) p = T-lchild; /p指向树根 while( p!=T ) /p等于T则说明已经遍历完毕 while( p-ltag=0 ) /p-lchild为指针 p = p-lchild; /则向左下走到底 Visit(p-data); /访问p while( p-rtag=1,145,中序线索二叉树的遍历,思考：如果反方向进行遍历呢(顺前驱进行)？ 第一个访问的结点应该是最右下角的结点(假设为p) 然后p的前驱是谁？ 若p-lchild是指针，说明p有左子树，前驱应该是p左子树中最右

55、下角的结点 若p-lchild是线索，直接访问p-lchild 如此循环往复,146,以后序线索二叉树为例 第一个访问的应该是最左下角的结点(假设为p)，p的后继是谁,线索二叉树：前/后序线索二叉树的遍历,147,解答 若p-rchild是线索 则后继就是p-rchild 否则 若p是树根，则无后继 若p是右孩子或者是唯一的左孩子，则后继是其父结点 若p是左孩子，且有右兄弟，则后继是p的父结点的右子树中第一个访问的结点,线索二叉树：前/后序线索二叉树的遍历,148,线索二叉树：前/后序线索二叉树的遍历,困难 对于后序线索二叉树，想要找结点p的后继结点，可能需要知道p的父结点是谁 可是这是很难办

56、到的 两种方法 从树根开始查找 改用三叉链表来表示二叉树 此困难对于后序线索二叉树找前驱结点、前序线索二叉树找后继/前驱结点同样存在,p,149,五、线索二叉树：二叉树的线索化,普通的二叉树怎么变成线索二叉树？ 称作线索化 基本思想 线索其实就是按照遍历的顺序把闲置的指针链接到前驱/后继结点： 遍历过程中维护两个指针：pre和p，分别指向遍历序列中一前一后的两个结点 若pre-rchild闲置，pre-rchild = p 若p-lchild闲置，p-lchild = pre,150,Status InOrderThreading(Bitree *Thrt,Bitree *T) Thrt =

57、(Bitree *)malloc(sizeof(bithptr); /头结点 if(!Thrt) exit(OVERFLOW); Thrt-ltag = 0; /头结点的lchild是指针 Thrt-rtag = 1; /头结点的rchild是线索 if(!T) /若T为空树，头结点的左右指针回指 Thrt-lchild=Thrt; Thrt-rchild=Thrt; else Thrt-lchild=T; /头结点的lchild指向树根 pre = Thrt; /pre是全局变量 InThreading(T); /调用中序线索化函数处理二叉树T pre-rchild = Thrt; /InT

58、hreading调用完以后 pre-rtag = 1; /就差最后一个结点没有链接好 Thrt-rchild = pre; /此时，pre指向最后一个结点 return OK;,创建中序线索二叉树的头结点,头结点与树根之间的连接,修改中序遍历的最后一个结点与头结点之间的连接,151,void InThreading(Bitree *p) if(p) /p为空则返回 InThreading(p-lchild); /左子树线索化 if(!p-lchild) /若p-lchild闲置 p-lchild = pre; p-ltag = 1; if(!pre-rchild) /若pre-rchild闲置

59、 pre-rchild = p; pre-rtag = 1; pre = p; /维持pre和p一前一后的关系 InThreading(p-rchild); /右子树线索化,152,void InThreading(Bitree *p) if(p) InThreading(p-lchild); if(!p-lchild) p-lchild = pre; p-ltag = 1; if(!pre-rchild) pre-rchild = p; pre-rtag = 1; pre = p; InThreading(p-rchild);,头结点,153,Status InOrderThreading(Bitree *Thrt,Bitree *T) . . InThreading(T); pre-rchild = Thrt; pre-rtag = 1; Thrt-rchild = pre; return OK;,头结点,pre此时指向遍历序列的最后一个结点，pre-rchild应作为线索，指向头结点,头结点的rchild应指向遍历序列的最后结点,程序结束,调用完毕,154,例：画出二叉链表存储结构上的中序线索二叉树,中序遍历序列: H,D,I,B,E,A,F,C,G,root,155,前序线索树上找前驱和后继,找前驱： 困难，需要知道其双亲,找后继： 若结点有左子女，则左子女是后继；