还原二叉树（求高度并输出二叉树）-创新互联
目录
为卫辉等地区用户提供了全套网页设计制作服务，及卫辉网站建设行业解决方案。主营业务为成都网站建设、网站建设、卫辉网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！举一个例子：
求大高度
先序遍历
树的层序遍历
解析：
在还原二叉树的过程中，我们必须明确中序遍历的结果才能进行
举一个例子：已知后序遍历结果和中序遍历结果：
（依据后序从后往前的结果为根节点开始划分）
例题：
题目详情 - 7-1 还原二叉树 (pintia.cn)
（前序和中序）
求大高度#includeusing namespace std;
const int N=55;
char pre[N],inoder[N];
int n,h;
typedef struct Binode{
int elem;
Binode*lchild,*rchild;
}Binode;
Binode*creatheap(char pre[],char in[],int N){
if(N<=0)
return NULL;
Binode*T1=new Binode;
int i=0;
T1->elem=pre[0];
while(ilchild=creatheap(pre+1,in,i);
T1->rchild=creatheap(pre+i+1,in+i+1,N-i-1);
return T1;
}
int heap(Binode*T){
if(T==NULL) return 0;
else
{
int m = heap(T->lchild);
int n = heap(T->rchild);
return (m >n) ? (m+1) : (n+1);
}
}
int main(){
cin>>n;
cin>>pre>>inoder;
Binode*T;
T=creatheap(pre,inoder,n);
h=heap(T);
cout< 例题：
题目详情 - 7-2 根据后序和中序遍历输出先序遍历 (pintia.cn)
先序遍历#includeusing namespace std;
const int N=35;
int post[N],inoder[N];
int n;
typedef struct Binode{
int elem;
Binode*lchild,*rchild;
}Binode;
Binode*creatheap(int po[],int in[],int N){
if(N==0)
return NULL;
int i=0;
//Binode*T1=new Binode;
Binode*T1=(Binode*)malloc(sizeof(Binode));
T1->elem=po[N-1];
while(ielem){
break;
}
i++;
}
T1->lchild=creatheap(po,in,i);
T1->rchild=creatheap(po+i,in+i+1,N-i-1);
return T1;
}
void printheap(Binode*T){
if(T){
cout<<' '<elem;
printheap(T->lchild);
printheap(T->rchild);
}
}
int main(){
cin>>n;
Binode*T;
for(int i=0;i>post[i];
for(int i=0;i>inoder[i];
cout<<"Preorder:";
T=creatheap(post,inoder,n);
printheap(T);
} 例题：
题目详情 - 7-3 树的遍历 (pintia.cn)
树的层序遍历 解析：通过一个队列对二叉树进行遍历，与广度优先搜索极为相似
#includeusing namespace std;
const int N=35;
int post[N],inoder[N];
int n;
typedef struct BiNode{
int elem;
BiNode*lchild,*rchild;
}BiNode;
BiNode*creatheap(int p[],int in[],int N){
if(N<=0)
return NULL;
BiNode*T1=new BiNode;
T1->elem=p[N-1];
int i=0;
while(ielem==in[i])
break;
i++;
}
T1->lchild=creatheap(p,in,i);
T1->rchild=creatheap(p+i,in+i+1,N-i-1);
return T1;
}
void printfheap(BiNode*T2){
queueque;
que.push(T2);
int i=0;
while(!que.empty()){
auto p=que.front();
if(i==0)
cout<elem;
else
cout<<' '<elem;
que.pop();
if(p->lchild!=NULL)que.push(p->lchild);
if(p->rchild!=NULL)que.push(p->rchild);
i++;
}
}
int main(){
BiNode*T;
cin>>n;
for(int i=0;i>post[i];
for(int i=0;i>inoder[i];
T=creatheap(post,inoder,n);
printfheap(T);
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：还原二叉树（求高度并输出二叉树）-创新互联
本文URL：http://6mz.cn/article/cogjcj.html