[聚合文章] 二叉树的创建及遍历（JavaScript实现）

学过二叉树的都应该知道，一棵二叉树最多只能有两个分支结点，当然也能没有结点。下图是常见的二叉树的形式：

图一只有一个根结点，而图2和图5除叶子节点外都有两个节点，图3和图4则是比较极端的情况，只有左子树/右子树，网上很多人都把它叫做 退化成为线性表

实现代码

通常二叉树都是用 类 的形式来创建的，虽然 javscript 现在也有 类 了，但是为了熟悉一下原型，这里还是用原型来模拟 类 的行为。以下是实现的代码：

function Node(){
    this.data = null
    this.leftChild = null
    this.rightChild = null
}

function binaryTree(){
    this.root = null
}

可以看到这里定义了两个类，一个是 Node 类，另一个是 binaryTree 类。其中一个结点含有数据域，和它的左指针以及右指针，而一颗树则含有结点包含的一切属性，以及一个根节点。这里可以看做树是结点的子类，下面则利用 原型 来实现它们之间的继承关系：

binaryTree.prototype = {
    constructor: Node,
    insertNode: function(data){
        if(this.root === null){
            this.root = {}
            this.root.data = data
        }else{
            insertNode(this.root, data)
        }
    }
}

//插入结点，这里构造的是一颗二叉搜索树
function insertNode(node,data){
    if(node.data < data){
        if(node.leftChild === null){
            node.leftChild = { data }
        }else{
            insertNode(node.leftChild, data)
        }
    }else{
        if(node.rightChild === null){
            node.rightChild = { data }
        }else{
            insertNode(node.rightChild, data)
        }
    }
}

遍历二叉树

常见的二叉树遍历方式有： 前序遍历 、 后序遍历 、 中序遍历 以及 层次遍历 ，这些遍历方式可以用 递归 来实现，当然用 队列 或者 栈 来实现也是可以的，但是 递归 还是要来得简洁一些，代码如下：

binaryTree.prototype = {
    constructor: Node,
    ...
    travelTree: function(root){//前序遍历
        console.log(root.data)
        this.travelTree(root.leftChild)
        this.travelTree(root.rightChild)
    }
}

以上就是 javascript 实现的二叉树的创建和遍历，完整的代码请 点击