在前文數(shù)據(jù)結(jié)構(gòu)：二叉樹的原理及java實(shí)現(xiàn)中，我們已經(jīng)了解了二叉樹的原理及二叉樹的三種遍歷方式，假設(shè)父節(jié)點(diǎn)是N，左節(jié)點(diǎn)是L，右節(jié)點(diǎn)是R：

• 前序遍歷 N－>L－>R
• 中序遍歷 L－>N－>R
• 后序遍歷 L－>R－>N

對于下面的二叉樹，遍歷結(jié)果分別為

• 前序遍歷：ABDECF
• 中序遍歷：DBEACF
• 后序遍歷：DEBFCA

已知二叉樹的前序遍歷和中序遍歷，如何得到它的后序遍歷

其實(shí)，只要知道其中任意兩種遍歷的順序，我們就可以推斷出剩下的一種遍歷方式的順序，這里我們只是以：知道前序遍歷和中序遍歷，推斷后序遍歷作為例子，其他組合方式原理是一樣的。要完成這個(gè)任務(wù)，我們首先要利用以下幾個(gè)特性：

• 特性A，對于前序遍歷，第一個(gè)肯定是根節(jié)點(diǎn)；
• 特性B，對于后序遍歷，最后一個(gè)肯定是根節(jié)點(diǎn)；
• 特性C，利用前序或后序遍歷，確定根節(jié)點(diǎn)，在中序遍歷中，根節(jié)點(diǎn)的兩邊就可以分出左子樹和右子樹；
• 特性D，對左子樹和右子樹分別做前面3點(diǎn)的分析和拆分，相當(dāng)于做遞歸，我們就可以重建出完整的二叉樹；

我們以一個(gè)例子做一下這個(gè)過程，假設(shè)：

• 前序遍歷的順序是: CABGHEDF
• 中序遍歷的順序是: GHBACDEF

1. 我們根據(jù)特性A，可以得知根節(jié)點(diǎn)是C，然后，根據(jù)特性C，我們知道左子樹是：GHBA，右子樹是：DEF。

        C
     /     \
GHBA   DEF

• 取出左子樹，左子樹的前序遍歷是：ABGH，中序遍歷是：GHBA，根據(jù)特性A和C，得出左子樹的父節(jié)點(diǎn)是A，并且A沒有右子樹。

        C
      /    \
     A    DEF
    /
GBH

• 使用同樣的方法，前序是BGH，中序是GHB，得出父節(jié)點(diǎn)是B，G和H分別是左右節(jié)點(diǎn)。

          C
        /    \
       A    DEF
      /
     B
   /    \
G      H

• 回到右子樹，它的前序是EDF，中序是DEF，依然根據(jù)特性A和C，得出父節(jié)點(diǎn)是E，左右節(jié)點(diǎn)是D和F。

             C
         /        \
        A           E
      /           /    \
     B           D      F
   /    \
G      H

到此，我們得到了這棵完整的二叉樹，因此，它的后序遍歷就是：GHBADFEC。

程序?qū)崿F(xiàn)

下面我們使用程序來實(shí)現(xiàn)根據(jù)前序遍歷和中序遍歷得到后續(xù)遍歷。
首先我們需要建立節(jié)點(diǎn)的實(shí)體類

/**
 * 二叉樹的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
 */
public class TreeNode {
    private String key = null;
    private String data = null;
    public boolean isVisted = false;
    /**
     * 左兒子節(jié)點(diǎn)
     */
    public TreeNode leftChild = null;
    /**
     * 右兒子節(jié)點(diǎn)
     */
    public TreeNode rightChild = null;

    /**
     * 默認(rèn)構(gòu)造方法
     */
    public TreeNode(){}

    /**
     * @param key  層序編碼
     * @param data 數(shù)據(jù)域
     */
    public TreeNode(String key, String data){
        this.setKey(key);
        this.setData(data);
        this.leftChild = null;
        this.rightChild = null;
    }

    /**
     * 序號
     */
    public String getKey() {
        return key;
    }

    public void setKey(String key) {
        this.key = key;
    }

    /**
     * 值
     */
    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }
}

具體實(shí)現(xiàn)代碼

