C Academy · 课时

向 BST 中插入

Q: 「向 BST 中插入」这节课中我会学到什么？

构建二叉搜索树。 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

构建二叉搜索树。

向 BST 中插入 是 CoddyKit 上的免费 C Academy 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

BST 排序规则

二叉搜索树（BST）是一种二叉树，它还遵循一条额外规则：对于每个节点，其左子树中的所有值都更小，右子树中的所有值都更大。

正是这种排序关系，使我们能够在与树高成正比的时间内进行搜索、插入和删除。

值应放在哪里

要插入值，我们从根节点开始进行比较。如果新值更小，就向左走；如果更大，就向右走。

我们不断重复，直到找到一个空位置（NULL）；这正是新节点应放置的位置。

/* insert 7 into:
 *        10
 *       /  \
 *      5    15
 * 7 < 10 -> left;  7 > 5 -> right of 5
 */

create_node 辅助函数

插入操作会创建新的叶节点，因此我们可以复用一个负责分配和初始化节点的构造函数。

两个子节点指针都从 NULL 开始，因为刚插入的节点总是叶节点。

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) return NULL;
    n->value = value;
    n->left = n->right = NULL;
    return n;
}

递归插入

最简洁的插入方式是使用递归，并返回（可能已经改变的）子树根节点。

如果子树为空，我们就返回一个新节点。否则，递归处理左侧或右侧，重新连接返回结果，然后返回未改变的根节点。

Node *insert(Node *root, int value) {
    if (root == NULL)
        return create_node(value);
    if (value < root->value)
        root->left = insert(root->left, value);
    else if (value > root->value)
        root->right = insert(root->right, value);
    return root;  /* equal: ignore duplicate */
}

为何要返回根节点

返回子树根节点后，父节点就能用一行代码重新连接指针：root->left = insert(root->left, v)。

如果子树为空，返回的新节点就会成为子节点；如果子树不为空，则返回同一个根节点，连接关系保持不变。

/* The assignment does double duty:
 * - empty case: stores the new node
 * - non-empty:  stores the same pointer back (no-op)
 */
root->left = insert(root->left, value);

处理重复值

实际的 BST 必须决定如何处理相等的值。一种常见选择是忽略重复值，我们的 insert 就采用了这种方式，因为相等时没有对应的分支。

其他选择包括为每个节点保存一个计数，或者始终将重复值放到同一侧。

if (value < root->value)
    root->left = insert(root->left, value);
else if (value > root->value)
    root->right = insert(root->right, value);
/* value == root->value -> do nothing */

构建 BST

按顺序插入一组值后，树的结构取决于插入顺序。

这里我们插入几个数字，并打印根节点的直接子节点，以确认排序规则仍然成立。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *create_node(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return create_node(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}

int main(void){
    Node *root = NULL;
    int data[] = {10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,data[i]);
    printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
    return 0;
}

迭代插入

您也可以不使用递归来插入。我们使用指针向下遍历，同时记住父节点，直到找到一个空位置。

然后，将新节点连接到该父节点正确的一侧。

void insert_iter(Node **rootp, int value) {
    Node *cur = *rootp, *parent = NULL;
    while (cur) {
        parent = cur;
        cur = (value < cur->value) ? cur->left : cur->right;
    }
    Node *n = create_node(value);
    if (!parent) *rootp = n;
    else if (value < parent->value) parent->left = n;
    else parent->right = n;
}

插入顺序决定树的形状

按排序顺序插入 1、2、3、4、5，会形成一棵退化树，看起来像链表，其高度等于节点数量。

按平衡顺序插入可以使高度接近 log(n)。平衡程度会直接影响搜索速度。

/* sorted insert 1..5 ->
 * 1
 *  \
 *   2
 *    \
 *     3   (height = 4, like a list)
 */

插入的代价

每次插入都会沿着从根节点到叶节点的一条路径行进，因此所执行的工作量与树的高度成正比。

对于平衡树，大约需要进行 log(n) 次比较；对于退化树，可能需要 n 次。这正是自平衡树存在的原因。

完整插入演示

此程序插入一些值，然后统计节点数量，以确认其中存储了五个不同的值，并且忽略了一个重复值。

重复值 10 不会增加计数，因为 insert 会舍弃相等的值。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,10,20};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("count=%d\n", count(root));
    return 0;
}

快速检查

思考插入行为。

回顾

BST 插入会将新值与每个节点进行比较：较小时向左走，较大时向右走，直到找到一个空位置。

递归形式会返回子树根节点，这样父节点就能简洁地重新连接链接。插入开销取决于树的高度，因此插入顺序很重要。

常见问题解答

「向 BST 中插入」课时是免费的吗？

是的 — 「向 BST 中插入」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「向 BST 中插入」这节课中我会学到什么？

构建二叉搜索树。你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 2 节课，共 4 节。

「向 BST 中插入」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy