二叉搜索树结构与操作详解
二叉搜索树（Binary Search Tree，BST）是一种基于节点层级关系的数据结构，其核心特性在于节点值的有序性。每个节点的左子树所有节点值均小于当前节点值，右子树所有节点值均大于当前节点值。这种特性使得中序遍历结果呈现严格递增序列。
构建基础
为实现稳定操作，通常在树结构中预置最小值和最大值占位节点。通过动态分配节点的方式构建初始结构，例如：
const int MAX_SIZE = 10000;
struct Node {
int left;
int right;
int value;
} nodes[MAX_SIZE];
int nodeCount = 0;
int root = 0;
int createNode(int val) {
nodes[++nodeCount].value = val;
return nodeCount;
}
void initialize() {
root = createNode(INT_MIN);
nodes[root].right = createNode(INT_MAX);
}
查找实现
基于BST特性设计的查找算法，通过比较当前节点值与目标值决定搜索方向。迭代版本实现如下：
int search(int target) {
int current = root;
while (current != 0) {
int currentValue = nodes[current].value;
if (currentValue == target) break;
current = (currentValue > target) ? nodes[current].left : nodes[current].right;
}
return current;
}
插入逻辑
插入操作遵循相似的比较规则，当到达空节点时创建新节点。递归实现示例：
void insert(int& current, int value) {
if (current == 0) {
current = createNode(value);
return;
}
int currentValue = nodes[current].value;
if (value < currentValue) {
insert(nodes[current].left, value);
} else {
insert(nodes[current].right, value);
}
}
极值获取
最值查找可直接通过单向遍历实现：
int findMin(int start) {
while (nodes[start].left != 0) {
start = nodes[start].left;
}
return start;
}
int findMax(int start) {
while (nodes[start].right != 0) {
start = nodes[start].right;
}
return start;
}
前驱后继计算
前驱节点为中序遍历的直接前驱，后继节点为直接后继。实现方式：
int getPredecessor(int node) {
if (nodes[node].left == 0) return 0;
return findMax(nodes[node].left);
}
int getSuccessor(int node) {
if (nodes[node].right == 0) return 0;
return findMin(nodes[node].right);
}
删除操作
删除包含三种情况处理：无子节点、单子节点、双子节点。双子节点场景采用替代法：
void remove(int& current, int value) {
if (current == 0) return;
int currentValue = nodes[current].value;
if (value < currentValue) {
remove(nodes[current].left, value);
} else if (value > currentValue) {
remove(nodes[current].right, value);
} else {
// 处理子节点情况
if (nodes[current].left == 0) {
current = nodes[current].right;
} else if (nodes[current].right == 0) {
current = nodes[current].left;
} else {
// 替代法处理双子节点
int successor = findMin(nodes[current].right);
nodes[current].value = nodes[successor].value;
remove(nodes[current].right, nodes[successor].value);
}
}
}
注意：BST操作的平均时间复杂度为O(log n)，最坏情况（退化为链表）可达O(n)。实际应用中常采用平衡二叉树结构（如AVL树、红黑树）优化性能。
