二叉树的遍历相关问题

二叉树的四种遍历方法给定前序+中序，后序输出给定后序+中序，前序输出给定前序+中序，层序输出给定后序+中序，层序输出给定完全二叉树后序，层序输出
首先要了解

。这篇博客讲得非常清楚了，我就不再赘述。

前序：9 2 3 1 7 5 4 6 8
中序：3 1 2 7 9 4 5 8 6
后序：1 3 7 2 4 8 6 5 9
层次：9 2 5 3 7 4 6 1 8

可以观察出，前序的第一个元素（后序的最后一个元素）9可在中序中划分出左右子树，在左右子树中可以如法炮制，直到叶结点。所以根据“前序（后序）+中序”我们可以递归还原出二叉树的结构。

#include
using namespace std;
int n;
int front[11],mid[11];
void fun(int ll,int lr,int rl,int rr)
{
	if(ll>lr)
	return;
	int pos;
	int t=front[ll];
	for(int i=rl;i<=rr;i++)
	{
		if(mid[i]==t)
		{
			pos=i;
			break;
		}
	}
	fun(ll+1,ll+pos-rl,rl,pos-1);
	fun(ll+pos-rl+1,lr,pos+1,rr);
	cout<>n;
	for(int i=0;i>front[i];
	for(int i=0;i>mid[i];
	fun(0,n-1,0,n-1);
	return 0;
}

#include
using namespace std;
int n;
int mid[11],back[11];
void fun(int ll,int lr,int rl,int rr)
{
	if(ll>lr)
	return;
	cout<=rl;i--)
	{
		if(mid[i]==t)
		{
			pos=i;
			break;
		}
	}
	fun(ll,pos+ll-rl-1,rl,pos-1);
	fun(pos+ll-rl,lr-1,pos+1,rr);
}

int main()
{
	cin>>n;
	for(int i=0;i>back[i];
	for(int i=0;i>mid[i];
	fun(0,n-1,0,n-1);
	return 0;
}

当我们已经将左孩子和右孩子分别储存到他们父结点对应数组下标中，怎样按层次顺序输出？用队列即可。先将根结点入队，用数组储存的数据获得左孩子和右孩子入队，这样按层先左后右地入队，输出就获得层次遍历结果。

#include
using namespace std;
int pre[35],in[35],ltree[35],rtree[35];
int n;
queueq;

int build(int l1,int r1,int l2,int r2)
{
	if(l1>r1) return 0;
	int root=pre[l2];
	int pos=l1;
	while(in[pos]!=root) pos++;
	int len=pos-l1;
	ltree[root]=build(l1,pos-1,l2+1,l2+len);
	rtree[root]=build(pos+1,r1,l2+len+1,r2);
	return root;
}

void level(int n)
{
	int root=pre[n];
	cout<>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&in[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&pre[i]);
	build(1,n,1,n);
	level(1);
	return 0;
}

#include
using namespace std;
int in[35],post[35],ltree[35],rtree[35];
int n;
queueq;

int build(int l1,int r1,int l2,int r2)
{
	//第1,2,3,4个参数分别为所要建的树的中序左端点，中序右端点，后序左端点，后序右端点 
	if(l1>r1) return 0;
	int root=post[r2];
	int pos=l1;
	while(in[pos]!=root) pos++;//在中序中找到父结点的位置，在该位置左边的为左子树序列，右边的为右子树序列 
	int len=pos-l1;
	ltree[root]=build(l1,pos-1,l2,l2+len-1);//建左子树 
	rtree[root]=build(pos+1,r1,l2+len,r2-1);//建右子树 
	return root;//该点是上一层的左孩子or右孩子，返回到上层 
}

void level(int n)
{
	int root=post[n];//后序的最后一个为总的根结点 
	cout<>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&post[i]);//输入后序 
	for(int i=1;i<=n;i++)
		scanf("%d",&in[i]);//输入中序 
	build(1,n,1,n);//建树 
	level(n);//层序输出 
	return 0;
}

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于深度为 D 的，有 N 个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点，这样的树就是完全二叉树，换句话说，除了深度为D的一层可能不满，其他层都是满的。

给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。

输入样例：
8
91 71 2 34 10 15 55 18

输出样例：
18 34 55 71 2 10 15 91

一开始我自己是这样写的，部分超时QAQ

#include
using namespace std;
int in[35],post[35],ltree[35],rtree[35];
int n;
queueq;

int build(int l,int r)
{
	if(l>r) return 0;
	int num=r-l;
    int cnt;
	for(int i=1;i<10;i++)
	{
		num-=(1<(1<>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&post[i]);//输入后序 
	build(1,n);//建树 
	level(n);//层序输出 
	return 0;
}

看了一下别人的玄学代码，不怪我自己想不出来QAQ

#include
using namespace std;

int n,a[100];

void solve(int x) 
{
    if (x<=n) 
	{
        solve(2*x);
        solve(2*x+1);
        cin>>a[x];
    } 
	else return;
}

int main() 
{
    cin>>n;
    solve(1);
    for(int i=1;i<=n;i++) 
	{
        if(i!=n)
        cout< 

 我们复原这个递归的过程，发现递归生成出来的二叉树跟原来二叉树结构一样。递归到最深层（这个最深层，是针对单路径的）的时候开始填数（可以联系“剪葡萄”式的后序遍历过程理解，当父亲的左右儿子都被填数时才轮到父亲填数）。