二叉搜索树(Binary Search Tree),是一种具有以下性质的二叉树:
- 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值
- 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值
- 任意节点的左、右子树也分别为二叉搜索树
节点的结构如下,以力扣为标准
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val == undefined ? 0 : val)
this.left = (left == undefined ? null : left)
this.right = (right == undefined ? null : right)
}
}
查找
二叉搜索树的中序遍历单调递增,中序遍历
插入
const insertIntoBST = (root: TreeNode | null, val: number): TreeNode | null => {
if (root == null) return new TreeNode(val)
if (val < root.val) {
root.left = insertIntoBST(root.left, val)
} else if (val > root.val) {
root.right = insertIntoBST(root.right, val)
}
return root
}
删除
const deleteNode = (root: TreeNode | null, key: number): TreeNode | null => {
if (root == null) return root
if (root.val == key) {
if (root.right == null) return root.left
else {
let node = root.right
while (node.left != null) node = node.left
node.left = root.left
return root.right
}
}
if (root.val < key) root.right = deleteNode(root.right, key)
else root.left = deleteNode(root.left, key)
return root
}