二叉树的遍历和应用.ppt

1、1,二叉树的遍历和应用,数据结构与算法,2,预备知识递归,3,什么是递归,递归是极强大的问题解决技术。 当一个函数用它自己来定义时就是递归。 递归将一个复杂问题分解为一些更小的问题,4,举例：查词典,顺序查找：可以从词典第一页开始，按顺序查找每个单词，直到找到。 递归解决方案 ：分而治之的策略；把问题划分成小问题，直到到达基例,查找词典,查找词典的前半部分,查找词典的后半部分,5,递归解决方案的一般形式,怎样按同类型的更小的问题来定义问题 各个递归调用怎么减小问题规模 哪个问题实例可用做基例 随着问题规模的减小，最终能否到达基例,6,举例1：n的阶乘,public static int fac

2、t(int n) /compute the factorial of a nonnegative integer /precondition:n must be greater than or equal to 0 /postcondition:returns the factorial of n /- if (n = 0) return 1; Else return n*fact(n-1); /end if /end fact,7,举例2：逆置字符串,减小规模：去掉最后一个字符 writeBackward(s) if (the string s is empty) do nothing th

3、is is the base case Else Write the last character of s writeBackward(s minus its last character) /end if /end,减小规模：去掉第一个字符 writeBackward2(s) if (the string s is empty) do nothing this is the base case Else writeBackward2(s minus its first character) Write the first character of s /end if /end,8,举例3：

