Chapter8-2二叉树的遍历课件

1、12022/10/10中国地质大学信息工程学院Chapter8 二叉树和树12022/10/9中国地质大学信息工程学院Chapter82内容提要8.1 树8.2 二叉树8.3 二叉树的特性8.4 二叉树的描述8.5 二叉树常用操作8.6 二叉树遍历8.7 抽象数据类型BinaryTree8.8 类BinaryTree8.9 抽象数据类型及类的扩充8.10 应用2内容提要8.1 树38.6 二叉树遍历 8.6.1 遍历二叉树的定义 二叉树遍历是指按照某种顺序访问二叉树中的每个节点，使每个节点被访问一次，且只被访问一次。 “访问”的含义：是指对节点施行某种操作，操作可以是输出节点信息，修改节点的数

2、据值等，但要求这种访问不破坏它原来的数据结构。 以二叉链表作为二叉树的存储结构。38.6 二叉树遍历 8.6.1 遍历二叉树的定义 二叉4 例 假设一棵二叉树存储着有关人事方面的信息，每个节点含有姓名、工资等信息。管理和使用这些信息时可能需要作这样一些工作：（1）将每个人的工资提高20%；（2）打印每个人的姓名和工资；（3）求最低工资数额和领取最低工资的人数。对于（1），访问是对工资值进行修改的操作；对于（2），访问的含义是打印该节点的信息；对于（3），访问只是检查和统计。 不管访问的具体操作是什么，都必须做到既无重复，又无遗漏。4 例 假设一棵二叉树存储着有关人事方面的信息，每个节5线性结构

3、的遍历非线性结构的遍历只要按照结构原有的线性顺序，从第一个元素起依次访问各元素即可。每个节点可能有一个以上的直接后继；必须规定遍历的规则，并按此规则遍历二叉树；最后得到二叉树所有节点的一个线性序列。线性结构与非线性结构遍历的区别5线性结构的遍历非线性结构的遍历只要按照结构原有的线性顺序，6 8.6.2 遍历二叉树的方式 深度优先遍历：是尽可能地沿分支节点向深度方向进行周游。节点既可以在向下遍历之前访问，也可以在从子树返回之前访问。 广度优先遍历：是按照从上到下、从左到右的顺序进行层次访问节点。ABEHJDLIKCGFM6 8.6.2 遍历二叉树的方式 深度优先遍历：是尽可能地7深度优先遍历1、

4、一棵二叉树由三部分组成： 根节点（V）；左子树（L）； 右子树（R）。VLR2、若规定： L：遍历根节点的左子树 ; R：遍历根节点的右子树； V：访问根节点。则遍历二叉树有6种方式： VLR LVR LRV VRL RVL RLV 若规定按先左子树后右子树的顺序进行遍历，则有：VLR：前序遍历（先根遍历）LVR：中序遍历（中根遍历） LRV：后序遍历（后根遍历）演示8-17深度优先遍历1、一棵二叉树由三部分组成：VLR2、若规定：8 8.6.3 前序遍历1、前序遍历的递归定义若二叉树为空，遍历结束；否则（1）访问根节点；（V）（2）前序遍历根节点的左子树；（L）（3）前序遍历根节点的右子树。

5、（R）ABDEFCHIG前序遍历的序列：A B D G H C E I F演示8-2前序序列的第一个元素必为二叉树的根节点8 8.6.3 前序遍历1、前序遍历的递归定义若二叉树为空92、前序遍历的递归算法template void PreOrder ( BinaryTreeNode *t ) if ( t != NULL ) Visit(t); PreOrder ( t-LeftChild ); PreOrder ( t-RightChild ); 92、前序遍历的递归算法template 10 8.6.4 中序遍历1、中序遍历的递归定义若二叉树为空，遍历结束；否则：（1）中序遍历根节点的左子

6、树；（L）（2）访问根节点；（V）（3）中序遍历根节点的右子树。（R）ABDEFCHIG中序遍历的序列：G D H B A E I C F演示8-3中序序列的根节点恰为左右子树的中序序列的分界点10 8.6.4 中序遍历1、中序遍历的递归定义若二叉树为112、中序遍历的递归算法template void InOrder ( BinaryTreeNode *t ) if ( t != NULL ) InOrder ( t-LeftChild ); Visit(t); InOrder ( t-RightChild ); 112、中序遍历的递归算法template class T12 8.6.5 后

