数据结构-二叉树的遍历

主要内容二叉树的遍历二叉树的创建二叉树遍历的应用二叉树的遍历二叉树的遍历是指按一定次序访问二叉树中的每个结点，且每个结点仅被访问一次。在二叉树的遍历过程中不要将整棵树看成是由多个结点组成，而要看成是由根、左子树、右子树组成。ACBDGFEAA的左子树A的右子树递归的思想若限定先左后右的次序，则二叉树的遍历可有以下三种顺序：前序遍历（根->左子树->右子树）中序遍历（左子树->根->右子树）后序遍历（左子树->右子树->根）按层遍历：对二叉树按照从上至下，每层按照从左至右的顺序进行遍历。（不常用）A左=B(B左)(B右)A右=C(C左)(C右)=C(C左)前序遍历（根左右）ACBDGFEBDECGFT=A(A左)(A右)=A

B(B左)(B右)C(C左)A右A左D(B左)E(B右)B左=D(D左)(D右)=DB右=E(E左)(E右)=EGF(C左)C左=F(F左)(F右)=F(F右)G(F右)F右=G(G左)(G右)=GT=A

B(B左)(B右)C(C左)=ABDECFGA左=(B左)B(B右)A右=

(C左)C(C右)=(C左)C

中序遍历（左根右）ACBDGFEBDECGFT=(A左)A(A右)=(B左)B(B右)A(C左)CA右A左D(B左)E(B右)B左=(D左)D(D右)=DB右=

(E左)E(E右)=EGF(C左)C左=(F左)F(F右)=F(F右)G(F右)F右=(G左)G(G右)=GT=(B左)B(B右)A(C左)C=DBEAFGCA左=(B左)(B右)BA右=

(C左)(C右)C

=(C左)C

后序遍历（左右根）ACBDGFEBDECGFT=(A左)(A右)A=(B左)(B右)B(C左)CAA右A左D(B左)E(B右)B左=(D左)(D右)D=DB右=

(E左)(E右)E=EGF(C左)C左=(F左)(F右)F

=(F右)FG(F右)F右=(G左)(G右)G=GT=(B左)(B右)B(C左)CA=DEBGFCA【例】写出下面二叉树的前序、中序和后序遍历序列。前序：ABDFGCEH中序：BFDGAEHC后序：FGDBHECAACBDHEFG前序遍历（根左右）ACBDHEFGAA左子树A右子树BB右子树DFGCC左子树EH中序遍历（左根右）ACBDHEFGAA左子树A右子树BB右子树DFGCC左子树EH后序遍历（左右根）ACBDHEFGAA左子树A右子树BB右子树DFGCC左子树EH【例】已知一颗二叉树的后序遍历序列和中序遍历序列分别为EBDCA和BEADC，试画出这颗二叉树。思路：由任意一个遍历序列均不能惟一确定一颗 二叉树，只有知道中序和后序或中序和前

序遍历序列才能惟一确定一颗二叉树。确定方法：由前序（或后序）遍历序列确定树或 子树的根，再由中序遍历序列确定根 的左子树和右子树。ABCDE后序遍历序列：EBDCA（左右根）中序遍历序列：BEADC（左根右）AAEBBBEBCC确定方法：由前序（或后序）序列确定根再由中序序列确定左、右子树的范围练习：已知一颗二叉树的先序遍历序列和中序遍历序列分别为ABCDEFG和CBEDAFG，试画出这颗二叉树。

若二叉树非空，则按以下次序进行（递归）遍历：访问根结点；前序遍历根结点的左子树；前序遍历根结点的右子树。voidPreOrder(BTNode*root){ if(root!=NULL){

cout<<root->data;

//访问根 PreOrder(root->lchild);//前序遍历左子树 PreOrder(root->rchild);//前序遍历右子树 }

} ACDEFBG^^^^^^^^T前序遍历算法ABDECFG中序遍历算法若二叉树非空则按以下次序进行（递归）遍历：中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树。voidInOrder(BTNode*root){ if(root!=NULL){InOrder(root->lchild);//中序遍历左子树

cout<<root->data;

//访问根 InOrder(root->rchild);//中序遍历右子树 }

} 后序遍历算法若二叉树非空则按以下次序进行（递归）遍历：后序遍历根结点的左子树；后序遍历根结点的右子树；访问根结点。voidPostOrder(BTNode*root){ if(root!=NULL){PostOrder(root->lchild);//后序遍历左子树

PostOrder(root->rchild);//后序遍历右子树

cout<<root->data;

//访问根

}

} 建立二叉树统计二叉树中结点总数计算二叉树深度查找二叉树中值为item的结点清空二叉树二叉树的遍历的应用以二叉树的某种遍历序列建立二叉树voidCreateBTree_Pre(BTNode*&root){//要求按照前序遍历序列输入结点值item

charitem;

cin>>item; if(item=='#')//如果读入#字符，创建空树

{root=NULL;return;}else{

root=newBTNode;root->data=item; CreateBTree_Pre(root->lchild);//建左子树

CreateBTree_Pre(root->rchild);//建右子树

}}练习：请画出通过先序遍历CreateBTree_Pre按下列次序输入字符时ABC##DE#G##F###创建的二叉树。ABCDEGF统计二叉树中结点总数左子树结点数+右子树结点数+1（根结点）intBTreeCount(BTNode*root){ if(root==NULL)return0;//空树的结点数为0 else returnBiTreeCount(root->lchild)+BiTreeCount(root->rchild)+1;}计算二叉树深度左、右子树中深度较大的子树深度+1intBTreeDepth(BTNode*root){if(root==NULL)return0;else{intdepl=BTreeDepth(root->lchild);intdepr=BTreeDepth(root->rchild);if(depl>depr)returndepl+1;elsereturndepr+1;}}查找二叉树中值为item的结点BTNode*FindBTree(BTNode*root,DataTypeitem){if(root==NULL)returnNULL;if(root->data==item)returnroot;BTNode*p=FindBTree(root->lchild,item);if(p!=NULL)returnp;elsereturnFindBTree(root->rchild,item);}清空二叉树释放二叉树中所有结点voidCl