07 - 树：从家谱到文件夹
前面的数组、链表、栈、队列都是「一条线」的线性结构。从这一章起，我们进入树——一种「分叉」的层级结构。它是现实世界里「有上下级、有归属关系」的东西的天然模型。
树长什么样
树（Tree） 由一个个节点组成，节点之间是「父子」关系，从一个顶点向下不断分叉：
[根: 电脑]
/ | \
[C盘] [D盘] [E盘]
/ \ |
[文档] [下载] [项目]
|
[简历.pdf]几个术语（对着上图看，一看就懂）：
- 根节点（Root）：最顶上的那个（电脑），整棵树的起点，只有一个。
- 父节点 / 子节点：C盘是「文档」「下载」的父节点；反过来它们是 C 盘的子节点。
- 叶子节点（Leaf）：最末端、没有孩子的节点（简历.pdf、项目）。
- 子树：任何一个节点带着它下面的所有后代，本身也是一棵小树。
它叫「树」，但习惯上是根朝上、枝叶朝下画的，像一棵倒着的树。
为什么需要树：现实里到处是层级关系
很多东西天生就是「一层套一层、有归属」的结构，用一条线（数组/链表）根本表达不了，用树却无比自然：
- 文件系统：文件夹里套文件夹套文件（操作系统篇第 09 章的目录树，就是一棵树）。
- 公司组织架构：CEO → 各部门总监 → 经理 → 员工。
- 家谱：祖先 → 父辈 → 子孙。
- 网页的结构（HTML DOM）：
<html>里套<body>，<body>里套<div>……前端说的「DOM 树」就是它。 - 分类目录：图书分类、商品分类，一级套二级套三级。
只要你看到「有上下级、有归属、能一层层展开」的关系，那就是树的用武之地。
树的关键特点
- 有且只有一个根，从根出发能到达任何一个节点。
- 每个节点只有一个父亲（除了根没有父亲），但可以有多个孩子。
- 没有环：顺着父子关系往下走，不会绕回来（绕回来就成「图」了，第 11 章讲）。
一句话概括树和线性结构的区别：
线性结构是「一个跟着一个」，树是「一个能分出好几个」——从一维的线，升级成了有层次的分叉。
树带来的好处：查找可以「分层排除」
树不只是用来「表示层级」，它还能大大加快查找。直觉是这样的：
在一条线上找东西，你只能一个个往后看。但在一棵有组织的树上，你每往下走一层，就能排除掉一大片不用看的分支。
好比找文件：你不会把电脑里所有文件翻一遍，而是「先进 D 盘 → 再进项目文件夹 → 再进这个项目」，每选一层就排除了其他盘、其他文件夹的海量文件。层层缩小范围，快得多。
这个「每往下一层就排除一大半」的能力，正是下一章二叉搜索树能做到 O(log n) 快速查找的核心。而它也解释了为什么数据库、文件索引都爱用树。
小结
- 树是「分叉」的层级结构，由节点通过父子关系连接，从根节点向下展开。
- 术语：根（顶点，唯一）、父/子节点、叶子（末端无孩子）、子树。
- 特点：只有一个根、每个节点只有一个父亲、没有环。
- 它是现实中层级/归属关系的天然模型：文件系统、组织架构、家谱、HTML DOM、分类目录。
- 树还能加速查找——每往下一层就排除一大片，这是下一章 O(log n) 查找的基础。
下一章 → 08 - 二叉树与二叉搜索树 ｜ 回到 README 目录