摘要：已知中序遍歷和后序遍歷中序遍歷后序遍歷根據中序和后序遍歷確定二叉樹，跟上面的方法類似，不過這次是根據后序遍歷確定根節點，根據中序遍歷確定左右子樹。

三種遍歷方法，很好記，什么時候訪問根節點就叫什么方法。如：先序遍歷，肯定就是先訪問根節點；中序遍歷，就是中間訪問根節點；后序遍歷就是最后訪問根節點。

1、先序遍歷：首先訪問根節點，然后先序遍歷左子樹，最后先序遍歷右子樹

2、中序遍歷：首先中序遍歷左子樹，然后訪問根節點，最后中序遍歷右子樹

3、后序遍歷：首先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問根節點

1、已知先序遍歷和中序遍歷：

先序遍歷：ABCDEFGHK

中序遍歷：BDCAEHGKF

算法的思想：根據先序遍歷確定根節點，根據中序遍歷確定左右子樹。先遍歷左子樹，直到左子樹為空或者左子樹為葉子結點，然后再遍歷右子樹。

在ABCDEFGHK樹中，首先根據先序遍歷確定root為A，再根據中序遍歷知道BDC是root的左子樹，EHGKF是root的右子樹；

在BDC樹中，首先根據先序遍歷可知BCD的根節點為B，再根據中序遍歷可知根節點B無左子樹，DC是根節點B的右子樹；

在DC樹中，首先根據先序遍歷可知DC樹的根節點為C，在根據中序遍歷可知D是根節點C的左子樹，根節點C無右子樹；

......每次都是先分析左子樹，左子樹分析完之后再分析右子樹。細心的同學肯定已經發現上面其實就是一個操作，每次都是根據先序遍歷先確定一個根節點，然后利用中序遍歷再將整個大樹分為左右兩個子樹，不斷重復，直到子樹中只有一個節點--葉子結點。

2、已知中序遍歷和后序遍歷:

中序遍歷：BDCAEHGKF

后序遍歷：DCBHKGFEA

根據中序和后序遍歷確定二叉樹，跟上面的方法類似，不過這次是根據后序遍歷確定根節點，根據中序遍歷確定左右子樹。

3、最后給出二叉樹中常用的創建樹，插入節點，先序、中序、后序遍歷，搜索最大值、最小值的方法

function BinarySearchTree(){
    var Node=function(key){
        this.key=key;
        this.left=null;
        this.right=null;
    }
    var root=null;

    // 創建新插入節點的Node類實例然后再判斷該節點是否為根節點
    this.insert=function(key){
        var newNode=new Node(key);
        if(root===null){
            root=newNode;
        }else{
            insertNode(root,newNode);
        }
    }

    // 插入節點
    function insertNode(node,newNode){
        // 新插入的節點小于該節點則插入到該節點的左邊
        if(node.key>newNode.key){
            if(node.left===null){
                node.left=newNode;
            }else{
                insertNode(node.left,newNode);
            }
        }else{
            if(node.right===null){
                node.right=newNode;
            }else{
                insertNode(node.right,newNode);
            }
        }
    }

    // 中序遍歷二叉樹(從小到大輸出)
    this.inOrderTraverse=function(callback){
        inOrderTraverseNode(root,callback);
    }
    var inOrderTraverseNode=function(node,callback){
        if(node!==null){
            inOrderTraverseNode(node.left,callback);
            callback(node.key);
            inOrderTraverseNode(node.right,callback);
        }
    }

    // 先序遍歷二叉樹(先訪問節點本身，然后再訪問左側子節點，最后是右側子節點)
    this.preOrderTraverse=function(callback){
        preOrderTraverseNode(root,callback);
    }
    var preOrderTraverseNode=function(node,callback){
        if(node!==null){
            callback(node.key);
            preOrderTraverseNode(node.left,callback);
            preOrderTraverseNode(node.right,callback);
        }
    }

    //后序遍歷（先訪問左側子節點，然后是右側子節點，最后是父節點本身）
    this.postOrderTraverse=function(callback){
        var postOrderTraverseNode=function(node,callback){
            if(node!==null){
                postOrderTraverseNode(node.left,callback);
                postOrderTraverseNode(node.right,callback);
                callback(node.key);
            }
        };
        postOrderTraverseNode(root,callback);
    }

    //搜索樹中最小值（最左邊的節點）
    this.min=function(){
        return minNode(root);
    }
    var minNode=function(node){
        if(node){
            while(node.left!==null){
                node=node.left;
            }
            return node.key;
        }
        return null;
    }

    //搜索樹中最大值（最右邊的節點）
    this.max=function(){
        return maxNode(root);
    }
    var maxNode=function(node){
        if(node){
            while(node.right!==null){
                node=node.right;
            }
            return node.key;
        }
        return null;
    }

}


var tree=new BinarySearchTree();
tree.insert(9);
tree.insert(12);
tree.insert(5);
tree.insert(10);
tree.insert(2);
tree.insert(6)

// 對每個節點的操作（打印）
var print=function(printNode){
    console.log(printNode);
};
console.log(tree);
console.log("----------------------------------------------");
tree.inOrderTraverse(print);
console.log("---------------------------------------");
tree.preOrderTraverse(print);
console.log("--------------------------------");
tree.postOrderTraverse(print);
console.log("--------------------------");
console.log(tree.min());
console.log("---------------------");
console.log(tree.max());