已知中序和前序序列，或者已知中序和后序序列，都能够构造一棵二叉树。在本例中，本人用C语言写程序解答了下面两个算法题：

（1）给出一棵二叉树的中序与后序遍历序列，求出它的先序遍历序列。

（2）给出一棵二叉树的中序与先序遍历序列，求出它的后序遍历序列。

知识点扼要回顾：
所谓二叉树的遍历，是指按一定的顺序对二叉树中的每个结点均访问一次，且仅访问一。按照根结点访问位置的不同，通常把二叉树的遍历分为六种：
TLR（根左右）, TRL（根右左）, LTR（左根右）
RTL（右根左）, LRT（左右根）, RLT（右左根）

其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。

前序遍历的规律是：输出根结点，输出左子树，输出右子树；  
中序遍历的规律是：输出左子树，输出根结点，输出右子树； 
后序遍历的规律是：输出左子树，输出右子树，输出根结点；

不多说了，看代码吧：）

http://blog.csdn.net/loomman/archive/2009/03/26/4027082.aspx

评论