本文主要是介绍已知二叉树先序序列和中序序列，求后序序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
回答了百度知道上的一个提问，原题是这样的：
当一棵二叉树前序序列和中序序列分别为HGEDBFCA和EGBDHFAC时，其后序序列为什么？当一棵二叉树前序序列和中序序列分别为HGEDBFCA和EGBDHFAC时，其后序序列为什么？虽然我已知道答案为EBDGACFH，请求详细算法，c语言或java都可以，也算是对你自己的一次挑战吧？哈哈
我是因为悬赏100分才做的。
先给出我的思路：
1、二叉树有根和叶子节点。我把二叉树想象成全是根，那么原来的叶子节点就是没有孩子节点的根节点了。（这个也是程序中递归结束条件）
2、根据1的设定，那么先序序列可以看作是一个根节点的遍历顺序。
3、根据1和2的想法，我的做法是根据先序序列读取根节点，然后划分中序序列。
例如：
a. 从先序序列中读取第一个字符H，然后根据H在中序序列中的位置，将中序序列切分成两部分，左边EGBD，右边FAC。
b. 递归处理左边EGBD和右边FAC序列。先是左边：从先序序列的读取第二个字符G，根据G在EGBD中的位置（此时的EGBD就是中序序列），将EGBD切分成两部分，左边E，右边BD。
c. 依旧递归处理左边的E，先从先序序列中读取下个字符是E，根据E将现在的序列切分成两部分，左边为空，右边也为空。因为E的左右孩子都没有（1中递归结束条件），递归不再进行，返回上一层，输出E，继续返回。
d. 此时，递归返回到处理b步骤中的BD序列。处理方式相同，先从先序序列中读取下一个字符D。根据D将BD切分成左边B，右边为空。继续递归处理左边的B序列。
e. …….（依次类推）
下面给出我的代码，用java写的，本来更擅长用c语言写，但是在切分字符串的时候总是很麻烦，所以用java写。
代码如下：
public class Bin {static int index = 0; //全局变量，用于遍历before序列public static void main(String[] args) {//要求数据，结果是EBDGACFHString before = new String("HGEDBFCA"); //先序序列String middle = new String("EGBDHFAC"); //中序序列//测试数据，结果是GHDBIEFCA//String before = new String("ABDGHCEIF"); //先序序列//String middle = new String("GDHBAEICF"); //中序序列Bin bin = new Bin();bin.getAfter(before, middle);}public void getAfter(String before, String middle){if(middle.length() == 0){ //递归终止条件，叶子节点return ;}//index每次递归加1，用以获取before序列中的下一个根字符char root = before.charAt(index++);//获取根在中序遍历中出现的位置，以此切割中序遍历的字符串int i = middle.indexOf(root); //切分middle字符串，得到left和right两部分String left = middle.substring(0, i);String right = middle.substring(i+1);getAfter(before, left); //递归处理左子树getAfter(before, right); //递归处理右子树//输出后序序列System.out.println("--" + root); }
}
结论：通过这个例子感受到了递归的方便，代码结构很清晰。但是就是想起来不太好想。还有就是如果是二叉树类的题目，应该都会用到递归。所以得好好练习。
这篇关于已知二叉树先序序列和中序序列，求后序序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
