[2018年必威体育精装版整理]08二叉树的遍历及应用.pptVIP

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的结点 清空二叉树 二叉树的遍历的应用 * 如果遍历序列中没有指明空指针的位置，则需要“前序遍历序列+中序遍历序列”或 “中序遍历序列+后序遍历序列” 才能还原一棵树。 如果在前序遍历序列中以 # 号表明空指针的位置，则只需要一个前序遍历序列就可以还原这棵树。 以二叉树的前序遍历序列建立二叉树 前序：AB### A B # # # * 以二叉树的前序遍历序列建立二叉树 void CreateBTree_Pre(BTNode *root) { //要求按照前序遍历序列输入结点值item char item; cinitem; if(item == #) //如果读