C / C++ / 系统课时

向二叉搜索树插入节点

向二叉搜索树插入节点

向二叉搜索树插入节点的关键,不是“把新节点挂上去”,而是沿比较结果持续寻找唯一合适的空位置。只要每一步都保持左子树较小、右子树较大的规则,插入完成后整棵树仍然有序,可继续支持高效查找。

学习目标

  • 理解二叉搜索树插入位置如何由比较结果确定
  • 能用 C 语言递归实现节点插入并正确连接返回的新子树
  • 知道重复键策略和树高对插入效率的影响

插入位置是怎样找到的

假设二叉搜索树规定:任意节点左子树中的键都小于该节点,右子树中的键都大于该节点。插入值 65 时,从根节点开始比较:小于当前节点就进入左子树,大于当前节点就进入右子树,直到遇到空指针。

空指针所在的位置就是新节点应该连接的位置。这个过程本质上与查找相同,只是查找在空位置结束,而插入会在这里创建并返回一个新节点。

二叉搜索树插入路径与连接位置

用递归完成插入

递归写法可以直接把“当前子树插入后的根节点”作为函数返回值。这样无论新节点出现在整棵树的根位置,还是某个节点的左、右子树,调用者都能把返回结果重新连接回去。

下面示例选择“重复键不插入”的策略,因此等于当前节点时直接返回原节点。

c
#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;
}

预期输出:

text
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) 后丢弃返回值。

重复键和性能边界

二叉搜索树必须提前决定重复键策略。常见做法包括拒绝重复值、把重复次数记录在节点中,或约定重复值始终进入某一侧。无论采用哪一种,都要在查找、删除和插入中保持一致。

单次插入需要沿树高走一条路径,因此时间复杂度为 O(h)O(h),其中 hh 是树高。树较均衡时接近 O(log⁡n)O(\log n);如果按已经有序的数据持续插入,普通二叉搜索树可能退化成单链表,最坏变为 O(n)O(n)。递归实现的调用栈空间同样为 O(h)O(h)。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

向二叉搜索树插入节点

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通