7、序遍历1、后序遍历的递归定义若二叉树为空，遍历结束；否则：（1）后序遍历根节点的左子树；（L）（2）后序遍历根节点的右子树。（R）（3）访问根节点；（V）ABDEFCHIG后序遍历的序列：G H D B I E F C A演示 8-4后序序列的最后一个元素必为二叉树的根节点12 8.6.5 后序遍历1、后序遍历的递归定义若二叉树为133、后序遍历的递归算法template void PostOrder ( BinaryTreeNode *t ) if ( t != NULL ) PostOrder ( t-LeftChild ); PostOrder ( t-RightChild ); Vis

8、it(t); 133、后序遍历的递归算法template T1读入+B+T1-T2topT3topET3topT4读入E读入-T3-E-T4读入/A/T2-T3BCDA20例：表达式A/(B+C*D)-E的后缀式ABCD*+/E21 8.6.7 层序遍历：广度优先遍历1、层序遍历的定义 层序遍历是指从二叉树的第1层（根节点）开始，从上至下逐层遍历，在同一层中，则按从左至右的顺序逐个访问。ABDEFCHIG层序遍历的序列：A B C D E F G H I21 8.6.7 层序遍历：广度优先遍历1、层序遍历的定义222、层序遍历的算法思想【思路】在进行层序遍历时，对第i层节点访问后，紧接着对第i

9、+1层节点进行访问，访问的顺序是按照第i层的访问顺序依次访问各节点的左孩子和右孩子。 即：先访问的节点，其左右孩子先访问； 后访问的节点，其左右孩子后访问。 设置一个队列结构222、层序遍历的算法思想【思路】在进行层序遍历时，对第i层23 层序遍历从二叉树的根节点开始， 首先将根节点指针入队， 然后从队头取出一个元素，每取出一个元素，执行两个操作：（1）访问该元素所指节点；（2）若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。 重复以上步骤，直到队列为空。层序遍历的算法思想23 层序遍历从二叉树的根节点开始，（1）访问该元素所指节点24ABDEFCHIG

10、ABCDEFGHI层序遍历结果：AIBCDEFGH层序遍历的演示24ABDEFCHIGABCDEFGHI层序遍历结果：AIB252526 例：已知一棵二叉树的前序序列和中序序列分别为ABDEGCFH和DBGEACHF，则该二叉树的后序序列为 ，层序序列为 。ABDEFCGHDGEBHFCAABCDEFGH8.6.8 由前序（后序）序列和中序序列建立二叉树ABDEGCFHDBGEACHFBDEGDBGEEGGECFHCHFFHHF左子树：右子树：26 例：已知一棵二叉树的前序序列和中序序列分别为ABDEG27 解答：若二叉树的任意两个节点的值都不相同，则二叉树的前序序列和中序序列可唯一确定一棵二

11、叉树，确定方法如下：（1）根据前序遍历的定义：前序序列的第一个元素必为二叉树的根节点； 根据中序遍历的定义：中序序列的根节点恰为左右子树的中序序列的分界点；根节点前的子序列为左子树的中序序列；根节点后的子序列为右子树的中序序列；（2）根据左子树的中序序列的节点个数，在前序序列中找出左子树的前序序列，剩下的即为右子树的前序序列；（3）然后用相同的办法分别找出左、右子树的根及其左右子树的前序序列和中序序列；（4）依此类推，直至待构造的二叉树的前序序列仅剩一个字母为止。27 解答：若二叉树的任意两个节点的值都不相同，则二叉树的28结论由二叉树的前序序列和中序序列或者中序序列和后序序列可以唯一确定一棵

12、二叉树28结论由二叉树的前序序列和中序序列或者中序序列和后序序列可29 2000年南开大学考研题 一棵非空的二叉树的前序遍历序列与后序遍历序列正好相反，则该二叉树一定满足： A、所有的节点均无左孩子 B、所有的节点均无右孩子 C、只有一个叶子节点 D、是任意一棵二叉树C课堂练习129 2000年南开大学考研题 一棵非空的二叉树的30 2000年西电考研题 一棵二叉树的前序、中序和后序序列分别如下，其中一部分未显示出来，试求出空格处的内容，并画出该二叉树。前序序列： B F ICEH G；中序序列：D KFIA EJC ； 后序序列： K FBHJ G A。ADKJBHGDIEC课堂练习230

13、2000年西电考研题 一棵二叉树的前序、中序31ABCDEFKIJHGABDFKICEHJGDBKFIAHEJCGDKIFBHJEGCA 前序遍历序列： 中序遍历序列： 后序遍历序列：31ABCDEFKIJHGABDFKICEHJGDBKFIA32课后作业 P252-练习4：绘制表达式的二叉树 P259-练习9：采用数组存储二叉树，实现中序遍历（提示：递归算法） P259-练习17：使用链式堆栈方法，来实现二叉树的前序遍历 （提示：非递归算法；在向左子树遍历之前，先把当前右子树节点压入栈中，以便后面遍历）32课后作业 P252-练习4：绘制表达式的二叉树338.7 抽象数据类型BinaryTr

