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

练习：请画出通过先序遍历CreateBTree_Pre按下列次序输入字符时ABC##DE#G##F###创建的二叉树。 A B C D E G F 统计二叉树中结点总数 左子树结点数 + 右子树结点数 + 1（根结点） int BTreeCount(BTNode *root) { if(root==NULL) return 0; //空树的结点数为0 else return BiTreeCount( root-left ) + BiTreeCount( root-right ) +1; } 计算二叉树深度 左、右子树中深度较大的子树深度+1 int BTreeDepth(BTNode *root) { if(root==NULL) return 0; else{ int depl=BTreeDepth( root-left ); int depr=BTreeDepth( root-right ); if(depldepr) return depl+1; else return depr+1; } } 查找二叉树中值为item的结点 BTNode *FindBTree(BTNode* root, DataType item) { if(root==NULL) return NULL; if(root-data==item) return root; BTNode *p=FindBTree( root-left, item); if(p!=NULL) return p; else return FindBTree( root-right, item); } 清空二叉树 释放二叉树中所有结点 void ClearBTree(BTNode* root) { if(root!=NULL) { ClearBTree( root-left ); ClearBTree( root-right ); delete root; root=NULL; } } 主要内容 二叉树的遍历 二叉树遍历的应用 二叉树的遍历 二叉树的遍历是指按一定次序访问二叉树中的每个结点，且每个结点仅被访问一次。 在二叉树的遍历过程中不要将整棵树看成是由多个结点组成，而要看成是由根、左子树、右子树组成。 A C B D G F E A A 的 左 子 树 A 的 右 子 树 若限定先左后右的次序，则二叉树的遍历可有以下三种顺序： 前序遍历（根 -左子树 -右子树） 中序遍历（左子树 -根-右子树） 后序遍历（左子树 -右子树-根） 按层遍历：对二叉树按照从上至下，每层按照从左至右的顺序进行遍历。 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右) = A B (B左) (B右) C (C左) 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= A B (B左) (B右) C (C左) = A B D E C F G 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右) A (C左) C 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右) A (C左) C = D B E A F G C 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左=