USACO/heritage

分析

输入二叉树的前序遍历、中序遍历，求后序遍历

对于这个题，完全可以扩展。如果我不仅仅是求出后续遍历，而要求出这棵二叉树，然后进行其他计算。那么就必须想办法把这棵树求出来。关键在于如何建立这棵二叉树。在NOIP初赛中，经常有这样的题目。手算不算难，写成程序实现就需要编程的基本功了。

采取递归的方法建立二叉树。首先取前序遍历的首元素当作二叉树的根，当前元素为根。把前序遍历中的当前元素当作中序遍历的分割点，中序遍历分割点前面的元素一定在当前元素的左子树，分割点后面元素一定在当前元素的右子树。然后加入下一个顶点，再把它当作分割点。如此递归的进行，直到二叉树建立完成。

对于这题建树与不建树都可以做。 但是建树相比不建树有点麻烦，不过这个理解。 思路：由于有中序遍历，而中序遍历是左根右，这样中序遍历就能分辨出左右孩子。所以我们以中序轴，先序遍历构造左右子树。还有先序遍历的第一个就是根，因此只需在中序遍历中找到它，就知道左右子树的先序遍历与中序遍历。 伪代码：

if n<=0 return;
 
int p=先序中的字母在中序中的位置。
 
Build(p,(char *)pre+1,(char *)mid); //递归构造左子树的遍历
 
Build(n-1-p,pre+p+1,mid+p+1);	    //递归构造右子树的遍历

还有先建好树，也简单。建好树后 后序遍历输出即可。

代码请见C Source Code/Uers:H Huang

题目拓展：想想有中序遍历和后序遍历能确定前序遍历吗？答案是肯定的。 在 UVa Online Judge 上 PID 548 - tree这题就是给出中序和后序遍历来确定先序遍历，有兴趣的话可以去做做。 当然也可以借鉴我的。

http://hi.baidu.com/knowledgetime/blog/item/b11f37f4a887422f730eec47.html

个人主页：[ http://hi.baidu.com/knowledgetime/home ]

框架

调用 create(0,元素总数-1,根节点);
void create(long L,long R,Node *C)
{
	E=下一个元素();
	if (没有下一个元素)
		return;
	else
	{
		if (E在C左边)
			create(L,分割点-1,C->左子树);
		if (E在C右边)
			create(分割点+1,R,C->右子树);
	}
}

参考代码

C++
c
pascal

引用

CmYkRgB123 [1]