什么是二叉搜索树？
二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树数据结构。在二叉搜索树中，每个节点都有一个键值，并且每个节点的左子树中的所有键值都小于该节点的键值，而右子树中的所有键值都大于该节点的键值。
这种特性使得二叉搜索树非常适合用来实现动态查找、插入和删除操作。在实际应用中，二叉搜索树经常用于数据库索引、符号表和缓存系统等场景。
BST 的基本操作
插入节点
在二叉搜索树中插入一个新节点时，需要根据节点的键值来决定插入的位置。具体步骤如下：
- 如果当前树为空，则新节点将成为根节点。
- 如果当前树不为空，则将新节点与当前节点进行比较：
- 如果新节点的键值小于当前节点的键值，则向当前节点的左子树递归地插入新节点。
- 如果新节点的键值大于当前节点的键值，则向当前节点的右子树递归地插入新节点。
// www.javascriptcn.com code example
function insertNode(root, key) {
if (!root) {
return {key};
}
if (key < root.key) {
root.left = insertNode(root.left, key);
} else if (key > root.key) {
root.right = insertNode(root.right, key);
}
return root;
}查找节点
查找二叉搜索树中的一个节点，只需要从根节点开始，根据键值的大小关系来决定向左子树还是右子树继续查找。
// www.javascriptcn.com code example
function searchNode(root, key) {
if (!root || root.key === key) {
return root;
}
if (key < root.key) {
return searchNode(root.left, key);
} else {
return searchNode(root.right, key);
}
}删除节点
删除二叉搜索树中的一个节点需要考虑三种情况：
- 要删除的节点是叶子节点：直接删除即可。
- 要删除的节点有一个子节点：用子节点替换要删除的节点。
- 要删除的节点有两个子节点：找到右子树中的最小节点或左子树中的最大节点，用它的值替换要删除的节点的值，然后删除这个最小或最大节点。
// www.javascriptcn.com code example
function minValueNode(node) {
let current = node;
while (current && current.left !== null) {
current = current.left;
}
return current;
}
function deleteNode(root, key) {
if (!root) return root;
if (key < root.key) {
root.left = deleteNode(root.left, key);
} else if (key > root.key) {
root.right = deleteNode(root.right, key);
} else {
if (!root.left) {
return root.right;
} else if (!root.right) {
return root.left;
}
root.key = minValueNode(root.right).key;
root.right = deleteNode(root.right, root.key);
}
return root;
}BST 的遍历方法
中序遍历
中序遍历是一种深度优先遍历方法，按照左-根-右的顺序访问每个节点。中序遍历可以得到一个从小到大的有序序列。
// www.javascriptcn.com code example
function inOrderTraversal(root) {
const result = [];
function traverse(node) {
if (node) {
traverse(node.left);
result.push(node.key);
traverse(node.right);
}
}
traverse(root);
return result;
}前序遍历
前序遍历也是一种深度优先遍历方法，按照根-左-右的顺序访问每个节点。前序遍历常用于复制一棵树。
// www.javascriptcn.com code example
function preOrderTraversal(root) {
const result = [];
function traverse(node) {
if (node) {
result.push(node.key);
traverse(node.left);
traverse(node.right);
}
}
traverse(root);
return result;
}后序遍历
后序遍历同样是一种深度优先遍历方法，按照左-右-根的顺序访问每个节点。后序遍历常用于计算二叉树的高度。
// www.javascriptcn.com code example
function postOrderTraversal(root) {
const result = [];
function traverse(node) {
if (node) {
traverse(node.left);
traverse(node.right);
result.push(node.key);
}
}
traverse(root);
return result;
}总结
二叉搜索树是一种非常实用的数据结构，它支持高效的查找、插入和删除操作。通过不同的遍历方法，我们还可以获得不同类型的节点访问顺序。在实际编程中，了解并掌握这些操作对于实现高效的数据管理非常重要。