4、Hanoi塔,solveTowers(count,source,destination,spare) if (count is 1) Move a disk directly from source to destination; Else sloveTowers(count-1,source,spare,destination) sloveTowers(1,source ,destination,spare) sloveTowers(count-1,spare,destination,source) /end if /end,9,举例4：兔子繁殖(递归法,public static int

5、rabbit(int n) if (n = 2) return 1; Else return rabbit(n-1) + rabbit(n-2); /end if /end,rabbit(n),1n=1 或 n2,rabbit(n-1) + rabbit(n-2) n2,10,举例4：兔子繁殖(迭代法,public static int iterativeRabbit(int n) /iterative solution to the rabbit problem /initialize base cases: int previous = 1; /rabbit(1) int current

6、= 1; /rabbit(2) int next = 1; /result when n is 1 or 2 /computer next rabbit values when n = 3 for (int i = 3;i = n; i+) next = current + previous; previous = current; current = next; /end for return next; /end,11,二叉树的遍历,12,一、问题的提出,二、遍历算法,三、算法的递归描述,四、遍历算法的应用举例,13,顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且

7、仅被访问一次,问题的提出,访问”的含义可以很广，如：输出结 点的信息等,14,遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构,每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题,15,层次遍历,首先创建一个队列；若二叉树非空，将根放入队列； 从队列取出一个元素并访问，如果该元素有左孩子就将它放入队列，如果该元素有右孩子就将它放入队列； 若队列非空，继续第2步，直至队列为空，则二叉树的层次遍历过程结束,例如, 图5.1中的二叉树 按照层次遍历的结果为,A B C D E F G H I,

8、16,前序周游(preorder traversal) 若二叉树非空, 则依次进行如下操作: (1) 访问根结点; (2) 前序周游左子树; (3) 前序周游右子树,前序遍历二叉树(preorder traversal,例如, 图5.1中的二叉树 按照前序周游的结果为,A B D C E G F H I,17,中序周游(inorder traversal) 若二叉树非空, 则依次进行如下操作: (1) 中序周游左子树; (2) 访问根结点; (3) 中序周游右子树,中序遍历二叉树(inorder traversal,例如, 图5.1中的二叉树 按照中序周游的结果为,B D A G E C H

9、F I,18,后序周游(postorder traversal) 若二叉树非空, 则依次进行如下操作: (1) 后序周游左子树; (2) 后序周游右子树; (3) 访问根结点,后序遍历二叉树(postorder traversal,例如, 图5.1中的二叉树 按照后序周游的结果为,D B G E H I F C A,19,已知二叉树的前序和中序周游序列如下, 画出该二叉树。 前序周游序列: ABCDEFGHIJ 中序周游序列: CBEDAGHFJI,课堂练习,20,已知二叉树的后序和中序周游序列如下, 画出该二叉树。 后序周游序列: ABCDEFG 中序周游序列: ACBGEDF,课堂练习,2

10、1,画出中序周游序列为ABCDEFGHIJKL的完全二叉树,课堂练习,22,上面三种周游方法都可以用递归函数来实现 例如, 前序周游二叉树的函数为: void preorder(BinNode* subroot) if (subroot = NULL) return; visit(subroot); preorder(subroot-left(); preorder(subroot-right();,遍历二叉树的递归实现,23,课后思考,思考遍历算法的非递归算法思想描述。 由先序、中序和后序中任意两个序列能够唯一确定一颗二叉树,24,遍历算法的应用举例,1、统计二叉树中叶子结点的个数 (先序遍

11、历,2、求二叉树的深度(后序遍历,3、复制二叉树(后序遍历,4、建立二叉树的存储结构,25,1、统计二叉树中叶子结点的个数,算法基本思想,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1,26,void CountLeaf (BiTree T, int / if / CountLeaf,27,Traversal Example,Return the number of nodes in the tree template int count(BinNode* subroot)

12、 if (subroot = NULL) return 0; / Nothing to count if (subroot .isleaf() return 1; / the node is leaf return count(subroot-left() + count(subroot-right();,28,2、求二叉树的深度,算法基本思想,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1,首先分析二叉树的深度和它的左、右子树深度之间的关系,29,求二叉树的深度的 伪

13、代码设计,请利用上课讲述的方法 设计出该问题的详细算法， 多写几个,课后复习,30,二叉树的存储,31,存于顺序存储结构,32,以字符串的形式 根 左子树 右子树 定义一棵二叉树,例如,A,B,C,D,以空白字符“ ”表示,A(B( ,C( , ),D( ,空树,只含一个根结点的二叉树,A,以字符串“A ”表示,以下列字符串表示,33,Status CreateBiTree(BiTree / CreateBiTree,34,A B C D,A,B,C,D,上页算法执行过程举例如下,A,T,B,C,D,35,仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树,由二叉树的先序和中序序列

14、建树,如果同时已知二叉树的中序序列“cbdaegf”，则会如何,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,36,a b c d e f g,c b d a e g f,例如,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,37,void CrtBT(BiTree else / / CrtBT,38,T=(BiTNode*)malloc(sizeof(BiTNode); T-data = preps; if (k=is) T-Lchild = NULL; else CrtBT(T-Lchild, pre, i

15、no, ps+1, is, k-is ); if (k=is+n-1) T-Rchild = NULL; else CrtBT(T-Rchild, pre, ino, ps+1+(k-is), k+1, n-(k-is)-1,39,二叉树的线索化,40,何谓线索二叉树,遍历二叉树的结果是， 求得结点的一个线性序列,A,B,C,D,E,F,G,H,K,例如,先序序列: A B C D E F G H K,中序序列: B D C A H G K F E,后序序列: D C B H K G F E A,41,指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索,与其相应的二叉树，称作 “线索二

16、叉树,包含 “线索” 的存储结构，称作 “线索链表,A B C D E F G H K,D,C,B,E,42,在二叉链表的结点中增加两个标志域， 并作如下规定,data,LTag,RTag,LChild,RChild,LTag,RTag,0 LChild 域指示结点的左孩子,1 LChild 域指示结点的前驱,0 RChild 域指示结点的右孩子,1 RChild 域指示结点的后继,43,在中序遍历过程中修改结点的 左、右指针域，以保存当前访问结 点的“前驱”和“后继”信息。遍历过 程中，附设指针pre, 并始终保持指 针pre指向当前访问的、指针p所指 结点的前驱,如何建立线索链表,44,4

17、5,void InThreading(BiThrTree p) if (p) / 对以p为根的非空二叉树进行线索化 InThreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild); / 右子树线索化 / if / InThreading,46,Status InOrde

18、rThreading(BiThrTree / InOrderThreading,47,if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 处理最后一个结点 pre-RTag = Thread; Thrt-rchild = pre;,48,父指针表示和等价类问题,49,父指针表示法,50,等价类问题,父指针表示法可以有效的解答下述问题: 给出两个结点，它们是否在同一棵树中? / Return TRUE if nodes in different trees bool Gentree:differ(int a, int b) int root1 = FIND(a); / Find root for a int root2 = FIND(b); / F