C 语言链表与二叉树
更新时间：2026-08-26。本文是
languages/c/主题高手层的骨架文档（占位），完整展开将在后续批次补齐。
本文要回答的问题
- 单链表、双链表、循环链表怎么选？
- 二叉树的前/中/后序、层序遍历怎么实现？递归什么时候该换成迭代？
- 链表明明"插入快"，为什么实际性能经常不如数组？
一、链表家族对比
| 类型 | 结构 | 优点 | 代价 |
|---|---|---|---|
| 单链表 | 每个节点一个 next | 实现最简单、省内存 | 只能向后遍历 |
| 双链表 | prev + next | 双向遍历、删节点 O(1) | 多一个指针开销 |
| 循环链表 | 尾接回头 | 环形处理（轮询、约瑟夫） | 注意死循环边界 |
二、二叉树与遍历
c
typedef struct Node { int val; struct Node *l, *r; } Node;- 前序：根→左→右（拷贝树、表达式前缀）。
- 中序：左→根→右（二叉搜索树得到有序序列）。
- 后序：左→右→根（释放整棵树，先放子树再放根）。
- 层序：队列实现，逐层访问。
递归 vs 迭代：递归简洁但吃栈（深度大可能栈溢出）；迭代用显式栈/队列，可控但啰嗦。深度 > 几千时优先迭代。
三、链表的性能真相
链表节点分散在堆上，地址不连续，遍历时缓存命中差；数组连续存储、顺序访问极快。所以"插入 O(1)"的红利常被"遍历缓存 miss"抵消——数据规模小、读多写少时，数组几乎总是更快。这正好衔接本站 缓存与局部性 与 伪共享实验。
四、与入门层的衔接
一句话总结
链表赢在插入删除、输在缓存局部性，二叉树赢在有序查找、输在递归深度：选数据结构先想清楚你的访问模式，别被"复杂度表"骗了。
本文为骨架文档：核心结构已就位，示例代码与实测数据将在后续批次补齐。