贵州省城乡与住房建设部网站深圳竞价托管公司

题目描述：设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组A[1…n]和 B[1…n]中，试编写算法建立该二叉树的二叉链表。

分析： 对于一颗二叉树，知道其中序和先序序列就可以完全确定其形态。

BiTree PreInOrder(ElemType A[],ElemType B[],int l1,int h1,int l2,int h2){//l1初始值为1，l2初始值为1，h1初始值为,n,h2初始值为nroot = (BiTree *)malloc(sizeof(BiTNode));root->data = A[l1];for(int i = l2;root->data != B[i];i++);llen = i - l2;rlen = h2 - i;if(llen != 0)root->lchild = PreInOrder(A,B,l1+1,l1+llen,l2,l2+llen-1);elseroot->lchild = NULL;if(rlen != 0)root->rchild = PreInOrder(A,B,h1-rlen+1,h1,h2-rlen+1,h2);else root->rchild = NULL;return root;
}