JS二叉树遍历

关于定义，性质这些，我就直接从书上抄过来吧。

二叉树的定义：

二叉树（Binary Tree）是n个节点的有限集合，或者是空树(n=0)，或者是由一个根节点及两颗互不相交的、分别成为左子树和右子树的二叉树所组成。
有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林： m棵互不相交的树的集合
二叉树：节点的一个有限集合，该集合或者为空，或者由一个根节点加上两棵左子树和右子树组成。二叉树是每个节点最多有两个子树的树结构。
根节点：一棵树最上面的节点称为根节点。
父节点、子节点：如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点。
叶子节点：没有任何子节点的节点称为叶子节点。
兄弟节点：具有相同父节点的节点互称为兄弟节点。
节点度：节点拥有的子树数。
节点的层数：根节点层数为1，其他节点的层数为双亲节点的层数+1
树的度： 一棵树中最大的结点度数
树的深度：从根节点开始（其深度为0）自顶向下逐层累加的。
树的高度：从叶子节点开始（其高度为0）自底向上逐层累加的。54的高度是2，根节点23的高度是3。

二叉树与树的区别：

1、二叉树节点的子树要区分左子树和右子树，即使在节点只有一颗子树的情况下也要明确指出该子树是左子树还是右子树。
2、二叉树节点的最大度为2，而树中不限制节点的度数。

二叉树的性质

1、在非空二叉树中，第i层的结点总数最大为2^i-1,i>=1（满树情况）
2、深度为h的二叉树最多有 2^h-1个结点(h>=1)，最少有h个结点
3、对于任意一棵二叉树，设其总结点数为N，如果其叶结点(度为0的结点）数为N0，而度数为2的结点总数为N2，则N0=N2+1，度为1的结点数N1=N-N0-N2
4、具有n个结点的完全二叉树的深度为(logN)+1，底数为2
5、有N个结点的完全二叉树各结点如果用顺序方式存储，如果所有结点从1开始编号则结点之间有如下关系：
若i为结点编号则 如果i>1，则其父结点的编号为i/2
如果2×i<=N，则其左儿子（即左子树的根结点）的编号为2×i
若2×i>N，则无左儿子
如果2×i+1<=N，则其右儿子的结点编号为2×i+1
若2×i+1>N，则无右儿子
6、此外，如果所有结点从0开始编号，那么相应的i号节点的双亲节点的编号为（i-1）/2，左孩子的编号为2i+1，右孩子编号为2i+2。
7、给定N个结点，能构成h(N)种不同的二叉树。 h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)
8、设有i个分支点，I为所有分支点的道路长度总和，J为叶的道路长度总和J=I+2i

JS代码实现

            <script>
            function BinaryTree(){
                let Node = function(key){
                    this.key = key;
                    this.left = null;
                    this.right = null;
                }
                let root = null;
                let 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){
                    let newNode = new Node(key);
                    if(root === null){
                        root = newNode;
                    } else {
                        insertNode(root,newNode);
                    }
                };
                //中序遍历
                let inOrderTraverseNode = function(node,callback){
                    if(node !== null){
                        inOrderTraverseNode(node.left,callback);
                        callback(node.key);
                        inOrderTraverseNode(node.right,callback);
                    }
                }
                this.inOrderTraverse = function(callback){
                    inOrderTraverseNode(root,callback);
                }
            }
            let nodes = [8,3,10,1,6,14,4,7,13];
            let binaryTree = new BinaryTree();
            nodes.forEach(function(key){
                binaryTree.insert(key);
            })
            let callback = function(key){
                console.log(key);
            }
            binaryTree.inOrderTraverse(callback);
        </script>

于是JS二叉树中序遍历就完成啦。