二叉树排序

用二叉数来进行排序：

function BinaryTree() {
    var TreeNode = function(key) {
        this.key = key; //当前节点的值
        this.left = null; //左子树
        this.right = null; //右子树
    };
    // 根节点
    var root = null;
    var insertNode = function(node, newNode) {
        if (node.key > newNode.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 TreeNode(key);
        if (root === null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    };
    this.init = function() {
        if (
            Object.prototype.toString.call(arr) !== '[object Array]' ||
            !arr.length
        ) {
            return;
        }
        for (var i = 0, len = arr.length; i < len; i++) {
            this.insert(arr[i]);
        }
    };
    this.orderTraversal = function() {
        if (root === null) {
            //传入根节点
            console.warn('请先初始化二叉排序树');
            return;
        }
        var sorted = [];
        var fn = function(node) {
            if (node !== null) {
                //当前节点不等于空的时候,先遍历左子树节点, 再遍历自身节点, 最后遍历右子树节点
                fn(node.left); //左子树
                sorted.push(node.key);
                fn(node.right); //右子树
            }
        };
        fn(root);
        return sorted;
    };
    this.init();
}
var arr = [8, 13, 3, 7, 19, 21, 15];
// 首先构建二叉树
var tree = new BinaryTree(arr);
tree.orderTraversal(); // [3, 7, 8, 13, 15, 19, 21]