中序遍历和后序遍历怎么确定一个树,已知一棵树的中序遍历和后序遍历
普通建树：已知结点标号，每次定义一个节点的左儿子和右儿子然后建树
void build(int root,int d)//完全二叉树建树，结点由1-n编号{if(root>n)//n为总结点个数return;q[root].left=root*2;//指向的都是结点标号q[root].right=root*2+1;q[root].depth=d;//每个点的深度build(q[root].left,d+1);//左儿子建树build(q[root].right,d+1);//右儿子建树} 如果给出权值，让按照二叉搜索树的形式建树
#include<bits/stdc++.h> using namespace std;struct node{int val; //权值 int left; int right;}q[1005];int n,t;void build(int root,int val){if(!q[root].val) //如果访问到一个空结点，则赋予权值，并且赋予左右儿子编号 {q[root].val=val;q[root].left=root*2;q[root].right=root*2+1;return;}else if(q[root].val<val) // 如果当前节点的权值 小于 待插入的值 就按照题目去往左或者右，此处是左 {build(root*2,val); }elsebuild(root*2+1,val); //同上 }int main(){cin>>n;for(int i=1;i<=n;i++){cin>>t;build(1,t); //一个点一个点的处理}} 给出中序序列和后序序列（或者前序序列和中序序列）建树
例如已知序列
中序遍历为：1234567
后序遍历为：2315764
由基本思想，先找到总树的根节点就为后序遍历的最后一个点。即4为Root
然后由找到的根节点
在中序遍历中找到左子树的中序遍历结果为123。
在后序遍历中找到左子树的后序遍历结果为231。
在中序遍历中找到右子树的中序遍历结果为567。
在后序遍历中找到右子树的后序遍历结果为576。
然后再分别讨论左右子树。对左子树，再次在后序遍历中找到根节点1
然后由找到的根节点
在中序遍历中找到左子树的中序遍历结果为啥也没有
…
反复递归，建树！
用两个数组存取两种遍历的结果，每次通过调用数组下标进行递归！
例题1：已知树的后序遍历和中序遍历，求树的层序遍历。
代码如下：
#include<bits/stdc++.h>using namespace std;struct Node{int left;int right;}tree[35];int root,n,hou[35],zhong[35];vector<int> v;/*已知前序和中序时的建树int build(int l1,int r1,int l2,int r2) {if(l2>r2)return -1;int root=a[l1]; //a数组代表前序序列，b数组代表中序序列int p=l2;while(b[p]!=root) //在中序中找到根 p++;int cnt=p-l2;tree[root].flag=1;tree[root].left=build(l1+1,l1+cnt,l2,p-1); tree[root].right=build(l1+cnt+1,r1,p+1,r2);return root;}*/int build(int l1,int r1,int l2,int r2)//l1-r1表示中序遍历当前讨论的树在数组中的范围。l2-r2表示后序遍历当前讨论的树在数组中的范围 {if(l1>r1) return -1;int root=hou[r2]; //每次找到根节点的编号int p=l1;while(zhong[p]!=root){p++;}int cnt=p-l1; tree[root].left=build(l1,p-1,l2,l2+cnt-1);//遍历左子树 递归进去的下标都是跟l1,r1,l2,r2有关联的tree[root].right=build(p+1,r1,l2+cnt,r2-1);//遍历右子树//如若一序列为 中序：1234567 后序：2315764//第一次找到根节点4，在中序中分到其左子树为123，下标为0-2。在后序中分到其左子树为231，下标为0-2。故得到了该根节点左子树的中序遍历和后序遍历//则可以通过下标访问进行对各个结点的遍历。 同理可得到右子树的中序遍历和后序遍历。 return root;}//层序遍历 void bfs(){queue<int> q;q.push(root);while(!q.empty()){int a=q.front();q.pop();v.push_back(a);if(tree[a].left!=-1){q.push(tree[a].left);}if(tree[a].right!=-1){q.push(tree[a].right);}}}//前序遍历 void qianshow(int root){if(root==-1)return;cout<<root<<" ";qianshow(tree[root].left);qianshow(tree[root].right);}//中序遍历 void zhongshow(int root){if(root==-1)return;zhongshow(tree[root].left);cout<<root<<" ";zhongshow(tree[root].right);}//后序遍历 void houshow(int root){if(root==-1)return;houshow(tree[root].left);houshow(tree[root].right);cout<<root<<" ";}int main(){cin>>n;for(int i=0;i<n;i++){cin>>hou[i];}for(int i=0;i<n;i++){cin>>zhong[i];}root=build(0,n-1,0,n-1);bfs();//输出层序遍历结果 for(int i=0;i<v.size();i++)cout<<v[i]<<" ";cout<<endl;cout<<"先序：";qianshow(root);cout<<endl; cout<<"中序：";zhongshow(root);cout<<endl;cout<<"后序：";houshow(root);cout<<endl; } 对于已经建好树求任一遍历序列
void qianshow(int root){if(root==-1)return;cout<<root<<" ";show(tree[root].left);show(tree[root].right);}void zhongshow(int root){if(root==-1)return;show(tree[root].left);cout<<root<<" ";show(tree[root].right);}void houshow(int root){if(root==-1)return;show(tree[root].left);show(tree[root].right);cout<<root<<" ";} 如果是仅仅由后序和中序输出前序的话，并且节点为字母，则可以直接输出例如 中序和后序是两个字符串 中序：BADC 后序：BDCA
#include<bits/stdc++.h>using namespace std;string z,h;void build(int l1,int r1,int l2,int r2){if(l1>r1)return;char root=h[r2];cout<<root; //由于最终只是求前序遍历，每次找到根节点直接输出即可 int p=l1;while(z[p]!=root)p++;int cnt=p-l1;build(l1,p-1,l2,l2+cnt-1);build(p+1,r1,l2+cnt,r2-1);}int main(){cin>>z>>h;build(0,z.size()-1,0,h.size()-1);cout<<endl;} 另一个概念：树的镜像
所谓树的镜像是指将树中所有非叶子节点的左儿子和右儿子互换位置。
例题2：已知树的前序遍历和中序遍历，求该树的镜像的层序遍历
代码如下：
#include<bits/stdc++.h>using namespace std;struct Node{int left;int right;}tree[35];int Root,qian[35],zhong[35];vector<int> v;int build(int l1,int r1,int l2,int r2)//l1,r1是中序遍历 {if(l1>r1)return -1;int root=qian[l2];int p=l1;while(zhong[p]!=root){p++;}int cnt=p-l1;tree[root].left=build(p+1,r1,l2+cnt+1,r2);tree[root].right=build(l1,p-1,l2+1,l2+cnt);//可以发现此处在找左右儿子时，将左右儿子的递归函数交换了位置，从而按其镜像建树return root;}void bfs(int root){queue<int> q;q.push(root);while(!q.empty()){int u=q.front();q.pop();v.push_back(u);if(tree[u].left!=-1)q.push(tree[u].left);if(tree[u].right!=-1)q.push(tree[u].right);}}int main(){int n;cin>>n;for(int i=0;i<n;i++)cin>>zhong[i];for(int i=0;i<n;i++)cin>>qian[i];Root=build(0,n-1,0,n-1);int t;bfs(Root);for(int i=0;i<v.size()-1;i++)cout<<v[i]<<" ";cout<<v[v.size()-1]<<endl;}