二叉树遍历问题

摘要：已知中序遍历和后序遍历中序遍历后序遍历根据中序和后序遍历确定二叉树，跟上面的方法类似，不过这次是根据后序遍历确定根节点，根据中序遍历确定左右子树。

三种遍历方法，很好记，什么时候访问根节点就叫什么方法。如：先序遍历，肯定就是先访问根节点；中序遍历，就是中间访问根节点；后序遍历就是最后访问根节点。

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());