js之排序二叉树

先说说什么是二叉树

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序，不能颠倒。

上面是来自维基百科的解释。
而每一个节点的值总大于左子树的值，而小于右子树的值的二叉树就叫排序二叉树。
比如：

function Btree() {
    // 节点对象
    var Node = function(key) {
        this.key = key;
        this.right = null;
        this.left = 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);
        }
    };
}

我们可以看到插入到二叉树的过程就是排序的过程，又如何把其输（遍历）出来呢。
遍历可分为：

1. 前序遍历
2. 中序遍历
3. 后序遍历
   我们先看中序遍历是如何实现的，只需要在Btree中加入以下两个方法

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

this.zhongxubianli = function(callback) {
        zhongxu(root, callback);
    }

而前序后序与中序的差别不过在于callback方法的先后，即

• 前序就是先输出值再依次遍历左右子树
• 中序就是先遍历左子树再输出值然后再遍历右子树
• 后序就是先遍历左右子树再输出值

// 前序遍历
var qianxu = function(node, callback) {
        if(node !== null) {
            callback(node.key);
            zhongxu(node.left, callback);
            zhongxu(node.right, callback);
        }
    };

// 后序遍历
var houxu = function(node, callback) {
        if(node !== null) {
            zhongxu(node.left, callback);
            zhongxu(node.right, callback);
            callback(node.key);
        }
    };

测试

var nodes = [8,2,4,5,7,13,11,9,14];
var btree = new Btree();
nodes.forEach(function(key) {
    btree.insert(key);
})
var callback = function(key) {
        console.log(key);
    };
btree.zhongxubianli(callback);

结果就是：

以上就是js的排序二叉树实现过程。