龙空技术网

4个例子,吃透 JavaScript 实现的二叉搜索树 BST

程序员小助手 88

前言:

现在我们对“二叉堆js”大概比较关注,咱们都需要剖析一些“二叉堆js”的相关内容。那么小编在网络上收集了一些关于“二叉堆js””的相关知识,希望各位老铁们能喜欢,朋友们快快来学习一下吧!

4个例子,吃透 JavaScript 实现的二叉搜索树 BST[1]1.判断BST的合法性

对于每一个节点root,代码值检查了它的左右孩子节点是否符合左小右大的原则;但是根据 BST 的定义,root的整个左子树都要小于root.val,整个右子树都要大于root.val。

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { *     this.val = (val===undefined ? 0 : val) *     this.left = (left===undefined ? null : left) *     this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {Boolean}*/const isValidBST = (root) = {    // 辅助函数传值{TreeNode} min max    const isValid = (root, min, max) => {        if (root === null) return true        // 若 root.val 不符合 max 和 min 的限制,说明不是合法 BST        if (min !== null && root.val <= min.val) return false        if (max !== null && root.val >= max.val) return false        // 限定左子树的最大值是 root.val,右子树的最小值是 root.val        return isValid(root.left, min, root) &&                isValid(root.right, root, max)    }    return isValid(root, null, null)}
2.在BST中搜索一个数

根据target和root.val的大小比较,就能排除一边。

/** * @param {TreeNode} root * @param {Number} target * @return {Boolean}*/const isInBST = (root, target) => {    if (root === null) return false    if (root.val === target) return true    // 但是穷举了所有节点    // return isInBST(root.left, target) || isInBST(root.right, target);    // 利用BST特性排除一半    if (root.val < target) return isInBST(root.right, target)    if (root.val > target) return isInBST(root.left, target)}
3.在BST中插入一个数
/*** @param {TreeNode} root* @param {Number} val* @return {TreeNode}*/const insertIntoBST = (root, val) {    if (root === null) return new TreeNode(val)    if (root.val > val) {        root.right = insertIntoBST(root.right, val)    }     if (root.val < val) {        root.left = insertIntoBST(root.left, val)    }    return root}
4.在BST中删除一个数
/*** @param {TreeNode} root* @param {Number} val* @return {TreeNode}*/const deleteNode = (root, val) {    if (root === null) return null    if (root.val === val) {        // 没有子节点或者只有一个子节点        if (root.left === null) return root.right        if (root.right === null) return root.left        // 有两个子节点 - 取右边最小来替换        let minNode = getMin(root.right)        root.val = minNode.val        root.right = deleteNode(root.right, minNode.val)    }    if (root.val > val) {        root.right = deleteNode(root.right, val)    }     if (root.val < val) {        root.left = deleteNode(root.left, val)    }    return root}// BST的最左子树就是最小const getMin(node) {    while(node.left !== null) node = node.left    return node}
引用链接

[1] 4个例子,吃透 JavaScript 实现的二叉搜索树 BST:

标签: #二叉堆js