二叉树的遍历序列求法

二叉树的前、中、后序遍历在面试题中是否常见，可以说是非常基础而又非常实用的算法。

void dfs(int x)
{
	if(x==0) return;
	cout< 
中序遍历序列为：4 2 3 1 5 
void dfs(int x)
{
	if(x==0) return;
	dfs(g[x].l);
	cout< 
后序遍历序列为：4 3 2 5 1 
void dfs(int x)
{
	if(x==0) return;
	dfs(g[x].l);
	dfs(g[x].r);
	cout< 
容易看出三种遍历方法在代码中只有一行的区别，理解起来也非常简单。
 
已知两种遍历求第三种遍历序列 
已知前序中序求后序： 
int ask(int len,int pre,int in[])
{
	for(int i=1;i<=len;i++)
		if(in[i]==pre) return i;
}

void cal(int len,int pre[],int in[])
{
	if(len<=0) return;
	int root=ask(len,pre[1],in);
	cal(root-1,pre+1,in);
	cal(len-root,pre+root,in+root);
	cout< 
已知后序中序求前序： 
int ask(int len,int pre,int in[])
{
	for(int i=1;i<=len;i++)
		if(in[i]==pre) return i;
}

void cal(int len,int h[],int in[])
{
	if(len<=0) return;
	int root=ask(len,h[len],in);
	cout< 
已知前序后序求中序： 
已知前后序遍历并不一定可以唯一确定一颗树，因此中序遍历不唯一。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5683969.html