利⽤后序和中序遍历恢复⼆叉树
利⽤后序和中序遍历恢复⼆叉树
  利⽤后序和中序遍历可以将⼆叉树还原出来，以便于进⾏其他树的操作。在这⾥我们还原出⼆叉树之后进⾏先序遍历来求得先序遍历的结果，我们约定还原树的函数叫做RestoreTree()。
过程
后序遍历实例:C B E H G I F D A
中序遍历实例:B C A E D G H F I
中序遍历开始位置，结束位置记做z1,z2，后序的记为h1,h2
1. 新建⼀颗空树，左右孩⼦置空
2. 拿到后序遍历的最后⼀个结点，其位置为z2，将该值存⼊树的数据域
3. 在中序遍历的序列中以遍历的⽅式到最后⼀个结点的位置，记为i
4. 如果i!=z1，说明以该结点为根结点的树有左⼦树，以递归的⽅式，调⽤当前函数恢复左⼦树
5. 如果i!=z2，说明以该结点为根结点的树有右⼦树，以递归的⽅式调⽤当前函数恢复右⼦树
6. 返回树的根结点值
需要注意的地⽅
  在恢复左右⼦树的时候，其位置需要算出来，即h1,h2和z1,z2的值需要重新计算，并在更新之后传递给RestoreTree()函数。以构建左⼦树为例，左⼦树的⾸元素下标为z1，最后⼀个元素下标为i-1，对应的h1的值为h1,h2的值为h1+(i-z1-1)，也就是h1当前的位置向前移动i-z1-1个长度。
代码实现
以实现之前提到的字母序列为例
#include<stdlib.h>
typedef struct Bitree{
char data;
struct Bitree* lchild;
struct Bitree* rchild;
}*bitree,bitnode;
bitree Createtree(void);
bitree Restoretree(int h1,int h2,int z1,int z2);
void Preorder(bitree bt);
char in[50],post[50];
int main(void)
{
int n;
scanf("%d",&n);
getchar();
/
/getchar()⽤于清除回车
for(int i =0;i < n;i++)
scanf("%c",&post[i]);
getchar();
for(int i =0;i < n;i++)
scanf("%c",&in[i]);
bitree b =Restoretree(0,n-1,0,n-1);
Preorder(b);
printf("\n");
return0;
}
bitree Createtree(void)
{
bitree bt =(bitree)malloc(sizeof(bitnode));
bt->lchild = bt->rchild =NULL;
return bt;
}
bitree Restoretree(int h1,int h2,int z1,int z2)
{
bitree bt =Createtree();
bt->data = post[h2];
for(int i = z1;i <= z2;i++)
{
if(in[i]==post[h2])
{
if(i!=z1)//存在左⼦树，构建左⼦树
bt->lchild =Restoretree(h1,h1+i-z1-1,z1,i-1);
if(i!=z2)//存在右⼦树，构建右⼦树
bt->rchild =Restoretree(h2-z2+i,h2-1,i+1,z2);
break;//到以后跳出遍历
}
}
return bt;
}
void Preorder(bitree bt)
{
if(!bt)
return;
printf("%c ",bt->data);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
  由于代码在恢复树的时候先恢复的根结点，然后访问的左右⼦树，因此，恢复的过程也相当于⼀个先根遍历的过程.如果只想求先根遍历，可以不建树.我们可以删掉先根遍历的函数，同时简化⼀些其他的语句.修改后的代码如下:
typedef struct Bitree{
char data;
struct Bitree* lchild;
struct Bitree* rchild;
}*bitree,bitnode;
void Restoretree(int h1,int h2,int z1,int z2);
char in[50],post[50];
int main(void)
{
int n;
scanf("%d",&n);
getchar();
for(int i =0;i < n;i++)
scanf("%c",&post[i]);
getchar();
for(int i =0;i < n;i++)
scanf("%c",&in[i]);
Restoretree(0,n-1,0,n-1);
printf("\n");
return0;
}
void Restoretree(int h1,int h2,int z1,int z2)
{
printf("%c ",post[h2]);
for(int i = z1;i <= z2;i++)
{
if(in[i]==post[h2])
{
if(i!=z1)//存在左⼦树，访问左⼦树
Restoretree(h1,h1+i-z1-1,z1,i-1);
if(i!=z2)//存在右⼦树，访问右⼦树
Restoretree(h2-z2+i,h2-1,i+1,z2);
break;//到以后跳出遍历
}
}
}
两段代码得到的结果是⼀样的，以下是样例输⼊:
9先序中序后序遍历二叉树
CBEHGIFDA
BCAEDGHFI
以下是输出:
A B C D E F G H I
代码拓展
  在这⾥补充⼀段利⽤先序遍历和中序遍历来还原⼆叉树并进⾏后序遍历的代码。
struct BiTree* lchild;
struct BiTree* rchild;
}bitnode,*bitree;
void Postorder(bitree bt);
bitree RestoreTree(char* pre,char* in,int q1,int q2,int z1,int z2);
int main()
{
char pre[10]={"DBACEGF"},in[10]={"ABCDEFG"};
bitree bt=RestoreTree(pre,in,0,6,0,6);
Postorder(bt);
return0;
}
bitree RestoreTree(char* pre,char* in,int q1,int q2,int z1,int z2)
{
bitree bt =(bitree)malloc(sizeof(bitnode));
bt->lchild = bt->rchild =NULL;
bt->data = pre[q1];
for(int i = z1;i<=z2;i++)
{
if(in[i]==pre[q1])
{
if(i!=z1)
bt->lchild =RestoreTree(pre,in,q1+1,q1+i-z1,z1,i-1);
if(i!=z2)
bt->rchild =RestoreTree(pre,in,q1+i-z1+1,q2,i+1,z2);
break;
}
}
return bt;
}
void Postorder(bitree bt)
{
if(bt->lchild!=NULL)
Postorder(bt->lchild);
if(bt->rchild)
Postorder(bt->rchild);
printf("%c",bt->data);
}
  代码和之前⼀样可以简化，简化以后，不需要建树，也可以进⾏后序遍历。
struct BiTree* lchild;
struct BiTree* rchild;
}bitnode,*bitree;
bitree RestoreTree(char* pre,char* in,int q1,int q2,int z1,int z2);
int main()
{
char pre[10]={"DBACEGF"},in[10]={"ABCDEFG"}; RestoreTree(pre,in,0,6,0,6);
return0;
}
bitree RestoreTree(char* pre,char* in,int q1,int q2,int z1,int z2) {
for(int i = z1;i<=z2;i++)
{
if(in[i]==pre[q1])
{
if(i!=z1)
RestoreTree(pre,in,q1+1,q1+i-z1,z1,i-1);
if(i!=z2)
RestoreTree(pre,in,q1+i-z1+1,q2,i+1,z2);
break;
}
}
printf("%c",pre[q1]);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。