如何根据二叉树的中序和前序后序推导出整棵二叉树

Fri, Apr 1, 2016     标签： Android  

本文将主要介绍程序的主要计算流程。具体Android APP代码在请看这里。

写作目的：

1. 当然是为了为了加深理解二叉树遍历啦
2. 因为受不了笔试题老出这种题目，所以做出来方便大家以后答题O(∩_∩)O~
3. 最关键的是，每次遇到这种题目，我只会凑./捂脸

so，我决定花一个小时，写个程序一劳永逸，结果还没写完，我就学会了，不需要它了，送给大家~

---

首先在知道中序的前提下，任意知道一个前序、后序，即可以构建整棵二叉树，也就知道了所有顺序的遍历。

由前序中序推导

已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：

• 根据前序序列的第一个元素建立根结点；
• 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
• 在前序序列中确定左右子树的前序序列；
• 由左子树的前序序列和中序序列建立左子树；
• 由右子树的前序序列和中序序列建立右子树。

由后序中序推导

已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：

• 根据后序序列的最后一个元素建立根结点；
• 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
• 在后序序列中确定左右子树的后序序列；
• 由左子树的后序序列和中序序列建立左子树；
• 由右子树的后序序列和中序序列建立右子树。

引用自：http://blog.sina.com.cn/s/blog_8c243ea30102uzwo.html

核心代码

public static void calPostOrder(String preString, String midString) {
    if (preString.length() == 0) return;
    if (preString.length() == 1) {
        result.add(preString.charAt(0));
    }
    if (preString.length() > 1) {
        //前序首字母拆分中序字符串           
        String[] resultStrings = midString.split(preString.charAt(0) + "");
        for (int i = 0; i < resultStrings.length; i++) {
            String newPreString = findSubStringInPreORPostString(preString, resultStrings[i]);
            calPostOrder(newPreString, resultStrings[i]);
        }
        result.add(preString.charAt(0));
    }
}

其中findSubStringInPreORPostString()函数就是从先序字符串中取出对应中序的字符串的子串。