数据结构由遍历序列构造二叉树 [复制链接]

若只给出中序、前序、后序或层序遍历中任意一种遍历序列，可能会构造出结构不同的二叉树。因此在由遍历序列构造二叉树时，有以下三种情况：

下面分别介绍实现过程。

　　　　在前序序列中，第一个节点一定是二叉树的根节点；而在中序序列中，根节点将中序序列分成两个子序列。前一个子序列是根结点的左子树的中序序列，后一个子序列是根节点的右子树的中序序列。根据这两个子序列，在前序序列中找到对应的左子序列和右子序列。如此递归下去，便能确定这颗二叉树。

例如：

中序序列为：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、后序?中序

　　　　在后序序列中，最后一个节点一定是二叉树的根节点；而在中序序列中，根节点将中序序列分成两个子序列。前一个子序列是根结点的左子树的中序序列，后一个子序列是根节点的右子树的中序序列。根据这两个子序列，在后序列中找到对应的左子序列和右子序列。如此递归下去，便能确定这颗二叉树。