6.65.c

数据结构习题及答案

6.65④  已知一棵二叉树的前序序列和中序序列分别
存于两个一维数组中，试编写算法建立该二叉树的二
叉链表。

要求实现以下函数：
void BuildBiTree(BiTree &bt, int ps, char *pre, 
                             int is, char *ino, int n);
/* 当前要建立的子树bt的元素总数为n，*/
/* 元素在前序序列pre的起始位置为ps，*/
/* 元素在中序序列ino的起始位置为is  */

二叉链表类型定义：
typedef char TElemType;
typedef struct BiTNode {
    TElemType data;
    BiTNode  *lchild, *rchild;
} BiTNode, *BiTree;
void BuildBiTree(BiTree &bt, int ps, char *pre, 
                             int is, char *ino, int n)
/* 当前要建立的子树bt的元素总数为n，*/
/* 元素在前序序列pre的起始位置为ps，*/
/* 元素在中序序列ino的起始位置为is  */
{int i;
 if(n==0)
  bt=NULL;
 else 
  {for(i=is;i<is+n;i++)
    if(ino[i]==pre[ps])
     break;
   if(i==is+n)
    bt=NULL;
   else
    {bt=(BiTNode*)malloc(sizeof(BiTNode));
     bt->data=pre[ps];
     if(i==is)
      bt->lchild=NULL;
     else
      BuildBiTree(bt->lchild,ps+1,pre,is,ino,i-is);
     if(i==(is+n-1))
      bt->rchild=NULL;
     else 
      BuildBiTree(bt->rchild,ps+1+(i-is),pre,i+1,ino,n-(i-is)-1);
    }
  }
}