⼆叉树的重构（前序后序+中序还原⼆叉树）
只要知道前序/后序+中序就可以还原⼆叉树。
前序+中序
PreOrder:        GDAFEMHZ
InOrder:            ADEFGHMZ
通过前序我们可以到根节点为G，之后在中序中我们中序遍历的特性到G的左⼦树ADEF和右⼦树MHZ。之后在通过前序到左⼦树的根节点D，那么左⼦树的左⼦树为A，左⼦树的右⼦树为EF。之后发现A空树，那么在同理通过前序到左⼦树的右⼦树的根为F，左节点为E，之后同理就可以还原⼀棵树了。
实现
void createtree(int *pr,int *in,int len,tree &T)
{
if(len==0){
T=NULL;
return ;
}
T=new bintree;
T->date=*pr;
int len1=0;
for(;len1<len;len1++){
if(in[len1]==*pr)
break;
}
createtree(pr+1,in,len1,T->lc); // 当前树的根节点左边的⼦树
createtree(pr+len1+1,in+len1+1,len-(len1+1),T->rc); // 当前树的根节点右边的⼦树
}
相关题⽬
后序+中序
按照后序的性质最后⼀个为根节点，之后为右⼦树的根节点，和前序+中序的思路相同，就可以还原成树了
实现
void createtree(int *in,int *po,int len,tree &T)
{
if(len==0){
T=NULL;
return;
}
T=new bintree;
T->date=*po;
int len1=0;
for(;len1<len;len1++){
if(in[len1]==*po)
先序中序后序遍历二叉树break;
}
createtree(in,po-(len-len1),len1,T->lc);
createtree(in+len1+1,po-1,len-len1-1,T->rc);
}
相关题⽬
数组实现版本待补充
如果⼆叉树是真⼆叉树，那么前序+后序也可以还原如下图

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