javascript BinarySearchTree 查找树 - 二叉查找树

* BinarySearchTree

/**
 * Created by PhpStorm.
 * User: Mch
 * Date: 8/16/18
 * Time: 23:26
 */
function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
}

function BinarySearchTree() {
    this.root = null;
}

BinarySearchTree.insertNode = function(node, newNode) {
    if (newNode.key < node.key) {
        if (node.left === null) {
            node.left = newNode;
        } else {
            BinarySearchTree.insertNode(node.left, newNode);
        }
    } else {
        if (node.right === null) {
            node.right = newNode;
        } else {
            BinarySearchTree.insertNode(node.right, newNode);
        }
    }
};

BinarySearchTree.prototype.insert = function(key) {
    var newNode = new Node(key);

    if (this.root === null) {
        this.root = newNode;
    } else {
        BinarySearchTree.insertNode(this.root, newNode);
    }
};

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

BinarySearchTree.prototype.inOrderTraverse = function(callback) {
    BinarySearchTree.inOrderTraverseNode(this.root, callback);
};

BinarySearchTree.findMinNode = function(node) {
    if (node) {
        while (node && node.left !== null) {
            node = node.left;
        }
        return node;
    }
    return null;
};

BinarySearchTree.prototype.min = function() {
    return BinarySearchTree.minNode(this.root);
};

BinarySearchTree.minNode = function(node) {
    if (node) {
        while (node && node.left !== null) {
            node = node.left;
        }
        return node.key;
    }
    return null;
};

BinarySearchTree.prototype.max = function() {
    return BinarySearchTree.maxNode(this.root);
};

BinarySearchTree.maxNode = function(node) {
    if (node) {
        while (node && node.right !== null) {
            node = node.right;
        }
        return node.key;
    }
    return null;
};

BinarySearchTree.prototype.search = function(key) {
    return BinarySearchTree.searchNode(this.root, key);
};

BinarySearchTree.searchNode = function(node, key) {
    if (node === null) {
        return false;
    }
    if (key < node.key) {
        return BinarySearchTree.searchNode(node.left, key);
    } else if (key > node.key) {
        return BinarySearchTree.searchNode(node.right, key);
    }
    return true;
};

BinarySearchTree.prototype.remove = function(key) {
    this.root = BinarySearchTree.removeNode(this.root, key);
};

BinarySearchTree.removeNode = function(node, key) {
    if (node === null) {
        return null;
    }
    if (key < node.key) {
        node.left = BinarySearchTree.removeNode(node.left, key);
        return node;
    } else if (key > node.key) {
        node.right = BinarySearchTree.removeNode(node.right, key);
        return node;
    } else {
        if (node.left === null && node.right === null) {
            node = null;
            return node;
        }
        if (node.left === null) {
            node = node.right;
            return node;
        } else if (node.right === null) {
            node = node.left;
            return node;
        }

        var aux = BinarySearchTree.findMinNode(node.right);
        node.key = aux.key;
        node.right = BinarySearchTree.removeNode(node.right, aux.key);
        return node;
    }

};

BinarySearchTree.prototype.toArray = function() {
    var a = [];
    this.inOrderTraverse(function(el) {
        a.push(el);
    });
    return a;
};

exports.BinarySearchTree = BinarySearchTree;
           

Test:

/**
 * Created by Mch on 8/19/18.
 */
var bst = require('./BinarySearchTree.js');

var tree = new bst.BinarySearchTree();

[7,15,5,3,9,8,10,13,11,12,14,20,18,25].forEach(function(el) {
    tree.insert(el);
});

console.log(tree.toArray());

console.log(tree.min());
console.log(tree.max());

// root 11
tree.remove(11);
console.log(tree.toArray());
           

$ node app.js

[ 3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 25 ]

3

25

[ 3, 5, 7, 8, 9, 10, 12, 13, 14, 15, 18, 20, 25 ]