C语言算法进阶路：从“队列分层”到“二级指针”的顿悟时刻

前言

今天是我在数据结构学习中跨度最大的一天。从最基础的层序遍历（BFS），一路杀到了二叉搜索树（BST）最复杂的删除操作。

这中间并非一帆风顺，我掉进过指针的坑，搞反过递归的方向，甚至在理解二级指针时几乎“CPU过载”。但正是这些痛点，让我真正触摸到了 C 语言与数据结构的灵魂。

本文将忠实记录我的代码实现、复杂度分析，以及那些困扰我许久但在今天终于顿悟的核心痛点。

---

第一章：层序遍历 (BFS) —— 迭代版与递归版的较量

1. 标准解法：迭代版 (Iterative Queue)

这是最经典、最常用的层序遍历方式。利用队列“先进先出”的特性。

🚨 我的痛点：如何分层？

同一个队列里既有这一层的节点，又有下一层的孩子，怎么把它们分开？

💡 顿悟：快照机制

不需要开两个队列。在每一层处理前，计算 tail - head，锁定这一层的节点数量。

代码实现：

C

void LevelOrder_Iterative(BTNode* root) {
    if (!root) return;
    BTNode* queue[1000]; // 指针数组模拟队列
    int head = 0, tail = 0;
    queue[tail++] = root; 

    int level = 1;
    while (head != tail) {
        // 【核心】：快照机制。锁定当前层的节点数量。
        int levelSize = tail - head; 
        printf("第 %d 层: ", level);

        for (int i = 0; i < levelSize; i++) {
            BTNode* cur = queue[head++]; // 出队
            printf("%d ", cur->val);
            
            // 孩子入队
            if (cur->left) queue[tail++] = cur->left;
            if (cur->right) queue[tail++] = cur->right;
        }
        printf("\n");
        level++;
    }
}

📊 复杂度分析：

时间复杂度：$O(N)$。每个节点进出队列各一次。

空间复杂度：$O(W)$。$W$ 为树的最大宽度。最坏情况下（满二叉树），队列要存下一整层的节点。

---

2. 另类解法：递归版 (Recursive DFS)

利用 DFS + depth 参数，虽然遍历顺序是先深后广，但通过索引可以把数据归位到对应的层级。

代码实现：

C

// results[depth][index] 存储数据
void DFS_LevelOrder(BTNode* root, int depth) {
    if (!root) return;
    
    // 把当前节点放入对应深度的数组中
    // results[depth][colSizes[depth]++] = root->val;

    DFS_LevelOrder(root->left, depth + 1);
    DFS_LevelOrder(root->right, depth + 1);
}

📊 复杂度分析：

时间复杂度：$O(N)$。

空间复杂度：$O(H)$。$H$ 为树的高度。递归栈只保存一条路径上的节点。

对比结论：

瘦高的树：递归版省空间（高度小，宽度小）。

矮胖的树：迭代版费空间（宽度大），递归版省空间（高度小）。

---

第二章：完全二叉树判定 —— 别把 NULL 当垃圾

🚨 我的痛点：

我习惯性地只把非空节点入队 (if left != NULL push)，结果无法发现树中间的空洞。

💡 顿悟：红绿灯模型

NULL 也是重要的数据！必须无脑入队。

一旦弹出 NULL，亮起红灯（标记 hasSeenNull = true）。

如果在红灯亮起后，还能弹出非空节点，说明树断层了，不是完全二叉树。

代码片段：

C

if (current == NULL) {
    hasSeenNull = true; // 亮红灯
} else {
    if (hasSeenNull) return false; // 红灯后发现活人，报错
    queue[tail++] = current->left; // 无脑入队
    queue[tail++] = current->right;
}

---

第三章：二叉搜索树 (BST) —— 秩序之美

1. 查找 (Search)

逻辑： 左 < 根 < 右。

代码 (递归版)：

C

BTNode* BST_Search(BTNode* root, int val) {
    if (!root || root->val == val) return root;
    if (val < root->val) return BST_Search(root->left, val);
    else return BST_Search(root->right, val);
}

复杂度分析 (面试必问)：

时间复杂度：最好/平均情况（平衡树）是 $O(\log N)$，就像猜数字游戏，每次比较都能排除一半的可能性；最坏情况（退化成链表）是 $O(N)$，这种情况下只能像链表一样逐个尝试。

空间复杂度（递归）：最好/平均情况是 $O(\log N)$，最坏情况是 $O(N)$；这是因为递归不仅看节点数量，更看树的深度，树越深，系统栈中“等待结果”的栈帧就越多。

二叉搜索树查找 (迭代版)

