若只给出中序、前序、后序或层序遍历中任意一种遍历序列，可能会构造出结构不同的二叉树。因此在由遍历序列构造二叉树时，有以下三种情况：
前序?中序后序?中序层序?中序下面分别介绍实现过程。
1、前序?中序在前序序列中，第一个节点一定是二叉树的根节点；而在中序序列中，根节点将中序序列分成两个子序列。前一个子序列是根结点的左子树的中序序列，后一个子序列是根节点的右子树的中序序列。根据这两个子序列，在前序序列中找到对应的左子序列和右子序列。如此递归下去，便能确定这颗二叉树。
前序?中序例如：
中序序列为：EAFDHCBGI
前序序列为：DAEFBCHGI，构造过程如图所示：
①根据前序序列确定根节点为D，根据中序序列确定，左子树为：EAF；右子树为：HCBGI。
构造如图：
②在前序序列中，确定左子树的根节点为A，右子树的根节点为B；在中序序列中，确定A的左子树为：E，右子树为：F；B的左子树为：HC，右子树为：GI。
构造如图：
③最后在前序序列中确定C为B的左孩子，G为B的右孩子；在中序遍历中确定H为C的左孩子，I为G的右孩子。如下图：
「代码实现：」
Bitreepreincreat(int*a,int*b,intl1,inth1,intl2,inth2){//l1,h1是前序的第一和最后一个节点的下标。l2,h2是中序的第一和最后一个节点的下标。//初始调用时，l1=l2=1,h1=h2=nBitreeroot=(BitNode*)malloc(sizeof(BitNode));root-key=a[l1];for(i=l2;b!=root-key;i++);//根节点在中序序列的划分llen=i-l2;//左子树长度rlen=h2-i;//右子树长度if(llen)//递归建立左子树root-lchild=preincreat(a,b,l1+1,l1+llen,l2,l2+llen-1);elseroot-lchild=NULL;if(rlen)//递归建立右子树root-rchild=preincreat(a,b,h1-rlen+1,h1,h2-rlen+1,h2);elseroot-rchild=NULL;returnroot;}2、后序?中序
在后序序列中，最后一个节点一定是二叉树的根节点；而在中序序列中，根节点将中序序列分成两个子序列。前一个子序列是根结点的左子树的中序序列，后一个子序列是根节点的右子树的中序序列。根据这两个子序列，在后序列中找到对应的左子序列和右子序列。如此递归下去，便能确定这颗二叉树。
后序?中序例如：
后序遍历序列：EFAHCIGBD
中序遍历序列：EAFDHCBGI构造过程如下图所示：
①根据后序序列确定根节点为D，根据中序序列确定，左子树为：EAF；右子树为：HCBGI。
构造如图：
②在后序序列中，确定左子树的根节点为A，右子树的根节点为B；在中序序列中，确定A的左子树为：E，右子树为：F；B的左子树为：HC，右子树为：GI。
构造如图：
③最后在后序序列中确定C为B的左孩子，G为B的右孩子；在中序遍历中确定H为C的左孩子，I为G的右孩子。如下图：
「代码实现：」
Bitreepostincreat(int*a,int*b,intl1,inth1,intl2,inth2){//l1,h1是前序的第一和最后一个节点的下标。l2,h2是中序的第一和最后一个节点的下标。//初始调用时，l1=l2=1,h1=h2=nBitreeroot=(BitNode*)malloc(sizeof(BitNode));root-key=a[h1];//根节点for(i=l2;b!=root-key;i++);//根节点在中序序列的划分llen=i-l2;//左子树长度rlen=h2-i;//右子树长度if(llen)//递归建立左子树root-lchild=postincreat(a,b,l1+1,l1+llen,l2,l2+llen-1);elseroot-lchild=NULL;if(rlen)//递归建立右子树root-rchild=postincreat(a,b,h1-rlen+1,h1,h2-rlen+1,h2);elseroot-rchild=NULL;returnroot;}3、层序?中序
在层序序列中，第一个节点一定是二叉树的根节点；而在中序序列中，根节点将中序序列分成两个子序列。前一个子序列是根结点的左子树的中序序列，后一个子序列是根节点的右子树的中序序列。之后，层序序列的第二个结点一定是，根节点左子树的根节点，这样就可以在中序序列中找到左子树的左右子树。若层序序列的第三个结点没有出现在左子树的中序序列中，则第三个节点为右子树的根节点。按照这种逻辑，便能确定这颗二叉树。
层序加中序例如：
层序遍历序列：DABEFCGHI
中序遍历序列：EAFDHCBGI构造过程如下所示：
①根据层序序列确定根节点为D，根据中序序列确定，左子树为：EAF；右子树为：HCBGI。
构造如图：
②在层序序列中，确定左子树的根节点为A，右子树的根节点为B；在中序序列中，确定A的左子树为：E，右子树为：F；B的左子树为：HC，右子树为：GI。
③最后根据层序序列，确定确定C为B的左孩子，G为B的右孩子；在中序遍历中确定H为C的左孩子，I为G的右孩子。
「代码实现：」
//由层序序列和中序序列建立二叉树Bitreeleveincreat(intn,char*level,char*mid){Bitreeroot;charleft[20];charright[20];inti,j,k;intl,r;intlcnt,rcnt;lcnt=0;rcnt=0;if(n==0)returnNULL;root=(Bitree)malloc(sizeof(BitNode));root-key=level[0];//找到根节点for(i=0;in;i++)if(level[0]==mid)break;//划分左右子树for(k=0;kn;k++){for(l=0;li;l++){if(mid[l]==level[k]){left[lcnt++]=level[k];}}for(r=0;rn-i-1;r++){if(mid[r+i+1]==level[k]){right[rcnt++]=level[k];}}}root-lchild=leveincreat(lcnt,left,mid);root-rchild=leveincreat(rcnt,right,mid+i+1);returnroot;}预览时标签不可点收录于话题#个上一篇下一篇