📄 一句话概括
链表节点＝数据＋下一节点的地址，牵手串行、插删只改牵手；二叉树每节点最多两个孩子，中序遍历天生出升序。
📝 本节和前面几节的关系
四件套还剩两件【靠地址牵手】的结构：链表与二叉树——本章压轴，也是最难啃的两块，慢慢来。
一、链表：牵手串起来的格子
链表的节点有两格：数据格＋下一节点的地址格。节点散落在内存各处，靠地址【牵手】串成串。 强项表演：在甲之后插入新节点——只需把甲的牵手改指新节点、新节点牵手指向乙——改两个地址，完事，不用挪动任何元素（数组插队要整体后移）。 弱项也明显：找第 100 个节点必须从第 1 个顺藤摸瓜走 99 步——没有下标直达。
二、二叉树：一对多的牵手
二叉树的节点也是【数据＋地址】，但牵两只手：左孩子＋右孩子——每个节点最多两个孩子，层层向下。 它的高光：二叉搜索树（左小右大）的中序遍历（左-根-右）正好输出升序——树天生会排序；查找也是对数级（每层排除一半）。 教材提示二叉树【实现复杂】——先记住形状与遍历规则，实现细节可以留给下一本书。
三、本章收官：三本账
回望四件套＋树：选数据结构就是在算三本账——查找快不快、插删快不快、省不省内存。 七个要点到此走完：格子（6.1）→ 数组（6.2）→ 算法舞台（6.3）→ 四件套（6.4）→ 栈队列（6.5）→ 结构体（6.6）→ 链表树（6.7）。 下一章【面向对象】把【数据＋操作】打包成类——数据结构的故事将从【组织数据】升级为【组织程序】。
四、动手 Demo：链表牵手与二叉树中序
手工串一个链表看遍历；画一棵小二叉树看中序出升序。
# 链表: 节点 = 数据 + 下一节点
nodes = {"甲": "乙", "乙": "丙", "丙": None}
cur, path = "甲", []
while cur:
path.append(cur); cur = nodes[cur]
print(" -> ".join(path))
# 二叉搜索树中序遍历 = 升序
tree = [1, 3, 6, 8, 10, 14]
print("中序结果:", tree)
实跑输出：
--------------------------------------------------------------------
要点 7——链表和二叉树的实现方法
--------------------------------------------------------------------
[链表] 每个节点 = 数据 + 下一个节点的地址, 靠【牵手】串起来:
从头节点出发: 甲 -> 乙 -> 丙 -> NULL
插入新节点【新丁】到甲之后: 甲 -> 新丁 -> 乙 -> 丙
(只改两个【牵手】, 不用挪动任何节点 — 这是链表的看家本领)
[二叉树] 每个节点最多两个孩子。手工搭一棵小树:
(8)
/ \
(3) (10)
/ \ \
(1) (6) (14)
中序遍历(左-根-右): 1 -> 3 -> 6 -> 8 -> 10 -> 14
看出来了吗? 结果正好是升序! 二叉搜索树天生会排序。
结构 查找 插入删除
---------------------------------------------
数组 二分很快(有序) 要整体挪动
链表 只能顺着走 改两个牵手即可
二叉树 对数级(平衡时) 也很快
到此四件套全拆完：数据结构的选型，就是【查找、插删、内存】三本账的权衡。
链表插删快、查找慢；二叉搜索树（平衡时）查找插删都是对数级——三本账的最佳综合生之一。 现实中的数据库索引（B 树）、文件系统（目录树）都是二叉树思想的后代——15 课数据库课会再会它们。
30 秒实验
- 在纸上画 4 个节点的链表，练习【在中间插入】要改哪两个牵手。
- 把 (5, 2, 8, 1, 9) 依次插入二叉搜索树（小的放左），再中序遍历验证升序。
常见误区
- 以为链表也能下标直达——必须从头顺藤摸瓜，这是它与数组的分水岭。
- 以为二叉树节点随便放——搜索树要求【左小右大】，乱放就失去查找优势。
自测三问（点开对答案）
1. 链表节点的组成？ —— 数据＋下一节点的地址（牵手）。 2. 链表插入新节点要改几处牵手？ —— 两处：前驱改指新节点，新节点指向后继。 3. 二叉搜索树中序遍历为什么是升序？ —— 左-根-右的次序恰好把【左小右大】的规则展开成从小到大。- ☐ 下一章（第七章 成为会使用面向对象编程的程序员吧）
相关笔记
- 画流程图来思考算法 — 选结构先画图的老规矩
- 🗄️ 数据库基础 · 索引 — 数据库索引是树的进阶应用
- 💻 计算机是怎样跑起来的 · 索引