前言：
现在我们对“二叉堆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