/**
 * 給出前序遍歷和終須遍歷，求得二叉樹及后續(xù)遍歷
 * Created by sschen on 17/5/2.
 *
 * 前序遍歷    N－>L－>R
 * 中序遍歷    L－>N－>R
 * 后序遍歷    L－>R－>N
 *
 * 特性A，對于前序遍歷，第一個(gè)肯定是根節(jié)點(diǎn)；
 * 特性B，對于后序遍歷，最后一個(gè)肯定是根節(jié)點(diǎn)；
 * 特性C，利用前序或后序遍歷，確定根節(jié)點(diǎn)，在中序遍歷中，根節(jié)點(diǎn)的兩邊就可以分出左子樹和右子樹；
 * 特性D，對左子樹和右子樹分別做前面3點(diǎn)的分析和拆分，相當(dāng)于做遞歸，我們就可以重建出完整的二叉樹；
 */
public class BinaryTreeFind {
    public static void main(String[] args) {
        /**
         *             A
         *          /        \
         *        B           C
         *      /     \          \
         *     D       E          F
         *   /        /  \           \
         *  G        H    I            J
         *   \      /
         *    K    L
         *
         * 前序遍歷： ABDGKEHLICFJ
         * 中序遍歷； GKDBLHEIACFJ
         * 后續(xù)遍歷： KGDLHIEBJFCA
         */

        String pr = "ABDGKEHLICFJ";
        String in = "GKDBLHEIACFJ";

        TreeNode node = GetTree(pr, in, "root");
        postOrder(node);
    }

    /**
     * 遞歸計(jì)算節(jié)點(diǎn)列表
     * @param pr 前序遍歷字符串
     * @param in 中序遍歷字符串
     * @param index 層級序號
     * @return 節(jié)點(diǎn)
     */
    private static TreeNode GetTree(String pr, String in, String index){
        if (pr == "" || in == "") {//如果字符串為空直接返回空值
            return null;
        }
        //前序遍歷的第一個(gè)節(jié)點(diǎn)必然是該段根節(jié)點(diǎn)
        String firstNodeValue = pr.substring(0, 1);
        TreeNode node = new TreeNode(index, firstNodeValue);

        if (in.length() == 1) {//中序遍歷沒有節(jié)點(diǎn)了，直接返回自身
            return node;
        }

        //得到跟節(jié)點(diǎn)在中序遍歷中的位置
        int iLeftLength = in.indexOf(firstNodeValue);


        if (iLeftLength == 0) {//已經(jīng)是中序遍歷的第一個(gè)元素，則代表沒有左兒子
            node.leftChild = null;
        }
        else {
            node.leftChild = GetTree(pr.substring(1, iLeftLength + 1), in.substring(0, iLeftLength),index + "-L");
        }
        if (iLeftLength == in.length() - 1) {//已經(jīng)是中序遍歷的最后一個(gè)節(jié)點(diǎn)，代表沒有右兒子
            node.rightChild = null;
        }
        else {
            node.rightChild = GetTree(pr.substring(iLeftLength + 1), in.substring(iLeftLength + 1),index + "-R");
        }
        return node;
    }

    /**
     * 對二叉樹進(jìn)行后續(xù)遍歷
     * @param subTree 二叉樹
     */
    public static void postOrder(TreeNode subTree) {
        if (subTree != null) {
            postOrder(subTree.leftChild);
            postOrder(subTree.rightChild);
            visted(subTree);
        }
    }

    public static void visted(TreeNode subTree){
        subTree.isVisted=true;
        System.out.println("key:" + subTree.getKey() + "--name:" + subTree.getData());;
    }
}

執(zhí)行結(jié)果為：

key:root-L-L-L-R--name:K
key:root-L-L-L--name:G
key:root-L-L--name:D
key:root-L-R-L-L--name:L
key:root-L-R-L--name:H
key:root-L-R-R--name:I
key:root-L-R--name:E
key:root-L--name:B
key:root-R-R-R--name:J
key:root-R-R--name:F
key:root-R--name:C
key:root--name:A

參考：
已知二叉樹的前序遍歷和中序遍歷，如何得到它的后序遍歷？