猫咪宠物商店价目表优惠活动公众号推送首图@凡科快图.png
查询节点过程是,比较元素值是否相等,相等则返回,不相等则判断大小情况,迭代查询左、右子树,直到找到相等的元素,或子节点为空,返回节点不存在。
let Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
}
this.roots = null;
实例一个节点
let node = new Node()
console.log(node)
//{ key: undefined, left: null, right: null }
//Node节点实例
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.roots = null;
this.insert = insert
}
由于二叉搜索树的特殊性质确定了二叉搜索树中每个元素只可能出现一次,所以在插入的过程中如果发现这个元素已经存在于二叉搜索树中,就不进行插入。否则就查找合适的位置进行插入。
直接插入,return true;
let insert = function (key) {
let newNode = new Node(key)
if (this.roots === null) {
this.roots = newNode
}
}
如上面所说,如果在二叉搜索树中已经存在该元素,则不再进行插入,直接return false;不再让它插入;
function insertNode(node, newNode) {
if(newNode.key === node.key){
return false
}
}
可以看到节点2没有重复插入;
let BST = new BinarySearchTree();
BST.insert(2)
BST.insert(2)
BST.insert(7)
BST.insert(3)
BST.insert(1)
console.log(BST)
function insertNode(node, newNode) {
if(newNode.key === node.key){
return false
}
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)
}
}
}
//Node节点实例
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
//二叉搜索树
function BinarySearchTree() {
this.roots = null;
this.insert = insert
}
let insert = function (key) {
let newNode = new Node(key)
if (this.roots === null) {
this.roots = newNode
} else {
insertNode(this.roots, newNode)
}
}
function insertNode(node, newNode) {
if(newNode.key === node.key){
return false
}
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)
}
}
}
let BST = new BinarySearchTree();
BST.insert(2)
BST.insert(6)
BST.insert(7)
BST.insert(3)
BST.insert(1)
console.log(BST)
所谓的前序遍历就是先访问根节点,再访问左节点,最后访问右节点。
那么遍历顺序就是:8->4->2->6->12->9->15
//先序遍历是以优先于后代节点的顺序访问每一个节点。
let preOrderTraverse = function (callback) {
preOrderTraverseNode(this.roots, callback)
}
function preOrderTraverseNode(node, callback) {
if (node!==null) {
callback(node.key)
preOrderTraverseNode(node.left, callback)
preOrderTraverseNode(node.right, callback)
}
}
let BST = new BinarySearchTree();
let tree =[8,4,2,6,12,9,15]
tree.forEach(v=>{
BST.insert(v)
})
BST.preOrderTraverse(key=>console.log(key)) //8,4,2,6,12,9,15
所谓的中序遍历就是先访问左节点,再访问根节点,最后访问右节点。
那么顺序是:2->4->6->8->9->12->15
//中序遍历是一种以从最小到最大的顺序访问所有节点的遍历方式
let inOrderTraverse = function (callback) {
inOrderTraverseNode(this.roots, callback)
}
function inOrderTraverseNode(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback)
callback(node.key)
inOrderTraverseNode(node.right, callback)
}
}
let BST = new BinarySearchTree();
let tree = [8, 4, 2, 6, 12, 9, 15]
tree.forEach(v => {
BST.insert(v)
})
BST.inOrderTraverse(key => console.log(key)) //2->4->6->8->9->12->15
所谓的后序遍历就是先访问左节点,再访问右节点,最后访问根节点。
那么顺序是:2->6->4->9->15->12->8
//后序遍历是先访问节点的后代节点,再访问节点本身
let postOrderTraverse = function (callback) {
postOrderTraverseNode(this.roots, callback)
}
function postOrderTraverseNode(node, callback) {
if (node!==null) {
postOrderTraverseNode(node.left, callback)
postOrderTraverseNode(node.right, callback)
callback(node.key)
}
}
二叉树的层序遍历,即二叉树的广度遍历,先遍历根节点的相邻节点,再一次遍历相邻节点的子节点。广度遍历通常借助队列来实现。用队列来存储当前层的节点数,遍历当前层的节点,将当前层的节点依次推入数组subRes[],再将当前节点的左右子节点推入队列中,进入下一层进行遍历,直到遍历完整棵树,即完成到二叉树的层序遍历。
图片来自leetcode题解:BFS 的使用场景总结:层序遍历、最短路径问题
非常的精彩,点赞!!!
let levelOrder = function (root) {
if (!root) return []
let res = [] //结果最外层数组
let queue = [root]
while (queue.length > 0) {
var len = queue.length//当前层的节点数目
var subRes = []
for (var i = 0; i < len; i++) {
var node = queue.shift() //节点出列
subRes.push(node.val) //将当前层的节点值加入subRes数组中
//将下一层节点计入队列中
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
res.push(subRes)
}
return res
};
具体的可以查看 leetcode 这道题的题解:102. 二叉树的层序遍历
在 JavaScript 中我们可以通过 hasOwnProperty 来检测指定 key 在对象是否存在,现在我们在二叉搜索中实现一个类似的方法,传入一个值 value 判断是否在二叉搜索树中存在 。
let search = function (key) {
searchNode(this.roots, key)
}
function searchNode(node, key) {
//查找失败,返回 false
if (node === null) {
return false;
}
//比当前节点小,在左侧节点继续查找
if (node.key > key) {
searchNode(node.left, key)
}
//比当前节点大,在右侧节点继续查找
if (node.key < key) {
searchNode(node.right, key)
}
return true;
}
查找最小值,往二叉树的左侧查找,直到该节点 left 为 null 没有左侧节点,证明其是最小值。
//最小值
function min() {
return minNode(this.roots) || null
}
function minNode(node) {
console.log(node)
while (node !== null && node.left !== null) {
node = node.left
}
return node.key
}
let BST = new BinarySearchTree();
let tree = [8, 4, 2, 6, 12, 9, 15]
tree.forEach(v => {
BST.insert(v)
})
console.log(BST.min()) //2
查找最大值,往二叉树的右侧查找,直到该节点 right 为 null 没有右侧节点,证明其是最大值。
//最大值
let max = function () {
return maxNode(this.roots) || null
}
function maxNode(node) {
while (node !== null && node.right !== null) {
node = node.right
}
return node.key
}
let BST = new BinarySearchTree();
let tree = [8, 4, 2, 6, 12, 9, 15]
tree.forEach(v => {
BST.insert(v)
})
console.log(BST.max()) //15
4.1.当前节点即无左侧节点又无右侧节点,直接删除,返回 null
4.2. 若左侧节点为 null,就证明它有右侧节点,将当前节点的引用改为右侧节点的引用,返回更新之后的值
4.3. 若右侧节点为 null,就证明它有左侧节点,将当前节点的引用改为左侧节点的引用,返回更新之后的值
4.4. 若左侧节点、右侧节点都不为空情况
//移除节点
let remove = function (key) {
this.roots = removeNode(this.roots, key)
console.log(this.roots)
}
function findMinNode(node, key) {
while (node !== null && node.left !== null) {
node = findMinNode(node.left, key);
}
return node;
}
function removeNode(node, key) {
//1.要删除节点小于当前节点,往树的左侧查找
if (node.key > key) {
node.left = removeNode(node.left, key);
return node;
}
//2.要删除节点大于当前节点,往树的右侧查找
if (node.key < key) {
node.right = removeNode(node.right, key);
return node;
}
if (node.key === key) {
//1.当前节点即无左侧节点又无右侧节点,直接删除,返回 null
if (node.left === null && node.right === null) {
return null;
}
//2.若右侧节点为 null,就证明它有左侧节点,将当前节点的引用改为左侧节点的引用,返回更新之后的值
if (node.left !== null && node.right === null) {
return node.left;
}
//3.若左侧节点为 null,就证明它有右侧节点,将当前节点的引用改为右侧节点的引用,返回更新之后的值
if (node.left === null && node.right !== null) {
return node.right;
}
node.right = findMinNode(node.right, key);
return node;
}
}
let BST = new BinarySearchTree();
let tree = [8, 4, 2, 6, 12, 9, 15]
tree.forEach(v => {
BST.insert(v)
})
console.log(BST.remove(15)) //15
//基础类
function BinarySearchTree() {
let Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
}
this.roots = null;
//二叉树插入
this.insert = function (key) {
let newNode = new Node(key)
if (this.roots === null) {
this.roots = newNode
} else {
insertNode(this.roots, newNode)
}
}
function 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.inOrderTraverse = function (callback) {
inOrderTraverseNode(this.roots, callback)
}
function inOrderTraverseNode(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback)
callback(node.key)
inOrderTraverseNode(node.right, callback)
}
}
//先序遍历是以优先于后代节点的顺序访问每一个节点。
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(this.roots, callback)
}
function preOrderTraverseNode(node, callback) {
if (node !== null) {
callback(node.key)
preOrderTraverseNode(node.left, callback)
preOrderTraverseNode(node.right, callback)
}
}
//后序遍历是先访问节点的后代节点,再访问节点本身
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(this.roots, callback)
}
function postOrderTraverseNode(node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback)
postOrderTraverseNode(node.right, callback)
callback(node.key)
}
}
//搜索二叉树
this.search = function (key) {
searchNode(this.roots, key)
}
function searchNode(node, key) {
if (node === null) {
return false;
}
if (node.key > key) {
searchNode(node.left, key)
}
if (node.key < key) {
searchNode(node.right, key)
}
return true;
}
//最小值
this.min = function () {
minNode(this.roots)
}
function minNode(node) {
while (node !== null && node.left !== null) {
node = node.left
}
return node.key
}
//最大值
this.max = function () {
maxNode(this.roots)
}
function maxNode(node) {
while (node !== null && node.right !== null) {
node = node.right
}
return node.key
}
//移除节点
this.remove = function (key) {
this.roots = removeNode(this.roots, key)
}
function findMinNode(node, key) {
while (node !== null && node.left !== null) {
node = findMinNode(node.left, key);
}
return node;
}
function removeNode(node, key) {
//1.要删除节点小于当前节点,往树的左侧查找
if (node.key > key) {
node.left = removeNode(node.left, key);
return node;
}
//2.要删除节点大于当前节点,往树的右侧查找
if (node.key < key) {
node.right = removeNode(node.right, key);
return node;
}
if (node.key === key) {
//1.当前节点即无左侧节点又无右侧节点,直接删除,返回 null
if (node.left === null && node.right === null) {
return null;
}
//2.若右侧节点为 null,就证明它有左侧节点,将当前节点的引用改为左侧节点的引用,返回更新之后的值
if (node.left !== null && node.right === null) {
return node.left;
}
//3.若左侧节点为 null,就证明它有右侧节点,将当前节点的引用改为右侧节点的引用,返回更新之后的值
if (node.left === null && node.right !== null) {
return node.right;
}
node.right = findMinNode(node.right, key);
return node;
}
}
}
let nodeTree = [1, 12, 2, 3, 4, 5, 14, 6, 19];
let BST = new BinarySearchTree();
nodeTree.forEach(v => {
BST.insert(v)
})
console.log(BST.remove(19))
console.log(BST.max())
console.log(BST.min())
console.log(BST.preOrderTraverse(key => console.log(key)))
console.log(BST.inOrderTraverse(key => console.log(key)))
console.log(BST.postOrderTraverse(key => console.log(key)))
样的数据,不同的插入顺序,树的结果是不一样的。这就是二叉树的局限性。同时节点过多时,会比较消耗性能。有啥问题可以评论区留言,一起学习,一起精进。也可以 访问个人博客地址。叫我詹躲躲
在线DEMO地址在线DEMO地址
1.二叉树查找与节点删除的javascript实现
2.二叉树的javascript实现
3.JavaScript二叉树深入理解
4.数据结构(二):二叉搜索树(Binary Search Tree)
5.实现一个二叉搜索树(JavaScript 版)
6.二叉搜索树的插入与删除图解
7.二叉树的四种遍历方式
8.102. 二叉树的层序遍历