树
复习
- 单向链表：节点用指针相连
- 递归：函数调用自身来解决问题
- 集合与映射：建立在哈希表之上的抽象
TL;DR
- 树用父子关系表示层次结构
- 每个节点最多有一个父节点，根没有父节点
- 树天然适合用递归来处理
- 层次结构在现实中随处可见
正文
前面那些结构都是“一条线”：数组是一排，链表是一串，队列是一队。可现实里很多数据是有层次的：文件夹套文件夹、公司里有上下级、网页里有嵌套标签。要表示这种层次，就需要树（tree）。
上下级关系
树由一个个节点（node）组成，节点之间有“父子”关系：
- 根（root）：最顶层那个节点，没有父节点
- 父节点 / 子节点：一个节点可以有多个子节点，但只有一个父节点
- 叶子（leaf）：没有子节点的节点
从根出发到某个节点，经过的层数，叫它的深度；从某个节点往下到最远叶子的层数，叫它的高度。整棵树只有一个根，不会绕回来（没有环）。
想想你的文件系统：根目录下有若干目录，每个目录里又有子目录和文件——这正是一棵树。
为什么树适合递归
树有一个很关键的性质：去掉根之后，剩下的每一棵子树，本身又是一棵树。
这种“自己包含更小的自己”的结构，和递归简直是天生一对。处理一棵树，往往可以写成：
- 先处理根
- 再分别递归地处理每一棵子树
后面要讲的遍历、查找，几乎都会用到这个套路。结构是递归的，解法自然也是递归的。
和链表的区别
值得对比一下：链表的每个节点，只有一个“后继”；而树的节点可以有好几个“后继”（子节点）。正是“一个变多个”，让树能表达层次，而不是一条直线。
最常用、也最容易处理的一种树，是每个节点最多两个孩子的树——二叉树。下一章就从它开始。
思考题 1
树和链表在“连接方式”上有什么不同？
思考题 2
为什么树特别适合用递归来处理？
小结
知识点
- 树用父子关系表达层次结构
- 有根、父、子、叶等基本概念
- 每个节点最多一个父节点，且无环
- 子树本身也是树，适合递归处理
参考资料
- Wikipedia(zh)：树 (数据结构)：由节点和父子关系构成的层次结构
- Wikipedia(zh)：递归：处理递归结构的自然方式
思考题答案（仅供参考）
思考题 1
链表的每个节点只有一个后继，所以整体排成一条线；树的每个节点可以有多个子节点，因此能分出层次和分支。正是“一个变多个”，让树能表达层次结构。
思考题 2
因为树本身是递归定义的：去掉根后，剩下的每个子树又是一棵树。处理树时，可以“处理根，再递归处理各子树”，这与树的定义一一对应，代码也就自然、简洁。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