实现二叉搜索树
二叉树的操作有
- 插入节点
- 查找节点
- 删除节点（复杂）
- 前序遍历（中左右）
- 中序遍历（左中右）
- 后序遍历（左右中）
- 广度优先遍历（层次遍历）
- 获取最小值节点
- 获取最大值节点
- 获取树的深度
class BstNode {
constructor(val, left = null, right = null) {
this.val = val
this.left = left
this.right = right
}
print() {
console.log(this.val);
}
}
// 二叉搜索树，左节点 < 父节点 < 右节点
class BinarySearchTree {
constructor() {
this.root = null // 根节点
}
// 插入节点
insert(val) {
const node = new BstNode(val)
if (!this.root) {
this.root = node
return
}
// 遍历，通过比较val大小找到合适的位置插入新节点
let cur = this.root
while (true) {
// 比父节点小时，新节点位置一定在父节点左侧
// 比父节点大时，新节点位置一定在父节点右侧
if (val < cur.val) {
if (cur.left === null) {
cur.left = node
break
}
cur = cur.left // 继续往左侧找
} else {
if (cur.right === null) {
cur.right = node
break
}
cur = cur.right // 继续往右侧找
}
}
}
// 查找节点
find(val) {
let cur = this.root
while (cur) {
if (val === cur.val) {
return cur
} else if (val < cur.val) {
cur = cur.left
} else if (val > cur.val) {
cur = cur.right
}
}
return null
}
// 查找节点，递归实现
find2(val, node) {
if (!node) {
return null
}
if (val === node.val) {
return node
} else if (val < node.val) {
return this.find2(val, node.left)
} else if (val > node.val) {
return this.find2(val, node.right)
}
}
// 删除节点
// 3种情况
// 第1种：待删除节点为叶子节点，只需把父节点指向该节点的链指向null
// 第2种：待删除节点左节点或右节点为null，只需把父节点指向该节点的链指向剩下的左子树或右子树
// 第3种：待删除节点的左右节点都存在
// (1)找到待删除节点 左子树的最大值节点 或 右子树的最小值节点；以右子树最小值节点为例
// (2)将最小值节点的val赋值给当前节点
// (3)然后删除最小值节点(采用递归)
// (4)删除最小值节点后，右子树根节点可能发生变化，当前节点应重新连接新的右子树根节点
remove(node, val) {
if (!node) {
return null
}
// 先寻找待删除节点
if (val < node.val) {
node.left = this.remove(node.left, val)
return node
} else if (val > node.val) {
node.right = this.remove(node.right, val)
return node
} else if (val === node.val) { // 找到待删除的节点了
// 如果是叶子节点
if (node.left === null && node.right === null) {
return null
} else if (node.right === null) { // 只含左节点
return node.left
} else if (node.left === null) { // 只含右节点
return node.right
} else if (node.left !== null && node.right !== null) { // 含两个子节点
// 找到右子树的最小值
let tempNode = this.getMin(node.right)
// 将最小值节点
node.val = tempNode.val
// 然后删除这个最小值节点
node.right = this.remove(node.right, tempNode.val)
return node
}
}
}
// 前序遍历,中左右
preOrder(node) {
if (node) {
node.print() // 中
this.preOrder(node.left) // 左
this.preOrder(node.right) // 右
}
}
// 中序遍历，左中右
inOrder(node) {
if (node) {
this.inOrder(node.left) // 左
node.print() // 中
this.inOrder(node.right) // 右
}
}
// 后序遍历，左右中
postOrder(node) {
if (node) {
this.postOrder(node.left) // 左
this.postOrder(node.right) // 右
node.print() // 中
}
}
// 广度优先遍历，利用队列实现
levelOrder() {
if (!this.root) {
return
}
let queue = []
let res = []
queue.push(this.root)
while (queue.length) {
// 从队列头取出节点
let node = queue.shift()
res.push(node.val)
// 从队尾插入子节点
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
return res
}
levelOrder2() {
let queue = []
let res = []
queue.push(this.root)
while (queue.length) {
let len = queue.length // 当前层的节点数
// 循环把当前层的节点拿出来，再把左节点和右节点插入队列
for (let i = 0; i < len; i++) {
let node = queue.shift()
res.push(node.val)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
}
return res
}
// 获取最小值,在左子树最后一层最左边的节点
getMin(node) {
node = node || this.root
let curr = node
while (curr.left !== null) {
curr = curr.left
}
return curr
}
// 用递归实现
getMin2(node) {
node = node || this.root
if (node.left === null) {
return node
} else {
return this.getMin2(node.left)
}
}
// 获取最大值，在右子树最后一层最右边的节点
getMax(node) {
node = node || this.root
let curr = node
while (curr) {
if (curr.right === null) {
return curr
}
curr = curr.right
}
}
// 树的深度
getDeep(node, deep) {
deep = deep || 0
if (node === null) {
return deep
}
deep++
let leftDeep = this.getDeep(node.left, deep) // 左子树深度
let rightDeep = this.getDeep(node.right, deep) // 右子树深度
return Math.max(leftDeep, rightDeep)
}
// 非递归
getDeep2() {
let queue = []
let count = 0
queue.push(this.root)
while (queue.length) {
let len = queue.length // 当前层的节点数
for (let i = 0; i < len; i++) {
let node = queue.shift()
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
count++
}
return count
}
}
const tree = new BinarySearchTree()
tree.insert(3)
tree.insert(8)
tree.insert(1)
tree.insert(2)
tree.insert(5)
tree.insert(7)
tree.insert(6)
tree.insert(0)
// console.log(tree);
// tree.inOrder(tree.root) //0 1 2 3 5 6 7 8
// tree.preOrder(tree.root) //3 1 0 2 8 5 7 6
// tree.postOrder(tree.root) //0 2 1 6 7 5 8 3
// console.log(tree.getMin())
// console.log(tree.getMax())
// console.log(tree.getDeep(tree.root))
// console.log(tree.find(5))
tree.remove(tree.root, 5)
console.log(tree.find(8))