摘要：已知中序遍歷和后序遍歷中序遍歷后序遍歷根據(jù)中序和后序遍歷確定二叉樹(shù)，跟上面的方法類似，不過(guò)這次是根據(jù)后序遍歷確定根節(jié)點(diǎn)，根據(jù)中序遍歷確定左右子樹(shù)。

三種遍歷方法，很好記，什么時(shí)候訪問(wèn)根節(jié)點(diǎn)就叫什么方法。如：先序遍歷，肯定就是先訪問(wèn)根節(jié)點(diǎn)；中序遍歷，就是中間訪問(wèn)根節(jié)點(diǎn)；后序遍歷就是最后訪問(wèn)根節(jié)點(diǎn)。

1、先序遍歷：首先訪問(wèn)根節(jié)點(diǎn)，然后先序遍歷左子樹(shù)，最后先序遍歷右子樹(shù)

2、中序遍歷：首先中序遍歷左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后中序遍歷右子樹(shù)

3、后序遍歷：首先后序遍歷左子樹(shù)，然后后序遍歷右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)

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

先序遍歷：ABCDEFGHK

中序遍歷：BDCAEHGKF

算法的思想：根據(jù)先序遍歷確定根節(jié)點(diǎn)，根據(jù)中序遍歷確定左右子樹(shù)。先遍歷左子樹(shù)，直到左子樹(shù)為空或者左子樹(shù)為葉子結(jié)點(diǎn)，然后再遍歷右子樹(shù)。

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

在BDC樹(shù)中，首先根據(jù)先序遍歷可知BCD的根節(jié)點(diǎn)為B，再根據(jù)中序遍歷可知根節(jié)點(diǎn)B無(wú)左子樹(shù)，DC是根節(jié)點(diǎn)B的右子樹(shù)；

在DC樹(shù)中，首先根據(jù)先序遍歷可知DC樹(shù)的根節(jié)點(diǎn)為C，在根據(jù)中序遍歷可知D是根節(jié)點(diǎn)C的左子樹(shù)，根節(jié)點(diǎn)C無(wú)右子樹(shù)；

......每次都是先分析左子樹(shù)，左子樹(shù)分析完之后再分析右子樹(shù)。細(xì)心的同學(xué)肯定已經(jīng)發(fā)現(xiàn)上面其實(shí)就是一個(gè)操作，每次都是根據(jù)先序遍歷先確定一個(gè)根節(jié)點(diǎn)，然后利用中序遍歷再將整個(gè)大樹(shù)分為左右兩個(gè)子樹(shù)，不斷重復(fù)，直到子樹(shù)中只有一個(gè)節(jié)點(diǎn)--葉子結(jié)點(diǎn)。

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

中序遍歷：BDCAEHGKF

后序遍歷：DCBHKGFEA

根據(jù)中序和后序遍歷確定二叉樹(shù)，跟上面的方法類似，不過(guò)這次是根據(jù)后序遍歷確定根節(jié)點(diǎn)，根據(jù)中序遍歷確定左右子樹(shù)。

3、最后給出二叉樹(shù)中常用的創(chuàng)建樹(shù)，插入節(jié)點(diǎn)，先序、中序、后序遍歷，搜索最大值、最小值的方法

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

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

    // 插入節(jié)點(diǎn)
    function insertNode(node,newNode){
        // 新插入的節(jié)點(diǎn)小于該節(jié)點(diǎn)則插入到該節(jié)點(diǎn)的左邊
        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);
            }
        }
    }

    // 中序遍歷二叉樹(shù)(從小到大輸出)
    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);
        }
    }

    // 先序遍歷二叉樹(shù)(先訪問(wèn)節(jié)點(diǎn)本身，然后再訪問(wèn)左側(cè)子節(jié)點(diǎn)，最后是右側(cè)子節(jié)點(diǎn))
    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);
        }
    }

    //后序遍歷（先訪問(wèn)左側(cè)子節(jié)點(diǎn)，然后是右側(cè)子節(jié)點(diǎn)，最后是父節(jié)點(diǎn)本身）
    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);
    }

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

    //搜索樹(shù)中最大值（最右邊的節(jié)點(diǎn)）
    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)

// 對(duì)每個(gè)節(jié)點(diǎn)的操作（打印）
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());