14、eeADT BinaryTree实例 元素集合；如果不空，则被划分为根节点、左子树和右子树； 每棵子树仍是一棵二叉树操作 Create( )：创建一棵空二叉树 IsEmpty( )：如果二叉树为空，return true；否则return false； Root(x)：取根节点x；操作失败，return false，否则return true； MakeTree(root,left,right)：创建一棵二叉树，根节点为root BreakTree(root,left,right)：拆分二叉树 PreOrder： 前序遍历 InOrder： 中序遍历 PostOrder： 后序遍历 Level

15、Order： 层次遍历338.7 抽象数据类型BinaryTreeADT Bina34函数指针作为函数的参数int fa(int a) return a+1; int fb(int b) return b+2; int AddFunc( int (*f1)(int), int (*f2)(int) , int a, int b) return (*f1)(a) + (*f2)(b); int main( ) int a=5, b=3; a= AddFunc(fa, fb, a, b); return 0; return fa(a)+fb(b);34函数指针作为函数的参数int fa(int a

16、) r358.8 类BinaryTreetemplateclass BinaryTree public: BinaryTree( ) root = 0; BinaryTree( ); bool IsEmpty( ) const return (root) ? false : true); bool Root(T& x) const; void MakeTree(const T& element, BinaryTree& left, BinaryTree& right); void BreakTree(T& element, BinaryTree& left, BinaryTree& right

17、);358.8 类BinaryTreetemplateclas36 void PreOrder (void(*Visit)(BinaryTreeNode *u) PreOrder(Visit, root); void InOrder (void(*Visit)(BinaryTreeNode *u) InOrder(Visit, root); void PostOrder (void(*Visit)(BinaryTreeNode *u) PostOrder(Visit, root); void LevelOrder (void(*Visit)(BinaryTreeNode *u);private

18、: BinaryTreeNode *root; / 根节点指针 void PreOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void InOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void PostOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); ; 36 void PreOrder (void(*Vi37templatebool BinaryTree:Root(T& x)

19、 const if (root) x = root-data; return true; else return false; 成员函数Root（取根节点）37template 成员函数Root（取38templatevoid BinaryTree:MakeTree(const T& element, BinaryTree& left, BinaryTree& right) / 将两颗已有子树合并成一棵新树！ root = new BinaryTreeNode (element, left.root, right.root); /子树已经被合并，将其根节点置空！ left.root = rig

20、ht.root = 0; 成员函数MakeTree（创建树）38template 成员函数MakeTr39templatevoid BinaryTree:BreakTree(T& element, BinaryTree& left, BinaryTree& right) if (!root) throw BadInput( ); / tree empty / break the tree element = root-data; left.root = root-LeftChild; right.root = root-RightChild; delete root; root = 0; 成员

21、函数BreakTree（分解树）39template 成员函数BreakT40templatevoid BinaryTree:PreOrder( void(*Visit)(BinaryTreeNode *u), BinaryTreeNode *t) if (t) Visit(t); PreOrder(Visit, t-LeftChild); PreOrder(Visit, t-RightChild); 前序遍历PreOrder（private成员函数）时间复杂度(n)40template 前序遍历PreOrd41template void BinaryTree:InOrder( void(*V

22、isit)(BinaryTreeNode *u), BinaryTreeNode *t) if (t) InOrder(Visit, t-LeftChild); Visit(t); InOrder(Visit, t-RightChild); 中序遍历InOrder（private成员函数）时间复杂度(n)41template 中序遍历InOrd42template void BinaryTree:PostOrder( void(*Visit)(BinaryTreeNode *u), BinaryTreeNode *t) if (t) PostOrder(Visit, t-LeftChild);

23、 PostOrder(Visit, t-RightChild); Visit(t); 后序遍历PostOrder（private成员函数）时间复杂度(n)42template 后序遍历PostO43template void BinaryTree:LevelOrder( void(*Visit)(BinaryTreeNode *u) ) LinkedQueueBinaryTreeNode* Q; BinaryTreeNode *t; t = root; while (t) Visit(t); if (t-LeftChild) Q.Add(t-LeftChild); if (t-RightChi

24、ld) Q.Add(t-RightChild); try Q.Delete(t); catch (OutOfBounds) return; 逐层遍历LevelOrder（private成员函数）时间复杂度(n)43template 逐层遍历Level44调用示例BinaryTree a, x, y, z;int main() y.MakeTree(1, a, a); z.MakeTree(2, a, a); x.MakeTree(3, y, z); y.MakeTree(4, x, a);123444调用示例BinaryTree a, x, y,458.9 抽象数据类型及类的扩充增加二叉树的操

25、作： PreOutput( ); /按前序方式输出数据域 InOutput( ); /按中序方式输出数据域 PostOutput( ); /按后序方式输出数据域 LevelOutput( ); /逐层输出数据域 Delete( ); /删除一棵二叉树，释放其节点 Height( ); /返回树的高度 Size( ); /返回树中节点数458.9 抽象数据类型及类的扩充增加二叉树的操作：46private: static void Ouput(BinaryTreeNode *t) coutdata ; 8.9.1 输出Outputpublic: void PreOuput( ) PreOrder

26、(Output, root); coutendl; 46private: 8.9.1 输出Outputpubli47public: void InOuput( ) InOrder(Output, root); coutendl; void PostOuput( ) InOrder(Output, root); coutendl; void LevelOuput( ) LevelOrder(Output, root); coutendl; 时间复杂度(n)47public:时间复杂度(n)48public： void Delete( ) PostOrder(Free, root); root=0

27、; 8.9.2 删除Delete 通过后序遍历在访问一个节点时，将其删除。private： static void Free(BinaryTreeNode *t ) delete t; 时间复杂度(n)48public： 8.9.2 删除Delete 通过后序遍49templateint BinaryTree:Height(BinaryTree *t) const if(!t) return 0; int hl = Height(t-LefChild); int hr= Height(t-RightChild); if(hlhr) return +hl; else return +hr; 8.

28、9.3 计算高度 Height：类似后序遍历 树的高度： maxhl, hr+1时间复杂度(n)49template 8.9.3 计算高度50templateint BinaryTree:Size(BinaryTree *t) const if(!t) return 0; int sl = Size(t-LefChild); int sr= Size(t-RightChild); return (1+sl+sr); 8.9.4 统计节点数Size ：类似后序遍历时间复杂度(n)50template 8.9.4 统计节点51int _count=0; / 类外定义private: static

29、void Add1(BinaryTreeNode *t) _count+; 统计节点数另一种方法：在过程中完成51int _count=0; / 类外定义 统计节点52public:int Size( ) _count=0; PreOrder(Add1, root); return _count; 将统计函数作为函数参数传入52public: 将统计函数作为函数参数传入53类BinaryTree：调用示例#include #include binary.h/ globalsint count = 0;BinaryTree a,x,y,z;templatevoid ct(BinaryTreeNo

30、de *t) count+; 53类BinaryTree：调用示例#include io54int main() y.MakeTree(1,a,a); z.MakeTree(2,a,a); x.MakeTree(3,y,z); y.MakeTree(4,x,a); cout Preorder sequence is ; y.PreOutput(); cout Inorder sequence is ; y.InOutput(); cout Postorder sequence is ; y.PostOutput(); cout Level order sequence is ; y.Level

31、Output(); cout Number of nodes = ; cout y.Size() endl; cout Height = ; cout y.Height() endl; y.PreOrder(ct); cout Count of nodes is count endl; return 0;Preorder sequence is 4 3 1 2Inorder sequence is 1 3 2 4Postorder sequence is 1 2 3 4Level order sequence is 4 3 1 2Number of nodes = 4Height = 3Cou

32、nt of nodes is 4123454int main()Preorder sequence 55二叉树遍历的非递归算法 递归算法转换为等价的非递归算法，使用“栈” 以前序为例：根-左-右，左下降 abcde 思考：如果能在左下降的过程中，记录留待以后访问的右子树的根结点，以便在遍历完一个结点的左子树后能转移到这个结点的右子树，即可实现！55二叉树遍历的非递归算法 递归算法转换为等价的非递归算法，56非递归前序遍历二叉树主要思想：每遇到一个结点，先访问该结点，并把该结点的非空右子结点压入栈中，然后遍历其左子树；当左子树为空时，从栈顶弹出待访问的结点，继续遍历。abcde访问a进栈c左进b访问b进栈d左进空退栈d访问d左进空退栈c访问c左进e访问e左进空退栈cdcc结束56非递归前序遍历二叉树主要思想：每遇到一个结点，先访问该结57算法描述void PreOrder( BinTree T ) stack S; InitStack(&S); /递归工作栈 BinTreeNode * p = T; Push (&S, NULL); while ( p != NULL ) cout data rightChild != NULL ) Push ( &S, p-rightChild ); if ( p-leftChild != NULL ) p = p-leftChild; /进左