JS去实现一个BST

[jinjiaxing]

树的概念：

• 根节点：没有父节点
• 节点：有父节点和子节点
• 深度：当前节点的祖先节点数量
• 高度：所有节点深度最大值
• 子树：由节点和它后代节点组成
• 二叉树：节点只能有两个子节点
  • 左节点（比父节点小）
  • 右节点(比父节点大或等于)
  • 中序遍历：左节点-节点-右节点（用于排序）
  • 先序遍历：节点-左节点-右节点（用于打印结构化文档）
  • 后续遍历：左节点-右节点-节点

function BinarySearchTree() {
    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }

    // 根节点
    var root = null;

    this.show = () => {
        console.log('root=', root);
    }

    // 插入
    this.insert = key => {
        let newNode = new Node(key);
        if (root == null) {
            root = newNode;
        } else {
            insertNode(root, newNode)
        }
    }
    let insertNode = (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.search = key => { searchNode(root, key) }
    let searchNode = (node, key) => {
        if (node == null) {
            return false;
        }
        if (key < node.key) {
            searchNode(node.left, key)
        } else if (key > node.key) {
            searchNode(node.right, key)
        } else {
            return true;
        }
    }
    // 删除
    this.remove = key => { root = removeNode(root, key) }
    let removeNode = (node, key) => {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = removeNode(node.left, key);
        } else if (key > node.key) {
            node.right = removeNode(node.right, key);
        } else {
            // 没有左右子节点的情况
            if (node.left == null && node.right == null) {
                node = null;
                return node;
            }
            // 只有一个子节点(如只有左节点或只有右节点)
            if (node.left == null && node.right !== null) {
                node = node.right;
                return node;
            } else if (node.right == null && node.left !== null) {
                node = node.left;
                return node;
            }
            // 两个子节点的节点(左右节点都存在)
            if (node.left && node.right) {
                // 找到该节点右侧的最小节点，替换当前节点
                let findRightMin = (node) => {
                    while (node && node.left !== null) {
                        node = node.left;
                    }
                    return node;
                }
                // 用右侧最小节点去替换当前节点
                var aux = findMinNode(node.right);
                node.key = aux.key;
                node.right = removeNode(node.right, aux.key);
                // 同事需要删除右侧最小节点
                return node;
            }

        }

    }
    // 中序遍历
    this.inOrder = () => {
        inOrderNode(root, (nodeKey) => { console.log(nodeKey) })
    }
    let inOrderNode = (node, callback) => {
        if (node !== null) {
            inOrderNode(node.left, callback);
            callback(node.key);
            inOrderNode(node.right, callback);
        }
    }
    // 前序遍历
    this.preOrder = () => { preOrderNode(root, (nodeKey) => { console.log(nodeKey) }) }
    let preOrderNode = (node, callback) => {
        if (node !== null) {
            callback(node.key);
            preOrderNode(node.left, callback);
            preOrderNode(node.right, callback);
        }
    }
    // 后序遍历
    this.postOrder = () => { postOrderNode(root, (nodeKey) => { console.log(nodeKey) }) }
    let postOrderNode = (node, callback) => {
        if (node !== null) {
            postOrderNode(node.left, callback);
            postOrderNode(node.right, callback);
            callback(node.key);
        }
    }
    // 树的最小值
    this.min = () => { return minNode(root) }
    let minNode = (node) => {
        if (node) {
            while (node && node.left !== null) {
                node = node.left;
            }

            return node.key;
        }
        return null;
    }
    // 树的最大值
    this.max = () => { return maxNode(root) }
    let maxNode = (node) => {
        if (node) {
            while (node && node.right !== null) {
                node = node.right;
            }

            return node.key;
        }
        return null;
    }


}