JavaScript 实现二叉排序树

问题

用 JavaScript 实现二叉排序树的定义和基本操作。

解答

什么是二叉排序树

二叉排序树是一种特殊的二叉树，具有以下性质：

• 若左子树不空，则左子树上所有节点的值均小于根节点的值
• 若右子树不空，则右子树上所有节点的值均大于根节点的值
• 左、右子树也分别为二叉排序树
• 没有键值相等的节点

节点定义

使用链式存储结构，每个节点包含数据域、左指针域、右指针域和计数器：

class Node {
    constructor(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
        this.count = 1; // 用于统计相同值的出现次数
    }
}

二叉排序树类

class BSTree {
    constructor() {
        this.root = null;
    }

    // 插入节点
    insert(data) {
        let newNode = new Node(data, null, null);

        if (this.root == null) {
            this.root = newNode;
        } else {
            let currNode = this.root;
            let parentNode = null;

            while (true) {
                parentNode = currNode;

                if (newNode.data < currNode.data) {
                    currNode = currNode.left;
                    if (!currNode) {
                        parentNode.left = newNode;
                        break;
                    }
                } else if (newNode.data > currNode.data) {
                    currNode = currNode.right;
                    if (!currNode) {
                        parentNode.right = newNode;
                        break;
                    }
                } else {
                    // 值相同时，计数器加1
                    currNode.count++;
                    break;
                }
            }
        }
    }

    // 查找节点
    find(data) {
        let currNode = this.root;
        while (currNode) {
            if (data === currNode.data) {
                return currNode;
            } else if (data < currNode.data) {
                currNode = currNode.left;
            } else {
                currNode = currNode.right;
            }
        }
        return null;
    }

    // 获取最小值节点
    getMinNode(node = this.root) {
        let currNode = node;
        while (currNode.left) {
            currNode = currNode.left;
        }
        return currNode;
    }

    // 获取最大值节点
    getMaxNode(node = this.root) {
        let currNode = node;
        while (currNode.right) {
            currNode = currNode.right;
        }
        return currNode;
    }

    // 删除节点
    remove(data) {
        this.root = this._removeNode(this.root, data);
    }

    _removeNode(node, data) {
        if (node == null) {
            return null;
        }

        if (data === node.data) {
            // 情况1：叶子节点
            if (node.left == null && node.right == null) {
                return null;
            }
            // 情况2：没有左子节点
            if (node.left == null) {
                return node.right;
            }
            // 情况3：没有右子节点
            if (node.right == null) {
                return node.left;
            }
            // 情况4：左右子节点都存在
            // 找到右子树的最小值节点
            let tempNode = this.getMinNode(node.right);
            node.data = tempNode.data;
            node.count = tempNode.count;
            node.right = this._removeNode(node.right, tempNode.data);
            return node;
        } else if (data < node.data) {
            node.left = this._removeNode(node.left, data);
            return node;
        } else {
            node.right = this._removeNode(node.right, data);
            return node;
        }
    }
}

测试示例

let myTree = new BSTree();

myTree.insert(20);
myTree.insert(10);
myTree.insert(30);
myTree.insert(7);
myTree.insert(9);
myTree.insert(15);
myTree.insert(42);
myTree.insert(57);

// 获取最大值
console.log(myTree.getMaxNode()); // Node {data: 57, ...}

// 获取最小值
console.log(myTree.getMinNode()); // Node {data: 7, ...}

// 删除节点
myTree.remove(7);
console.log(myTree.getMinNode()); // Node {data: 9, ...}

myTree.remove(42);
console.log(myTree.getMaxNode()); // Node {data: 57, ...}

关键点

• 二叉排序树的插入操作通过比较节点值，小于当前节点则向左子树查找，大于则向右子树查找，直到找到空位置插入
• 查找最小值只需沿着左子树一直向下，查找最大值则沿着右子树向下
• 删除节点分三种情况：叶子节点直接删除，只有一个子节点则用子节点替代，有两个子节点则用右子树的最小值替代
• 使用 count 属性可以记录相同值的出现次数，避免插入重复节点
• 删除操作使用递归实现，代码更简洁清晰