08.二叉树的遍历及应用分析.ppt

A左= (B左) (B右) B A右= (C左) (C右) C = (C左) C 后序遍历（左右根） A C B D G F E B D E C G F T= (A左) (A右) A = (B左) (B右) B (C左) C A A右 A左 D (B左) E (B右) B左= (D左) (D右) D =D B右= (E左) (E右) E =E G F (C左) C左= (F左) (F右) F = (F右) F G (F右) F右= (G左) (G右) G =G T= (B左) (B右) B (C左) C A = D E B G F C A 【例】写出下面二叉树的前序、中序和后序遍历序列。 前序：ABDFGCEH 中序：BFDGAEHC 后序：FGDBHECA A C B D H E F G 前序遍历（根 左 右） A C B D H E F G A A左子树 A右子树 B B右子树 D F G C C左子树 E H 中序遍历（左 根 右） A C B D H E F G A A左子树 A右子树 B B右子树 D F G C C左子树 E H 后序遍历（左 右 根） A C B D H E F G A A左子树 A右子树 B B右子树 D F G C C左子树 E H 【例】已知一颗二叉树的后序遍历序列和中序遍历序列分别为 EBDCA 和 BEADC ，试画出这颗二叉树。 思路：由任意一个遍历序列均不能惟一确定一颗 二叉树，只有知道中序和后序或中序和前 序遍历序列才能惟一确定一颗二叉树。 确定方法：由前序（或后序）遍历序列确定树或 子树的根，再由中序遍历序列确定根 的左子树和右子树。 A B C D E 后序遍历序列：E B D C A （左 右 根） 中序遍历序列：B E A D C （左 根 右） A A E B B B E B C C 确定方法：由前序（或后序）序列确定根 再由中序序列确定左、右子树的范围 练习： 已知一颗二叉树的先序遍历序列和中序遍历序列分别为 ABCDEFG 和 CBEDAFG ，试画出这颗二叉树。 　 若二叉树非空，则按以下次序进行（递归）遍历： 访问根结点； 前序遍历根结点的左子树； 前序遍历根结点的右子树。 void PreOrder(BTNode *root) { if(root!=NULL){ coutroot-data; //访问根 PreOrder( root-lchild ); //前序遍历左子树 PreOrder( root-rchild ); //前序遍历右子树 } } A C D E F B G ^ ^ ^ ^ ^ ^ ^ ^ T 前序遍历算法 A B D E C F G 中序遍历算法 若二叉树非空则按以下次序进行（递归）遍历： 中序遍历根结点的左子树； 访问根结点； 中序遍历根结点的右子树。 void InOrder(BTNode *root) { if(root!=NULL){ InOrder( root-lchild ); //中序遍历左子树 coutroot-data; //访问根 InOrder( root-rchild ); //中序遍历右子树 } } 后序遍历算法 若二叉树非空则按以下次序进行（递归）遍历： 后序遍历根结点的左子树； 后序遍历根结点的右子树； 访问根结点。 void PostOrder(BTNode *root) { if(root!=NULL){ PostOrder( root-lchild ); //后序遍历左子树 PostOrder( root-rchild ); //后序遍历右子树 coutroot-data; //访问根 } } 建立二叉树 统计二叉树中结点总数 计算二叉树深度 查找二叉树中值为item的结点 清空二叉树 二叉树的遍历的应用 以二叉树的某种遍历序列建立二叉树 void CreateBTree_Pre(BTNode *root) { //要求按照前序遍历序列输入结点值item char item; cinitem; if(item == #) //如果读入#字符，创建空树 { root = NULL; return ;} e