C / C++ / 系统课时
向二叉搜索树插入节点
向二叉搜索树插入节点
向二叉搜索树插入节点的关键,不是“把新节点挂上去”,而是沿比较结果持续寻找唯一合适的空位置。只要每一步都保持左子树较小、右子树较大的规则,插入完成后整棵树仍然有序,可继续支持高效查找。
学习目标
- 理解二叉搜索树插入位置如何由比较结果确定
- 能用 C 语言递归实现节点插入并正确连接返回的新子树
- 知道重复键策略和树高对插入效率的影响
插入位置是怎样找到的
假设二叉搜索树规定:任意节点左子树中的键都小于该节点,右子树中的键都大于该节点。插入值 65 时,从根节点开始比较:小于当前节点就进入左子树,大于当前节点就进入右子树,直到遇到空指针。
空指针所在的位置就是新节点应该连接的位置。这个过程本质上与查找相同,只是查找在空位置结束,而插入会在这里创建并返回一个新节点。

用递归完成插入
递归写法可以直接把“当前子树插入后的根节点”作为函数返回值。这样无论新节点出现在整棵树的根位置,还是某个节点的左、右子树,调用者都能把返回结果重新连接回去。
下面示例选择“重复键不插入”的策略,因此等于当前节点时直接返回原节点。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node *left;
struct Node *right;
} Node;
Node *createNode(int key) {
Node *node = malloc(sizeof(Node));
if (node == NULL) {
fprintf(stderr, "memory allocation failed\n");
exit(EXIT_FAILURE);
}
node->key = key;
node->left = NULL;
node->right = NULL;
return node;
}
Node *insert(Node *root, int key) {
if (root == NULL) {
return createNode(key);
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
}
return root;
}
void inorder(const Node *root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
void freeTree(Node *root) {
if (root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main(void) {
int values[] = {50, 30, 70, 20, 40, 60, 80, 65};
size_t count = sizeof(values) / sizeof(values[0]);
Node *root = NULL;
for (size_t i = 0; i < count; ++i) {
root = insert(root, values[i]);
}
inorder(root);
printf("\n");
freeTree(root);
return 0;
}预期输出:
20 30 40 50 60 65 70 80中序遍历结果严格递增,说明插入后仍满足二叉搜索树的有序性质。root = insert(root, value) 这一写法不能省略,因为第一次插入时原来的 root 是 NULL,函数返回的新节点就是新的根。
为什么必须重新连接返回值
递归进入 root->left 或 root->right 后,最深层调用可能创建一个新节点。上层调用必须把这个返回值赋回对应的子指针,否则新节点虽然申请了内存,却不会真正接入树中。
因此,正确写法是 root->left = insert(root->left, key) 或 root->right = insert(root->right, key),而不是只调用 insert(root->left, key) 后丢弃返回值。
重复键和性能边界
二叉搜索树必须提前决定重复键策略。常见做法包括拒绝重复值、把重复次数记录在节点中,或约定重复值始终进入某一侧。无论采用哪一种,都要在查找、删除和插入中保持一致。
单次插入需要沿树高走一条路径,因此时间复杂度为 ,其中 是树高。树较均衡时接近 ;如果按已经有序的数据持续插入,普通二叉搜索树可能退化成单链表,最坏变为 。递归实现的调用栈空间同样为 。