二叉树是常见的数据结构之一,当然也是程序猿必须得熟悉的数据结构之一。大一时我用过C++和C语言实现过它，那最近都在用javascript，索性就写一下javascript版本的二叉树，相信不会太难。

创建二叉树

一些常见的二叉树

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

实现代码

通常二叉树都是用类的形式来创建的，虽然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实现的二叉树的创建和遍历，完整的代码请