浅谈js之二叉树的前，中，后序的遍历

二叉树遍历分为三种：前序、中序、后序，其中序遍历最为重要。为啥叫这个名字？是根据根节点的顺序命名的。

比如上图正常的一个满节点，A：根节点、B：左节点、C：右节点，前序顺序是ABC（根节点排最先，然后同级先左后右）；中序顺序是BAC(先左后根最后右）；后序顺序是BCA（先左后右最后根）。

实现前，中，后序的代码如下：

<script>
    window.onload = function(){
        function BinaryTree(){
            //创建二叉树的基本结构
            var Node = function(key){
                this.key = key;
                this.left = null;
                this.right = null;
            };

            var root = null;//根节点的值

            //放置左右节点的值
            var insertNode = function(node,newNode){
                if(newNode.key<node.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.insert = function(key){
                var newNode = new Node(key);
                if(root === null){
                    root = newNode;
                }else{
                    insertNode(root,newNode)
                }
            };

            var inOrderTraverseNode = function(node,callback){
                //如果node为null返回callback
                if(node !== null){
                    inOrderTraverseNode(node.left,callback);
                    callback(node.key);
                    inOrderTraverseNode(node.right,callback);
                }
            }

            this.inOrderTraverse = function(callback){
                inOrderTraverseNode(root,callback);
            }

            var preOrderTraverseNode = function(node,callback){
                if(node !== null){
                    callback(node.key);
                    preOrderTraverseNode(node.left,callback);
                    preOrderTraverseNode(node.right,callback);
                }
            }

            this.preOrderTraverse = function(callback){
                preOrderTraverseNode(root,callback);
            }

            var postOrderTraverseNode = function(node,callback){
                if(node !== null){
                    postOrderTraverseNode(node.left,callback);
                    postOrderTraverseNode(node.right,callback);
                    callback(node.key);
                }
            }

            this.postOrderTraverse = function(callback){
                postOrderTraverseNode(root,callback);
            }
        }
        var nodes = [8,3,10,1,6,14,4,7,13];
        var binaryTree = new BinaryTree();
        nodes.forEach( function(key) {
            binaryTree.insert(key);
        });

        var callback = function(key){
            console.log(key);
        }
        //中序遍历
        // binaryTree.inOrderTraverse(callback);
        //前序遍历
        // binaryTree.preOrderTraverse(callback);
        //后序遍历
        binaryTree.postOrderTraverse(callback);
    }
</script>