BTNode* BST_Search(BTNode* root, int val) {
    // 只要还没有走到死胡同 (root != NULL)
    while (root != NULL) {
        
        // 1. 运气好，直接找到了
        if (root->val == val) {
            return root;
        }
        
        // 2. 目标值比当前节点大 -> 往右走
        else if (val > root->val) {
            root = root->right;
        }
        
        // 3. 目标值比当前节点小 -> 往左走
        else { // val < root->val
            root = root->left;
        }
    }

    // 走到最后也没找到 (root 变成了 NULL)
    return NULL;
}

复杂度分析 (面试必问)：

时间复杂度：最好/平均情况（平衡树）是 $O(\log N)$，就像猜数字游戏，每次比较都能排除一半的可能性；最坏情况（退化成链表）是 $O(N)$，这种情况下只能像链表一样逐个尝试。

空间复杂度（迭代）：始终是 $O(1)$；这是因为迭代法不需要使用系统递归栈，无论树有多深，只需要几个指针变量就能搞定。

---

第四章：BST 插入 —— 翻越“二级指针”的大山

这是今天最深刻的顿悟时刻。我明白了为什么修改根节点需要传 BTNode**。

🚨 我的痛点：二级指针的困惑

*root 指向节点，那 **root 到底是什么？为什么要修改节点的地址？

💡 深度比喻：抽屉原理

房间 (Entity)：内存 0x5A00，真实的节点。

钥匙 (Level 1 Pointer)：BTNode* root。它是一把写着 0x5A00 的钥匙。

抽屉 (Variable)：main 函数里的变量 root。它是存放钥匙的地方。

寻宝图 (Level 2 Pointer)：BTNode** ptr。它写着抽屉的地址（0x9999）。

场景：抽屉是空的（空树 NULL），我要造一把新钥匙放进去。

❌ 传一级指针 = 拍了一张空抽屉的照片给函数。函数在照片上放了钥匙。原抽屉没变。

✅ 传二级指针 = 给函数一张寻宝图。函数找到抽屉，拉开，把新钥匙放进去。成功！

代码实现 A：迭代版 (需二级指针)

C

int BST_Insert_Iterative(BTNode** root_ptr, int val) {
    if (*root_ptr == NULL) {
        *root_ptr = BuyNode(val); // 修改抽屉里的钥匙
        return 1;
    }
    // ... 后续逻辑需要维护 parent 指针 ...
}

代码实现 B：递归版 (推荐，避开二级指针)

利用 return root 机制，自动链接。

C

BTNode* BST_Insert_Recursive(BTNode* root, int val) {
    if (root == NULL) return BuyNode(val); // 返回新节点
    
    if (val < root->val) 
        root->left = BST_Insert_Recursive(root->left, val); //以此接住返回值
    else 
        root->right = BST_Insert_Recursive(root->right, val);
        
    return root;
}

---

第五章：BST 删除 —— 狸猫换太子的艺术

🚨 我的痛点

删除拥有两个孩子的节点（如根50，左30，右70）。若直接删除，左右子树会断裂，难以重组。

💡 解决方案：继承人策略

“只换灵魂，不换肉体”

1. 找继承人：去右子树找最小的节点（后继节点）。因为它能大于左边所有，小于右边所有。
2. 篡位：把继承人的值赋给当前节点。
3. 灭口：递归删除那个继承人（因为它肯定是叶子或只有右孩子，很容易删）。

代码实现：

C

BTNode* BST_Delete(BTNode* root, int val) {
    if (!root) return NULL;
    // 1. 查找
    if (val < root->val) {
        root->left = BST_Delete(root->left, val);
        return root;
    }
    else if (val > root->val) {
        root->right = BST_Delete(root->right, val);
        return root;
    }
    
    // 2. 找到了！
    // 情况 A/B: 独苗或叶子
    if (!root->left) {
        BTNode* temp = root->right;
        free(root); return temp;
    }
    else if (!root->right) {
        BTNode* temp = root->left;
        free(root); return temp;
    }
    
    // 情况 C: 左右双全
    else {
        // 找继承人 (右子树最小)
        BTNode* minNode = root->right;
        while (minNode->left) minNode = minNode->left;
        
        // 狸猫换太子 (只换值)
        root->val = minNode->val;
        
        // 借刀杀人 (删掉那个多余的继承人)
        root->right = BST_Delete(root->right, minNode->val);
    }
    return root;
}

---

总结

今天的学习让我明白，算法不仅仅是背代码，更是对内存模型和逻辑闭环的深刻理解。

队列 教会了我如何控制时序（分层快照）。

指针 教会了我如何精准操作内存（抽屉与钥匙）。

BST 教会了我如何利用规则“借刀杀人”（删除策略）。

从被指针绕晕，到能画出内存图；从恐惧递归，到能写出优雅的删除逻辑。这就是算法进阶的乐趣所在！