您现在的位置是:首页 > Javascript
当前栏目
4个例子,吃透 JavaScript 实现的二叉搜索树 BST
2023-02-18 16:36:02 时间
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: https://raw.githubusercontent.com/cry101/cry101.github.io/save/source/_posts/algo-1.md
相关文章
- java基于ssm,jsp鞋城源码卖鞋服装男鞋商城女鞋商城项目源码
- 前端扛把子 axios 的 GET 也要发送 JSON
- jsbridge-n22使用指南
- Express 基于 Node.js 平台,快速、开放、极简的 Web 开发框架
- NodeJS多版本切换使用(Windows)
- javaScript操作DOM
- javaScript数组方法
- JS常用方法
- 实现我博客旁边的线条效果 html canvas-nest.js 源码
- 前端工程化筑基-Node/npm/babel/polyfill/webpack
- JavaScript冒泡排序+Vue可视化冒泡动画
- JavaScript中的防抖与节流-图文版
- JavaScript入门⑩-ES6归纳汇总
- JavaScript入门⑨-异步编程●异世界之旅
- JavaScript入门⑧-事件总结大全
- JavaScript入门⑦-DOM操作大全
- JavaScript入门⑥-WEB浏览器API
- JavaScript入门⑤-欲罢不能的对象原型与继承-全网一般图文版
- JavaScript入门④-万物皆对象:Object
- JavaScript入门③-函数(2)原理{深入}执行上下文