树系列第 2 篇：树的基本术语——把每一句话都看懂

2026/8/8 31272 字 63 分钟算法树系列 · 第 2 篇

本文是”树系列”的第 2 篇。第 1 篇我们从数组、链表一路走到树，知道了”树”是一种用来表达层级关系和一对多关系的数据结构。这一篇我们不写任何复杂的算法，只做一件事：把树这门”语言”里的每一个词都讲透。读完本文，你再拿起任何一本数据结构教材，看到”子树""内部节点""有序树""路径长度”这些词时，都不会发怵，因为每个词背后都有一幅清晰的画面。

树的结构与术语

1 开场：先回顾第 1 篇，再认识本篇的使命

1.1 我们是怎么走到”树”这里的

第 1 篇里我们讲过，数组像一条排好队的队伍，每个人都有编号，从 0 开始依次排开；要找人，只要知道编号，一步就能到。链表像一条手拉手的队伍，每个人只记住下一个人在哪里；要找人必须从队头开始，一个一个往下问。这两种结构都能存数据，但它们的共同特点是：数据之间的关系是一条线。数组是”前后相邻”，链表是”一个接一个”。

可现实世界里，很多关系根本不是一条线。比如一家公司的组织结构：总经理下面有技术部、市场部、财务部，技术部下面又有前端组、后端组、测试组。这就像一棵倒着长的大树——树根在最上面，树干分叉，树枝再分叉，最后挂满叶子。计算机科学家发现，这种”分叉的、有层级的关系”太常见了，于是专门发明了一种数据结构来表达它，名字就叫树（Tree）。

在第 1 篇里我们还对比过三种结构的优缺点：数组按下标访问最快，链表插入删除灵活，而树擅长表达”谁属于谁""谁包含谁”这样的关系。文件系统就是一个活生生的例子：C 盘下面有 Windows 文件夹、Program Files 文件夹、用户文件夹；用户文件夹下面又有文档、图片、音乐。你在资源管理器里看到的那个目录树，就是一棵标准的树。

1.2 为什么要单独花一整篇讲术语

很多初学者学树的时候，第一个困难不是”树难”，而是”话听不懂”。翻开教材，可能会看到这样一句话：

“树的深度是指根节点到该节点路径上的边数，而树的高度是指该节点到其所有叶子节点路径中的最大值，空树的高度定义为 0。”

这句话里至少有七个词在吓唬人：根节点、路径、边数、叶子节点、最大值、空树、高度。如果你连这些词都还没建立画面，这句话就和天书没有区别。而一旦每个词都有画面，这句话立刻变得平淡无奇。

所以本篇的使命是：把树这门语言的基础词汇全部讲完。这就像学英语先背字母和常见单词，学数学先懂”点、线、面”。后面第 3 篇讲二叉树、第 4 篇讲遍历、第 5 篇讲搜索树，所有文章都会用本篇的词汇来描述。如果本篇没读懂，后面的文章每一句都可能是障碍；如果本篇读懂了，后面所有文章都会变得顺畅。

另外，术语还有一个实际作用：它们是沟通的公约数。你和一个程序员讨论代码，你说”那个节点的父亲”、“它下面的子树”，对方能瞬间理解；你说”它上面那一坨”、“它底下那一片”，对方可能一脸茫然。教材、论文、面试题、开源代码注释里用的都是标准术语。学会术语，等于拿到了进入这个圈子的通行证。

1.3 本篇的阅读方法

本文是一篇”术语大全”，你可以从头到尾读，也可以把它当字典用：遇到不懂的术语就回来查对应小节。每个术语我都会按同样的套路讲解：一句话通俗定义 → 图示 → 生活中的例子 → 易错点。最后还有一张速查表和几道自测题，帮你检验自己是不是真的学会了。

我强烈建议你边读边在纸上画一棵自己的树，比如画你家的家谱，或者画你的电脑里的文件夹。每学一个术语，就在你画的树上把它指出来。纸上那棵树会变成你脑子里那棵树，以后所有算法都在这棵树上跑。

2 术语总览：先看到整片森林

在逐个讲解之前，我们先看一张”术语总览图”。这张图是一棵只有 9 个节点的小树，我会在它的不同部位标出各种术语。你先不用记住全部，只要有一个整体印象：树是由节点和边组成的，节点之间有上下辈分，树有层次、有深度、有高度，还有各种局部结构。

图 1：术语总览图——一棵 9 节点的树同时标出根、内部节点与叶子。

这张图同时展示了树的三个角色：A、B、D 有孩子，是内部节点；C、E、F、G、H、I 没有孩子，是叶子；从根往下每一层都离根更远，后面的深度、高度、层都会以这棵树为底图。

这棵树有 9 个节点：A 是根节点；B、C、D 是 A 的子节点；E、F 是 B 的子节点；G、H、I 是 D 的子节点。C、E、F、G、H、I 没有子节点，是叶子节点；A、B、D 有子节点，是内部节点。A 是第一层，B、C、D 是第二层，E、F、G、H、I 是第三层。

这张图太小，装不下所有术语。我们会在后面的小节里给它补充：深度、高度、度、路径、子树、森林等，都会各有一张自己的图。你可以把图 1 当作”主地图”，后面的每张图都是对主地图某一部分的放大。

3 为什么术语很重要：术语就是算法的”坐标”

3.1 没有术语，描述会变得又长又模糊

想象一下，没有”父节点”这个词，你要怎么描述”B 是 A 的孩子”？你只能说：“树最上面那个点，和它下面左边的那个点，有关系，左边那个是下面那个的……上级？来源？“你会发现怎么描述都不精确。而”父节点”三个字，把”谁在上、谁在下、谁从谁那里分出来”这个关系压缩成了一个词。

再想象一下，没有”子树”这个词，你要怎么解释”递归遍历”？你只能说”把每个节点下面那一大块再当作一棵小树来处理”。而有了”子树”这个词，一句话就清楚了：“遍历一棵树，就是先处理根，再依次遍历它的每棵子树。“术语是算法的坐标：算法书上每一个步骤，都是用术语写成的。

3.2 术语决定算法描述的精确度

算法是严谨的，不允许歧义。“路径长度”到底是边数还是节点数？“高度”到底从 0 数还是从 1 数？不同教材可能给出不同的约定。术语本身只是名字，但约定必须一致，否则两个程序员讨论问题时会在不知不觉中各说各话。所以本篇在讲解每个度量术语时，都会明确说明我们采用的是哪种约定，以及为什么这种约定在编程中更常见。

这也是为什么”易错点”部分很重要。比如”深度”和”高度”两个词，日常中文里几乎是同义词：“这口井的深度""这座山的高度”，听起来差不多。但在树的结构里，它们有严格分工：深度是从上往下数的，高度是从下往上数的。搞反了，后面学 AVL 树、红黑树的平衡因子时就会完全糊涂。

3.3 术语是不同教材之间的”翻译器”

你以后可能会看中文教材、英文教材、网上的教程，甚至别人的课程笔记。同一个概念，不同地方叫法可能不同：有人把”节点”叫”结点”，有人把”父节点”叫”双亲”，有人把”叶子节点”叫”终端节点”或”树叶”。如果你只记得一种叫法，换一本书就懵了；如果你掌握了概念本身，就知道这些名字都是同一回事。本篇会在适当位置列出常见的别名，帮你建立”翻译能力”。

总之，请把本篇当作一座桥：桥的这边是你已经会的数组和链表，桥的那边是二叉树、堆、搜索树、哈夫曼树。术语就是桥上的每一块木板。

4 第一组术语：树的”积木”——节点与边

树是由什么组成的？答案只有两个：节点和边。就像一栋楼是由砖块和水泥组成的，一台自行车是由零件和螺丝组成的，一棵树在数据结构里，就是”节点 + 边”的组合。这一节我们把这两块积木讲透，顺带把”根”和”空树”这两个特殊成员也讲清楚。

4.1 节点（Node），也叫顶点（Vertex）

一句话定义：树里的每一个”点”就是一个节点，它是存放数据的基本单位。

在画图的时候，节点通常画成一个小圆圈、一个小方块，或者一个小圆角矩形；里面可以写一个字母、一个数字，也可以写一句话。在真实的程序里，节点就是一个对象、一个结构体，里面至少有两样东西：要存的数据，以及指向其他节点的指针（引用）。

图 2：节点的抽象图——节点是"数据 + 指向子节点的指针"的容器。

一个节点就像一个抽屉：抽屉里放着数据（数字、字符串、对象都可以），抽屉外壁有几个挂钩，用来挂住它的子节点。当挂钩上什么都没有时，就说明这个节点没有对应的子节点。

生活中的例子： 文件夹资源管理器里的每一个文件夹、每一个文件，都是”节点”。家谱里的每一个人，公司组织图里的每一个职位，网页里的每一个 HTML 标签（<html>、<body>、<p>），都是节点。节点可以很小，比如一个整数；也可以很大，比如一个包含几百个字段的对象。

易错点：

“节点”和”结点”是同一个意思。 在计算机教材里，两个词都大量出现，只是译法不同。考试、面试、写代码时不要因为它们长得不一样就觉得是两个概念。
节点不等于数据本身。 准确地说，节点是”装数据的容器”。同一个数字 42 出现在树的两个不同位置上，那是两个不同的节点；它们恰好存着相同的值。这在以后学”树的查找”时很重要：我们找的是节点，判断的是节点里的值。
一个节点可以有 0 个子节点，但树里每个节点（除了根）都有且仅有一个父节点。 这个”有且仅有一个”是树和普通”图”的关键区别，后面讲性质时还会回到这里。
顶点（Vertex）是图论里的叫法。 树是图的一种特例，所以有些教材在讲树时会用”顶点”代替”节点”。在本书（本系列）中，我们统一用”节点”，但你看到”顶点”时要知道它们是一回事。

4.2 边（Edge）

一句话定义：连接两个节点的线就是边，它表示两个节点之间”有关系”。

在树的图里，边通常画成一条直线或一条折线，把父节点和子节点连起来。边本身不存数据（在更高级的”带权树”里边上可以带数字，但现在我们先不考虑）。一条边只做一件事：表示”我从你来”或者”我是你的孩子”。

图 3：边——只连接父节点与子节点，兄弟之间没有边。

A 和 B 之间有一条边，A 和 C 之间有一条边。注意：边连接的是”父子关系”，而不是任意两个节点之间的随便连线。树里没有”跨层直连”的边，比如 B 和 C 之间绝对不能直接画一条线（除非这棵树变成了一张图，那就是另一回事了）。

生活中的例子： 家谱里”爸爸”和”儿子”之间那条从父指向子的连线就是边；公司组织图里”总经理”到”部门主管”的连线是边；文件系统里”文件夹”和它直接包含的”子文件夹”之间的包含关系是边。人际关系里的”认识""同事""亲戚”都是关系，但只有”直接上下级”或”直接包含”这种一对一的从属关系才会成为树里的边。

易错点：

边是”直接”关系，不是”传递”关系。 爷爷和孙子之间有血缘，但树里爷爷到孙子之间没有直接边；它们之间隔着爸爸这个节点。边只存在于”直接相连”的父子之间。从爷爷到孙子要经过两条边（爷爷→爸爸、爸爸→孙子）。
树里的边没有方向争议。 有些教材把树画成”上面到下面”的有向边，有些画成无向边。重要的是关系：谁是谁的父节点。我们画图时统一用箭头或直线都可以，只要能从位置关系看出层级。
边上通常不存数据。 如果你在某个数据结构里看到”边上带权值”，那叫带权树（加权树），比如网络最小生成树。基础阶段默认边是”裸的”，只表达关系。
n 个节点的树恰好有 n-1 条边。 这是树的铁律，我们会在第 9 节专门讲它的直觉。现在先记住这个数字关系：节点数减一等于边数。

4.3 根（Root）

一句话定义：整棵树最顶端的、没有父节点的那个节点，就是根。

现实中的树，根长在泥土下面，枝干朝上长；数据结构里的树正好反过来，根画在最上面，树枝朝下长。这是几乎所有教材的默认画法：根在上，叶子在下。为什么这么画？因为人类阅读习惯是从上往下，而且文件系统、目录结构、公司组织图都是这么画的，看多了就习惯了。

图 4：根——唯一没有父节点的节点，是整棵树的入口。

最上面那个节点没有箭头指向它，也就是没有任何节点是它的父节点，它就是根。树里的根只有一个，不可能有两个根同时存在；如果出现两个没有父节点的节点，那它就不是一棵树，而是两棵树（或一片森林）。

生活中的例子： 家谱里最早的祖先（比如族谱的第一代）是根；公司组织图里最高的那个职位（CEO）是根；文件系统里最顶层的盘符（C:\）是根；HTML 文档里最外层的 <html> 标签是根。网站的域名解析树里，最顶层的根域名服务器是根。

易错点：

根没有父节点，但它可以有 0 个、1 个或多个子节点。 一个只有根、没有任何子节点的树是合法的，它叫”只有一个节点的树”，也叫”退化到极点的树”。
根不是”最重要的数据”，而只是”入口”。 很多初学者以为根节点必须存最重要的数据，其实根只是一个起点，数据重要性由你自己决定。搜索树里根的值恰好处于中间，那是算法设计的结果，不是树的定义要求。
树”倒过来”画不影响它是一棵树。 有些书把根画在左边，叶子在右边（常见的二叉树画法）；有些书甚至把根画在下面。只要关系不变，都是同一棵树。考试时别因为画法不同就以为结构不同。
根唯一是判断”这是不是一棵树”的第一步。 看到一张图，先数一数有几个没有父节点的节点：0 个说明它连”根”都没有（是空树或画错了）；2 个及以上说明它至少是两棵树。

4.4 空树（Empty Tree）

一句话定义：一个节点都没有的树，叫空树，它是树的”零”。

你可能觉得”没有节点的树”是个奇怪的概念——什么都没有，还能叫树吗？能。空树在算法里非常重要，因为很多树的操作都要处理”树是空的”这种情况：比如在一个空目录里查文件、在一个空家谱里找祖先、在递归函数里判断”该返回了”。空树是递归的终点，也是很多定义的边界条件。

图 5：空树——0 个节点、0 条边，是递归的终止条件。

空树没有根，没有边，没有叶子，深度为 0（不同约定下高度为 -1 或 0，后面会细讲）。它就是一个”什么都没有”的容器。

生活中的例子： 一个刚新建、还没有放入任何文件的文件夹；一个还没开始记录的族谱；一个空目录。程序里最常见的空树就是一个值为 null（或 None）的根指针——null 表示”这里没有节点”。

易错点：

空树和”只有一个节点的树”完全不同。 空树有 0 个节点；只有一个节点的树有 1 个节点、0 条边，它的根同时也是一个叶子。很多初学者把两者混为一谈，导致递归边界写错。
空树在”高度”和”深度”的定义上有分歧。 有的教材规定空树高度为 -1（这样只有一个节点的树高度就是 0，方便某些公式），有的规定空树高度为 0。考试时先看教材约定；编程时，取决于你用的语言和库的文档。本系列采用最流行的约定：空树高度为 -1，深度为 0（严格说深度是”根到某节点”，空树没有节点，所以没有深度；后面我们会把约定讲清楚）。
空树不是一个”节点值为空”的树。 如果一个根节点存在，但它的值恰好是 null 或空字符串，那它仍然是一个有 1 个节点的树，不是空树。判断空树要看”有没有节点”，而不是看”节点里存了什么”。
写递归遍历时，空树是终止条件。 几乎每一个树算法都会先写一句”如果当前节点为空，直接返回”。这句话就是在处理空树（以及递归到叶子下面时的空指针）。

5 第二组术语：树里的”亲戚关系”

树之所以叫”家族树”，是因为节点之间的关系特别像家庭成员：有父母、有孩子、有兄弟姐妹、有祖辈、有后代。这一组术语是整个树语言里最常用、最基础的，务必彻底掌握。

5.1 父节点（Parent Node），也叫双亲节点

一句话定义：在一条边上，位于上方、直接”生出”下方节点的那个节点，就是下方节点的父节点。

父节点是”直接上级”，不是”所有上级”。比如你的爸爸是你的父节点，你的爷爷是你的祖先，但不是你的父节点。在树里，“父”这个字永远表示隔了一层的直属关系。

图 6：父节点——一个父节点可以有多个孩子，每个孩子却只有一个父节点。

P 是 C1 的父节点，也是 C2 的父节点。反过来，C1 和 C2 都是 P 的子节点。一个父节点可以有很多子节点，但一个子节点只有一个父节点。

生活中的例子： 文件夹 A 里面直接装着文件夹 B，那么 A 是 B 的父文件夹（父目录）。公司里”部门经理”是”小组长”的直接上级，经理是小组长的父节点；总经理是经理的父节点，但不是小组长的父节点。家谱里你的父亲是你的父节点，你的祖父不是。

易错点：

父节点是”直接”的，不是”间接”的。 这是新手最常犯的错。面试时说”根节点是所有节点的父节点”是不对的，根节点是所有节点的祖先，但不是除直接子节点以外任何节点的父节点。
根节点没有父节点。 当你用程序表示树时，根节点的 parent 指针通常是 null（或 None）。检查一个节点是不是根，就看它的 parent 是不是空。
在”孩子表示法”的实现里，每个节点只存它的子节点列表，父节点不单独存。 这时要找父节点可能很麻烦（要遍历整棵树）。反过来，在”双亲表示法”的实现里，每个节点只存 parent 指针，找父节点很容易，找子节点却要遍历。实现方式决定操作成本，后面讲树存储时再展开。

5.2 子节点（Child Node），也叫孩子节点

一句话定义：在一条边上，位于下方、直接挂在父节点下面的节点，就是父节点的子节点。

子节点是”直接下属”。一个父节点可以有多个子节点，也可以一个都没有（那它就是叶子）。子节点之间没有先后顺序的硬性规定——除非我们在讲”有序树”（第 8 节），那时从左到右的顺序才有意义。

图 7：子节点——孩子数量没有上限，所有孩子共用同一个父节点。

P 有三个子节点：K1、K2、K3。树里”孩子”的数量没有上限，一棵树可以长出几百万个孩子；但每个孩子都只有这一个父节点。

生活中的例子： 一个文件夹里的直接子文件、一个经理手下的直接下属、一个 HTML 标签里的直接子标签。注意”直接”二字：<div> 里嵌着 <span>，<span> 里又嵌着 <b>，那么 b 是 span 的子节点，div 是 b 的祖先，但不是它的父节点。

易错点：

子节点必须在”下面一层”，不能隔层。 孙子不是儿子的父节点直接子节点。在树图里，“同一条边两端”才是父子。
子节点的顺序。 对于无序树，画图时把三个孩子按什么顺序排都无所谓；但对于有序树（比如二叉树、表达式树），左右顺序就是结构的一部分，交换两个孩子的顺序会得到一棵不同的树。这一点到第 8 节详细讲。
“孩子”是相对的。 同一个节点，在爸爸面前是孩子，在自己的孩子面前是爸爸。一个节点既可以有父节点，又可以有子节点，这完全正常。
数组和链表里的”下一个”不是子节点。 子节点表示”分支出去”，而链表里的 next 表示”继续往前走”。树之所以是树，正因为一个父节点可以有多个子节点，形成分叉。

5.3 兄弟节点（Sibling）

一句话定义：拥有同一个父节点的两个节点，互为兄弟节点。

“同一个爸爸”是唯一条件。同辈但不同爸（比如堂兄弟姐妹）不是树里的兄弟；叔叔和你也不是兄弟。树里的兄弟关系只认父节点。

图 8：兄弟节点——同一个父节点才互为兄弟，同一层不等于兄弟。

S1、S2、S3 因为拥有同一个父节点 P，所以互为兄弟。W 和 V 虽然和 S 们处于同一层，但父节点不同，不算兄弟。画树时经常会把”同一层的节点”误认为兄弟，其实层只是视觉上的水平对齐，兄弟关系看的是”同一个父节点”。

生活中的例子： 同一个文件夹里的两个子文件夹是”兄弟文件夹”；同一个父亲的两个孩子是亲兄弟；同一级、同一个经理手下的两个员工是兄弟节点。注意：不同经理手下的员工，即使职级一样，也不是树里的兄弟。

易错点：

兄弟必须同父。 判断时不要看”是不是同一层”（深度相同），而要看”父节点是不是同一个”。深度相同但父不同的节点，在树里没有任何特殊称呼，就叫”非兄弟的节点”。
兄弟之间没有边。 树里只有父子之间有边，兄弟之间没有直接连线。有些实现为了遍历方便，会用指针把兄弟串成一个链表（这叫”孩子兄弟表示法”），但那是实现细节，不是树本身的定义。
叶子节点也可以有兄弟。 “兄弟”和”是不是叶子”无关，只和”是否同父”有关。两个叶子可以是兄弟；一个叶子和一个内部节点也可以是兄弟。
“兄弟”在某些教材里也叫”同胞”。 英文是 sibling，有的中文教材译为”兄弟结点”或”姊妹结点”。看到这些词都明白是同一个意思。

5.4 小结：亲戚关系图

我们把这一组的四个术语放在一张图里，方便你对照记忆：

图 9：亲戚关系对照——父、子、兄弟、堂关系只看"是否直接相连/同父"。

A 和 B 是兄弟（同一个父节点 Root）；C 和 D 是兄弟（同一个父节点 A）；E 是 C 的子节点；F 是 D 的子节点。注意 E 和 F 是”堂”关系（父节点不同），在树术语里没有专门的词，它们只是”同一层但不是兄弟”。

这组术语为什么如此重要？ 因为树的所有算法都建立在”沿着父子关系移动”之上：从父到子叫”往下走”，从子到父叫”往上走”，处理完一个孩子再处理下一个孩子叫”遍历”。如果你能脱口而出”X 的父节点是 Y、兄弟是 Z”，你就已经具备了阅读任何树算法的基本能力。

6 第三组术语：往上追溯与往下延伸

有了”父母”和”孩子”，我们就可以沿着边往上走或往下走。往上走遇到的所有节点叫祖先，往下走遇到的所有节点叫后代。而一棵树里那些”没有孩子”的节点和”有孩子”的节点，分别叫叶子和内部节点。这四个词看似简单，却是很多复杂算法的关键词。

6.1 祖先（Ancestor）

一句话定义：从某个节点出发，沿着”父节点”指针一路往上走到根，途中经过的所有节点（不含它自己）都是它的祖先。

“祖先”是”父节点”的推广：父节点是直接上一级，祖先是上面所有级别。判断规则很简单：只要”往上走多少步”能走到你，你就是我的祖先。 走 1 步到的是父节点，走 2 步到的是祖父，走到头是根。根是所有非根节点的祖先。

图 10：祖先——沿父指针往上能走到我的所有节点，不包括自己。

对于”我”来说，父节点 P 是祖先，祖父 G 是祖先，根 R 也是祖先；但”我的子节点 S”不是我的祖先。祖先永远在自己”上面”，不包括自己。

生活中的例子： 你的父亲、祖父、曾祖父、族谱上每一代长辈都是你的祖先；公司里你的直属领导、领导的领导、直到 CEO 都是你的祖先；文件夹里，C:\文档\报告\2026 这个路径中，C:\ 和 C:\文档 是 报告 的祖先文件夹，C:\文档\报告 是 2026 的祖先文件夹。

易错点：

祖先不含自己。 这是约定：某个节点不是自己的祖先。有些图论教材会区分”真祖先”和”祖先（含自己）“，但在树和大多数算法教材里，祖先默认不含自己。写代码时如果实现”返回所有祖先”，要注意起点是否包含当前节点。
根节点没有祖先。 往上走一步都走不动，所以根节点的祖先集合是空集。
祖先不要求是”同一分支”外的其他分支。 等等，这里要说清楚：从你往上走，路径是唯一的，所以祖先一定在同一条”主干线”上。不可能出现”你的祖先同时也是你叔叔”这种混乱情况——因为树的每个节点只有一条往上走的路。
“祖先”和”长辈”不同。 家谱里”叔叔”是你的长辈，但在树里，叔叔和你的父节点才是兄弟，叔叔不是你的祖先（从你往上走只会经过爸爸、爷爷，不会经过叔叔）。这个区别请特别记住，生活直觉有时会误导树术语。

6.2 后代（Descendant）

一句话定义：从某个节点出发，沿着”子节点”指针一路往下走，能到达的所有节点（不含它自己）都是它的后代。

后代是祖先的反方向：子节点是直接后代，孙子、重孙子都是后代，一直到叶子为止。规则同样简单：从”我”往下走多少步能走到你，你就是我的后代。 走 1 步到的是子节点，走 2 步到的是孙节点。

图 11：后代——从我开始往下能走到的所有节点，不包括兄弟和长辈。

对于”我”来说，所有能往下走到的节点——子、孙、重孙——都是后代。我的兄弟不是后代，我父亲的兄弟（叔叔）不是后代，因为他们不在”从我开始往下走”的路径上。

生活中的例子： 你的儿女、孙子孙女、家族谱里所有后辈都是你的后代；一个经理手下的所有员工（包括间接下属）都是他的后代；文件夹 A 里嵌套的所有子文件夹、子文件都是 A 的后代。

易错点：

后代不含自己。 与祖先的约定一致：自己不是自己的后代。
叶子节点没有后代。 往下一步都走不了，所以叶子的后代集合是空集。
“直接包含”和”间接包含”都算后代。 只要路径上”顺着走”能到，不管隔多少层都算。这与”子节点”不同，子节点只算直接一层。
后代是按”整棵子树”计算的。 某个节点的所有后代，加上它自己，恰好组成”以它为根的一棵子树”——这是下一节”子树”的核心，先在这里埋个伏笔。
别把”数组里的后面元素”叫后代。 树的后代是层级上的”下方”，不是线性顺序上的”后面”。只有父子边组成的路径才能决定后代关系。

6.3 叶子节点（Leaf），也叫叶节点、终端节点

一句话定义：没有子节点的节点，就是叶子节点。

叶子是树的”末端”。它没有孩子，所以不能再往下分叉。在画图时，叶子通常画在树的最底层，但要注意：叶子不一定都在同一层。一棵树可以有的叶子在第 2 层，有的叶子在第 5 层，只要”没有子节点”，就是叶子。

图 12：叶子节点——没有子节点的节点，叶子不一定在同一层。

B、C、D、E 都没有子节点，都是叶子。注意 B 在第 2 层，C、D、E 在第 3 层——叶子不一定同层。A 有子节点，不是叶子。

生活中的例子： 文件系统里，文件夹是内部节点，文件通常是叶子（文件里面不能再装文件夹；不过某些系统允许文件里嵌文件，那是特例）；家谱里还没有孩子的人是叶子；公司里没有下属的普通员工是叶子；HTML 里没有子标签的标签（比如 <img>、<br>）是叶子。表达式树里，数字和变量名是叶子，运算符是内部节点。

易错点：

叶子看”有没有子节点”，不看”有没有父节点”。 根如果只有一个节点，那它既是根又是叶子。这个”既是又是”让很多初学者困惑：一棵只有一个节点的树，它的唯一节点没有父节点（所以是根），也没有子节点（所以是叶子）。完全合法。
叶子不一定在最底层。 这是最常被误解的一点。树不是”满”的，有些分支长、有些分支短，短分支上的末端节点依然是叶子，即使旁边还有更深的节点。
“终端节点”是叶子的别名。 英文 leaf 或 terminal node。看到”终端”别以为是跟网络设备有关，就是指树走到头了。
叶子是递归的终点。 遍历、计算高度、判断平衡，几乎所有算法都会遇到”这个节点是叶子吗”的问题。判断代码通常是 node.left == null && node.right == null（二叉树）或 node.children.length == 0（一般树）。

6.4 内部节点（Internal Node），也叫非终端节点、分支节点

一句话定义：有至少一个子节点的节点，就是内部节点。

内部节点是”中间人”：它既不是树的最顶端（根除外），也不是树的最末端。它至少有一个孩子，所以还能继续”分叉”。根也算内部节点（只要根有至少一个子节点），这是很多人的认知盲区。

图 13：内部节点——至少有一个孩子的节点，有孩子的根也是内部节点。

R、A、B 都有子节点，都是内部节点；L1、L2、L3 没有子节点，是叶子。注意 R 是根，同时也是内部节点——“根”和”内部节点”不是互斥的。

生活中的例子： 公司里的所有中层管理者（有下属）都是内部节点；文件系统里的所有非空文件夹都是内部节点；家谱里有孩子的人都是内部节点。一句话：能往下”生”的节点就是内部节点。

易错点：

内部节点和叶子合起来正好是所有节点。 这是数学上”互补”的两个集合：任意一个节点，要么没有子节点（叶子），要么有至少一个子节点（内部节点），不存在第三种情况。所以记住一个定义，另一个自动得到。
根是不是内部节点，取决于它有没有孩子。 只有一个节点的树，根没有孩子，那它是叶子而不是内部节点（也不是”根兼内部节点”）。有孩子的根，就既是根又是内部节点。
不要用”在第几层”来判断。 一个第 2 层的节点如果有孩子，它依然是内部节点；一个第 5 层的节点如果没有孩子，它依然是叶子。层数与是否内部无关，只与”有没有孩子”有关。
二叉树里，内部节点特指度数为 2 或度数为 1 的节点（有孩子即内部）。 有些教材把二叉树里”度数为 2 的节点”单独叫”双分支节点”或”全节点”，这类细分到第 3 篇讲二叉树时再说。

6.5 补充：根、叶子、内部节点三者的关系

用一个简单的包含关系来总结：叶子 = 没有孩子的节点；内部节点 = 有孩子的节点；根 = 没有父节点的节点。 根可能同时是内部节点（有孩子时），也可能同时是叶子（单节点树时）；叶子永远不会是根（除非树只有一个节点）。三者的定义各管各的，不要把它们当成”并列的三类”。

7 第四组术语：树的”局部”与”路线”

这一节讲两个特别重要的概念：子树和路径。子树让我们能用”递归的眼光”看树——整棵树里套着小树；路径让我们能精确说出”从 A 到 B 要走几步”。这两个概念是后面一切树算法的支柱。

7.1 子树（Subtree）

一句话定义：选中树里的任意一个节点，把它和它所有的后代（再加上它们之间的边）一起拿出来，就是一棵子树，根就是选中的那个节点。

子树是”树里的树”。因为树的每一部分都保持着树的所有特征——有根（你选的那个节点）、有边、有叶子、有层级——所以完全可以把”某节点及其后代”当作一棵独立的树来看待。这是递归思想的物质基础：处理一棵大树时，可以把问题分解成”处理根 + 处理它的若干子树”。

图 14：子树——某节点连同全部后代构成一棵完整的小树，是递归的基本单位。

虚线框里的 A、C、D、E、F 是一棵完整的小树：它有根、有边、有叶子，完全符合树的定义。递归遍历正是靠”把当前节点连同后代看成子树”才把大问题拆小的。

以 A 为根的子树包含 A、C、D、E、F 这五个节点以及连接它们的四条边；B 和 G 不在 A 的子树里。整棵树则以 R 为根，包含所有节点。每个节点（包括叶子）都定义了一棵自己的子树——叶子的子树只有一个节点，就是它自己。

生活中的例子： 文件系统里任何一个文件夹，连同它里面的所有子文件夹和文件，就是一棵子树；公司里任何一个部门，连同它下面的所有小组，就是一棵子树；家谱里任何一个人，连同他所有的后代，就是一棵子树。你在 Windows 资源管理器里”展开”一个文件夹看到的所有东西，就是以它为根的子树。

易错点：

子树必须”连根拔起”，不能只拿一部分。 如果你把 A 的某个孩子 C 拿走了，剩下的 A、D、E、F 就不构成子树吗？不，A、D、E、F 依然构成以 A 为根的子树，但那是”另一棵”子树（少了 C 分支）。真正的”以 A 为根的子树”包含 A 的所有后代，一个都不能少。
叶子也形成子树。 以叶子为根的子树只有一个节点。所以”每个节点都有一棵子树”这句话永远成立，这为递归算法提供了统一性：遍历整棵树 = 遍历以根为根的子树，递归出口就是叶子（或空）。
子树与祖先/后代的关系： 以 A 为根的子树 = {A} ∪ A 的所有后代。这个公式把两个术语连起来了。
“子树”的英文是 subtree，常缩写为 sub-tree。 读代码时看到 leftSubtree、rightSubtree 就是”左子树、右子树”，那是二叉树里特有的说法。
不要幻想”悬浮的子树”。 子树不能脱离原来的父节点独立存在吗？可以独立存在——当我们”取出”子树作为新的根时，它在逻辑上就是一棵新树。但在原树中，它仍然连着上面。两种视角都合法，取决于上下文。

7.2 路径（Path）

一句话定义：从树中一个节点出发，沿着边走到另一个节点，所经过的节点序列（按顺序）就是一条路径。

路径是”走出来的路线”。在树里，任意两个节点之间的路径是唯一的（这是树的另一条重要性质，第 9 节会讲）。路径上依次经过的节点不能”跳着走”，必须一步一步沿着边移动。

图 15：路径——R→A→C→E 是唯一路线，不能跳边。

从 R 到 E 的路径是 R → A → C → E，一共经过 4 个节点、3 条边。注意不能从 R 直接”跳到”E，因为 R 和 E 之间没有边；也不能走 R → B → G → ……，因为那到不了 E，而且那不是通往 E 的唯一路线。

生活中的例子： 文件夹路径 C:\文档\报告\2026 就是从根 C:\ 到文件夹 2026 的路径，中间依次经过文档、报告；家谱里从曾祖父到你的”血统链”就是一条路径；公司里从 CEO 到你，逐级往下的一条”汇报链”就是一条路径。计算机网络里的”路由”这个词，也和树的路径思想同源。

易错点：

路径要”经过边”，不能隔空跳。 有些初学者把”A 和 E 都是 R 的后代”就直接说”R 到 E 有一条边”，这是错的：边只连接父子，R 到 E 的路径要经过中间节点。
树中路径唯一。 在一般的图里，两点之间可能有很多条路径；在树里，任意两点之间恰好只有一条路径。这个性质是树被称为”无环连通图”的通俗表达，后面会展开。
路径有方向吗？ 树上从 A 到 B 和从 B 到 A，经过的节点集合相同、顺序相反。说”路径”时通常不强调方向，但说”从根到节点 X 的路径”时，起点固定为根。
路径里不能重复经过同一个节点。 因为树里没有环，所以树上的自然路径永远不会绕圈；如果你发现某条”路径”绕回了起点，那它一定不是树上的路径。

7.3 路径长度（Path Length）

一句话定义：一条路径经过的”边”的条数，就是这条路径的长度。

路径长度用”步数”来衡量：走一条边，算长度 1。从节点 A 到它自己，路径长度为 0（不走动）；从 A 到它的父节点，路径长度为 1；从根到第 k 层的节点，路径长度为 k-1（如果根是第 1 层的话）。注意：路径长度数的是边，不是节点。

图 16：路径长度——数边不数点，节点数 = 长度 + 1。

R 到 E 的路径经过 3 条边，所以路径长度为 3。路径上一共 4 个节点，但长度是 3。记住口诀：节点数 = 长度 + 1。

生活中的例子： 从家到学校如果经过 2 个路口，路径长度是 2（假设每条路是一段）；文件路径 C:\A\B\C.txt 中从根到文件经过了 3 个文件夹层级，边的数量是 3。坐地铁：换乘站之间的”站间距离”数的是区间数，而不是站点数，这也是路径长度的直觉。

易错点：

数边不数点。 最经典的口误：“R 到 E 经过 4 个节点，所以路径长度是 4”。正确是 3。考试和面试中这种”差一”错误极其常见，务必养成先画边再数边的习惯。
路径长度和”距离”常混用。 在无权树里，“距离”通常就指路径长度（边数）。在带权树里，距离是边上权值的总和，那就不是简单的边数了。
根到根的路径长度为 0。 有些题问”根节点的深度”，答案通常是 0（按边数约定），和”根到根的路径长度是 0”一致。如果你按”层数减一”算，也得到 0。
路径长度用于定义深度： 一个节点的深度 = 从根到这个节点的路径长度。下一节马上讲深度，这两个概念是连在一起的。

7.4 为什么子树和路径是”递归与查询”的基础

子树给了我们”分解”的工具：一棵树的问题可以变成”根的问题 + 每棵子树同样的问题”。路径给了我们”定位”的工具：每个节点都能用”从根到它的路径”来描述，就像每个文件都有绝对路径一样。几乎所有树算法——遍历、查找、插入、删除、平衡——最终都是在”沿着路径走”和”递归处理子树”这两件事上做文章。你现在先建立这两个画面，后面每一篇文章都会反复用到。

8 第五组术语：给树”量尺寸”——深度、高度与层

接下来这一组是树术语里最容易被搞混的：深度、高度、层。它们都是用来描述”节点在树里的纵向位置”的，但方向和约定各不相同。我先把三个词用一句话说清，再逐个配图展开：

深度（depth）：从根往下数，到某个节点要经过几条边。
高度（height）：从某个节点往下数，到它最深的后代叶子要经过几条边。
层（level）：把节点按”离根几步”分组，同一组就在同一层。

一句话记忆：深度是”我从根上走了多远”，高度是”我离最深的叶子还有多远”，层是”我们按距离分的班”。

8.1 深度（Depth）

一句话定义：一个节点的深度 = 从根节点到这个节点的路径长度（经过的边数）。

深度是”以根为参照物的绝对纵向坐标”。根节点的深度是 0；根的直接子节点深度是 1；再下一层是 2，依此类推。深度只和”这个节点离根多远”有关，和树的其他部分无关。

图 17：深度——从根往下数边，根深度 0，同层节点深度相同。

R 的深度为 0，A、B 的深度为 1，C、D、E 的深度为 2，F 的深度为 3。深度由”从根往下走的边数”决定，同一层的节点深度相同。F 离根最远，深度最大，等于 3。

生活中的例子： 公司里”你是第几级下属”就是深度：CEO 是第 0 级，直接向 CEO 汇报的是第 1 级，再往下是第 2 级。文件系统里”从盘符开始数，路径中有几个文件夹”就是深度（按边数算）。家谱里”你是第几代”也是深度的直觉，不过家谱通常从 1 开始数代，那是”层”的约定。

易错点：

深度从 0 开始（按边数约定）。 这是本系列采用的约定，也是大多数现代教材和编程实现（如数组下标、树的高度公式）默认的约定。但有的教材从 1 开始数，把根叫”第 1 层、深度 1”。考试时一定要先看题目约定；和别人讨论时先说清”按边数还是按节点数”。
深度是每个节点自己的属性。 “树的深度”的说法其实不太严谨——树没有唯一的深度，除非特指”最大深度”（等于树的高度）。当有人问”这棵树的深度”，他通常想问的是”最深节点的深度”，也就是树的高度。
叶子节点也有深度。 深度只看离根多远，与是不是叶子无关。第 2 层的叶子和第 2 层的内部节点深度相同。
深度和路径长度是一回事。 深度 = 根到该节点路径的长度。所以第 7 节讲的”数边不数点”在这里同样适用：根的第 3 层后代（根算第 0 层）深度为 3。

8.2 高度（Height）

一句话定义：一个节点的高度 = 从该节点出发，往下走到它最远的叶子节点所经过的边数。

高度是”以最深的叶子为参照物的向下距离”。叶子节点的高度是 0（因为它自己就是最远的叶子，走 0 步就到了）。根节点的高度就是整棵树的高度——这是树最重要的指标之一，决定了很多算法的时间复杂度。

图 18：高度——从节点到最远叶子数边，叶子高度 0，取最大值。

每个节点旁边标的是它自己的高度：叶子 D、E、F 高度为 0；C 的最远叶子是 F，C→F 有 1 条边，所以 C 高度为 1；A 的最远叶子是 F（路径 A→C→F 有 2 条边）或 D（A→D 有 1 条边），取最大值 2，所以 A 高度为 2；R 的最远叶子是 F，路径 R→A→C→F 有 3 条边，所以整棵树高度为 3。注意 B 高度只有 1，因为它的子树比较矮。

生活中的例子： 一座大楼里，某层的”剩余高度”是从这一层到最高层还要爬几层楼梯——你在一楼时离顶楼最远，在顶楼时剩余为 0。公司里”从我这个职位往下还有几级”就是我的高度：普通员工高度 0，CEO 的高度等于公司层级数减一。

易错点：

高度往下数，深度往上数。 深度从根往下量，高度从叶子往上量。同一个节点，深度和高度几乎总是不同的数字。比如图 18 里 C 的深度是 2、高度是 1；F 的深度是 3、高度是 0。
高度是”到最远叶子”的距离，不是”到最近叶子”的距离。 必须取所有叶子中的最大值。C 有叶子 F（距离 1），如果 C 还有别的叶子在 2 条边外，C 的高度就是 2。
叶子高度为 0，根的高度等于树的”最大深度”。 一棵只有根的树：根的高度 = 0，最大深度 = 0，两者相等。节点数更多时，根的高度 = 最深的叶子离根有几条边 = 树的最大深度。
空树的高度约定不一。 我们采用：空树高度 = -1。这样只有一个节点的树高度 = 0，完美衔接”高度 = 子树高度最大值 + 1”的递归公式（空子树返回 -1，所以叶子 = max(-1, -1) + 1 = 0）。如果你看到教材把空树高度定为 0，也不要慌，那只是另一套约定，公式会相应调整。
“节点高度”和”树的高度”是两码事。 树的高度就是根的高度；每个节点都有自己的高度。面试题里说”计算二叉树的高度”，指的是根的高度。

8.3 层（Level），也叫层级

一句话定义：把”离根同样远”（深度相同）的节点归为一组，每一组就是一层；根所在的那一层叫第 1 层（按节点数约定）或第 0 层（按边数约定）。

层是”横向分组”。它把树横着切成一片一片：第 1 片是根，第 2 片是根的孩子，第 3 片是孙辈，依此类推。层的编号有两种主流约定，我们全系列统一采用第 1 层 = 根的”层”约定（因为层天然对应”第几代”，从 1 开始更符合直觉），而深度继续用 0 起始（因为深度对应”走了几条边”）。两者关系：深度 = 层 - 1。

图 19：层——按深度横向分组，本系列约定根为第 1 层（深度 = 层 - 1）。

根单独在第 1 层；A、B 在第 2 层；C、D、E 在第 3 层；F 在第 4 层。每一层的节点都有相同的深度（层数减一）。如果题目采用”根是第 0 层”，那图中标签全部减一即可，结构不变。

生活中的例子： 公司组织图里的”第 1 级领导、第 2 级领导”就是层；家谱里的”第几代人”就是层；HTML 文档的嵌套层数（<html> 是第 1 层，<body> 是第 2 层，<div> 是第 3 层……）就是层。Excel 里的目录大纲、Markdown 标题层级（# 一级、## 二级）也都是层的直觉。

易错点：

层从 1 还是 0 开始，先问清楚。 数据结构教材常见两种：根在第 1 层（“代数”约定，直观）或根在第 0 层（“下标”约定，方便公式）。本系列中，说”层”默认根在第 1 层；说”深度”默认根深度为 0。你在答题时最好把约定写出来，避免因默认不同而失分。
层和深度容易混用。 同一棵树上，根”在第 1 层”且”深度为 0”；A”在第 2 层”且”深度为 1”。记住：层数 = 深度 + 1（在根为第 1 层的约定下）。如果看到”第 3 层的节点深度为 2”，这就是对的。
“完全二叉树”和”满二叉树”对层的要求，都是以层为计数单位的。 比如”满二叉树的第 k 层有 2^(k-1) 个节点”（根为第 1 层时）。这些公式在第 3 篇会用到，现在先记住层的编号方式即可。
空树没有层。 层是给节点用的，空树一个节点都没有，所以无所谓”第几层”。同理，空树没有深度、没有高度（或高度按约定为 -1）。

8.4 深度、高度、层的”三问三答”

为了帮你彻底分清这三个词，我做一个小问答：

问：一个节点的深度怎么算？ 答：从根出发，走到这个节点经过几条边，深度就是几。根深度 0。

问：一个节点的高度怎么算？ 答：从这个节点出发，走到它最远的叶子经过几条边，高度就是几。叶子高度 0。

问：一棵树的高度是多少？ 答：就是根的高度，也就是从根到最深的叶子经过的边数，等于树里所有节点深度的最大值。

问：深度和高度会相等吗？ 答：可能相等，但不是必然。比如单节点树：根的深度 0、高度 0，相等。链状树（每层只有一个节点）的最深节点深度 = 高度，但中间节点两者不同。总之，不要因为某一次相等就以为两者永远相等。

问：为什么要区分它们？ 答：因为后面学 AVL 树、红黑树时，“左子树高度和右子树高度之差”是平衡判断的核心；学树的遍历时，深度决定递归栈有多深；学完全二叉树时，层数直接出现在数组下标公式里。三个词各有用途，混用会直接导致公式错误。

9 第六组术语：树的”胖瘦”与”秩序”——度、有序树、无序树

树除了有纵向的深度和高度，还有横向的”胖瘦”：一个节点能分出多少个孩子，叫它的度；整棵树最胖的节点有多胖，叫树的度。另外，孩子之间的顺序算不算数，决定了这棵树是有序树还是无序树。这一组术语直接为第 3 篇讲二叉树（度 ≤ 2 的有序树）铺路。

9.1 节点的度（Degree of a Node）

一句话定义：一个节点拥有的”子节点个数”，就是这个节点的度。

度就是”孩子数”。没有孩子的叶子节点，度为 0；有一个孩子的节点，度为 1；有两个孩子的节点，度为 2；有 k 个孩子的节点，度为 k。注意：度只数”直接子节点”，不数孙子、不数父节点。 这和”朋友数量”不同——树里的”度”是单向的，只看往下走了几叉。

图 20：节点的度——有几个直接子节点，度就是几。

左边节点没有孩子，度为 0；中间的节点依次有 1、2、3 个孩子，度分别为 1、2、3。注意所有箭头都从”父母”指向”孩子”，孩子数才是度。

生活中的例子： 家谱里”你有几个孩子”就是你的度：丁克夫妇度为 0，有两个孩子的家庭度为 2。文件夹里”直接包含几个子项”就是该文件夹的度。公司里”直接管理几个下属”就是经理的度。

易错点：

度只看子节点，不看父节点。 这是和”图论中的度”最大的区别：在一般图论里，一个顶点的度是”与它相连的边数”（上下都算）；在树论教材里，“节点的度”几乎总是指”子节点数”。读图论书和数据结构书时要留意语境。有些数据结构教材为了避免歧义，会把图论的度叫”边度”或”图度”，但默认大家说的树的度都是孩子数。
叶子的度是 0。 有子节点才算度，没有就是 0。度不可能为负数。
度与层无关。 一个第 2 层的节点可以有度 5，一个第 1 层的节点也可以有度 0（退化链）。胖瘦与位置无关。
“出度""入度”是图论术语。 如果有人在讲树时说出度，通常指”子节点数”；入度通常指”父节点数”（除了根为 0，其他都是 1）。树的这种”每个节点入度至多 1”的特性，正是它被称为”树”的原因之一。

9.2 树的度（Degree of a Tree）

一句话定义：一棵树里所有节点度的最大值，就是这棵树的度。

树的度描述整棵树的”最大分叉能力”：如果一棵树里最宽的节点有 5 个孩子，这棵树的度就是 5。注意是最大值，不是平均值，也不是根节点的度。根节点度 3、但某个叶子的兄弟节点度 7 的树，树的度是 7。

图 21：树的度——所有节点度中的最大值，B 的 4 决定整棵树是 4 叉树。

这棵树的节点度分别是：根 3、A 2、B 4、其余叶子 0。最大值为 4，所以树的度为 4。如果有人说”这棵树是几叉树”，他问的其实就是树的度：度为 4 的树也叫”4 叉树”。

生活中的例子： 一家公司里管理下属最多的那个经理管了 8 个人，那么这家公司组织树的度就是 8；一个文件夹里最多的直接子项数是 12，那棵目录树的度就是 12。家谱里孩子最多的祖先有 6 个孩子，那棵家谱树的度就是 6。

易错点：

树的度 = 所有节点度的最大值。 不要拿”平均孩子数”来算，也不要只盯根。必须遍历所有节点找最大。
度为 m 的树里，每个节点最多有 m 个孩子。 这是”度”定义的直接推论。后面讲 m 叉树（比如 B 树）时，“m”就是这个最大孩子数。
二叉树的度 ≤ 2。 二叉树的严格定义是”每个节点最多有两个孩子”的有序树，所以它的度至多为 2。但”度为 2 的树”不一定是二叉树——二叉树还要求有序（左/右孩子区分），这个坑第 3 篇会重点讲。
叶子的度为 0，不影响树的度。 一棵全是叶子加一个根的树，树的度就是根的孩子数；如果根也没有孩子（单节点树），树的度是 0。度为 0 的树是合法的，它只有一个节点（或空树按 0 度处理）。

9.3 无序树（Unordered Tree）

一句话定义：孩子的排列顺序不影响树的”身份”，这样的树就是无序树。

在无序树里，父节点的几个孩子”谁在左边、谁在右边”没有意义。把两个孩子交换位置，得到的还是同一棵树。无序树强调的是”集合”：孩子是一个集合，集合没有顺序。

图 22：无序树——孩子是集合，交换顺序仍是同一棵树。

左右两幅图的孩子集合相同（都是 {B, C}），只是画的时候顺序不同。在无序树看来，它们是同一棵树。

生活中的例子： “我有两个孩子，小明和小红”——说”小明、小红”还是”小红、小明”都不改变家庭关系；一个文件夹里两个文件谁排在列表上面都不影响目录树的结构（除非你按名字排序，但排序只是显示方式）。公司里”我手下有张三和李四”，张三李四谁在前谁在后无所谓。

易错点：

无序不代表”没有结构”。 无序只表示兄弟之间不区分顺序，父子、祖先后代这些关系依然严格存在。
存储时孩子通常还是用一个列表。 即使是无序树，程序里也得有个容器装孩子，列表本身有下标；但算法不会依赖下标含义，交换两个孩子的存储位置不算修改树。
判断两棵无序树是否相同，要比”孩子集合”，不能比”孩子序列”。 这在实际编码（比如树的序列化、比较相等）时是个不小的坑，后面讲遍历时会再遇到。

9.4 有序树（Ordered Tree）

一句话定义：孩子的排列顺序是树结构的一部分，交换任意两个孩子的顺序会得到一棵不同的树，这样的树就是有序树。

有序树里，每个父节点的孩子从左到右有明确编号：第 1 个孩子、第 2 个孩子……孩子顺序变了，树就变了。二叉树是典型的有序树：左孩子和右孩子是两回事，哪怕存的值一样，左右互换后就是不同的二叉树。

图 23：有序树——左右顺序是结构的一部分，交换后变成另一棵树。

左右两棵树的节点值集合相同，但左右孩子的分配不同：左边树根的孩子是（1 在左，2 在右），右边树是（2 在左，1 在右）。在有序树（如二叉树）里，它们是两棵不同的树。

生活中的例子： 表达数学公式的表达式树必须有序：3 - 2 和 2 - 3 结果完全不同，所以减号的两个操作数必须区分左右；比赛的对阵表必须有序：A 队 vs B 队和 B 队 vs A 队虽然对手相同，但在赛程表里位置不同；文件系统一般是无序树（排序只是视图），但编程语言里的语法树是有序树（a+b 与 b+a 是不同表达式）。

易错点：

有序树的”顺序”指兄弟之间的左右顺序，不是插入时间。 你可以先插入 B 后插入 C，但规定 B 必须在 C 左边，那 B 就是左孩子。顺序是结构属性，不是历史属性。
二叉树一定是有序树；但有序树不一定是二叉树。 有序树允许一个节点有 3 个、4 个孩子，只要它们有明确的左右次序。第 3 篇讲的二叉树 = 有序 + 度 ≤ 2。
画图时，无序树怎么摆都行，有序树不能乱摆。 遇到有序树，交换两个孩子再画出来，就是另一棵树。判断题目里”画一棵二叉树”，左右顺序错了就判错。
遍历顺序与有序性有关。 中序遍历（左→根→右）之所以有确定结果，前提就是二叉树是有序树。如果树是无序的，“中序遍历”根本没法定义——因为左右没有区别。

9.5 小结：度、有序无序为什么重要

度决定了树的”形状上限”：度为 m 的树，每个节点最多 m 个孩子，所以整棵树最多有多少节点可以由层数算出（第 3 篇会推出公式）。有序性决定了”树怎么被比较、怎么被遍历”：无序树用集合思维，有序树用序列思维。二叉树之所以是计算机里最重要的树，就是因为它”有序 + 度 2”这两个特性叠加，让遍历、查找、堆、哈夫曼编码都有了稳定的秩序。记住这个伏笔。

10 第七组术语：多棵树放在一起——森林

10.1 森林（Forest）

一句话定义：零棵或若干棵互不相交的树放在一起，就组成一片森林。

“森林”不是一个神秘的新结构，它只是”树的集合”。一片森林由多棵树组成，每棵树各有自己的根；树和树之间没有任何边相连。你也可以这样理解：把一棵树的根砍掉（去掉根节点），剩下的就是一片森林——原来根的所有子树，现在变成了各自独立的树。

图 24：森林——若干互不相交的树的集合，删根变森林、加公共根变树。

这里有三棵独立的树，合在一起就是一片森林。三棵树之间没有边，各有各的根。如果把”树 1”的根 1 去掉，剩下的 A、B、C 子树（如果 A、B 各自还有后代）会变成新的独立树，森林里就多出几棵树。

生活中的例子： 你的电脑上有多个盘符，C 盘一棵目录树、D 盘一棵目录树，它们合起来就是一片”目录森林”；一个城市有多家公司，每家公司一棵组织树，全市的公司就是一片森林；族谱分成几个家族支系，每个支系一棵树，合起来是一片森林。数据库里的”多棵索引树”、搜索引擎里的”倒排索引森林”，也都是森林。

易错点：

森林里的树必须”互不相交”。 如果两棵树之间出现一条边把它们连起来，那它们就变成一棵更大的树了，不再是森林。判断森林：数一数有几个没有父节点的根，大于等于 2 就是森林（严格说森林允许 0 棵树，那叫空森林）。
森林不是”节点集合”，而是”树的集合”。 元素是树，不是节点。所以”森林里有几个节点”和”森林里有几棵树”是两个问题，后者问的是根的数量。
删根变森林，加公共根变树。 反过来，如果给一片森林加一个新的根节点，并让新根成为所有树根的父节点，森林就变成了一棵树。这个操作在”森林与二叉树的转换”里非常有用，第 3 篇或第 4 篇会讲到。
空森林存在。 0 棵树也是森林，就像 0 也是自然数。在算法里，“空森林”常常作为递归的起点或终点出现。
森林在存储上通常就是”根的数组”。 一个文件系统可以有多个盘符（多个根）；一个程序可以有多个根节点（比如多个顶层组件）。实现森林时，维护一个”根列表”即可。

10.2 为什么专门给”森林”起个名字

因为很多现实数据天然就是森林：多盘符文件系统、多棵树组成的索引、分片存储的树形数据。更重要的原因是，森林是理解”树与图”关系的桥梁：一片森林加上一个虚拟根节点，就是一棵树；一棵树去掉根，就是一片森林。后面学”森林转二叉树”时，你会感谢现在记住了这个双向转换。

11 树的两个基本性质：为什么树”不会多一条边”

术语讲完了，最后补两棵”定海神针”性质。它们不是要你背诵的结论，而是可以凭直觉想明白的规律。几乎所有树算法的复杂度分析都建立在这两条性质上。

11.1 性质一：n 个节点的树，恰好有 n-1 条边

通俗表述：树里”边数”永远比”节点数”少 1。 1 个节点 0 条边；3 个节点 2 条边；100 个节点 99 条边。

图 25：节点数与边数——n 个节点的树恰好有 n-1 条边。

这棵树有 5 个节点、4 条边，满足 5 = 4 + 1。你随便画多少棵树，这个关系都不会变。

直觉解释（为什么一定是 n-1，不多不少）： 想象一棵树是”从根开始，一个一个地接入新节点”长出来的。最开始只有 1 个根节点，0 条边。每接入一个”新孩子”，它必须连到已有的某个节点上，所以新增 1 个节点、1 条边。于是每增加一个节点，边数跟着增加一条。最终 n 个节点对应 0 + (n-1) = n-1 条边。为什么不能更多？因为每个非根节点有且仅有一个父节点，一条边只对应”一个孩子”，而孩子（非根节点）正好 n-1 个，所以边最多 n-1 条。为什么不能更少？如果少于 n-1 条边，一定至少有一个节点”够不着”根，那它就不在这棵树里，与”树包含所有 n 个节点”矛盾。

这个性质有什么用？ 存储时，树可以用”n-1 条边”的结构来描述，遍历一遍所有边就能访问所有节点；分析递归算法时，每次递归处理一个节点、经过它的一条”进入边”，总工作量与 n 成正比，而不是 n²。比如后面学树的遍历，时间复杂度是 O(n) 而不是 O(n²)，根本原因就是”每个节点只有一条进入边，每个节点只被访问常数次”。

易错点：

n-1 是对”连通且无环”的树说的。 如果图里有环，边数可能 ≥ n；如果图不连通，边数可能 < n-1。树恰好同时满足”连通（从根能到每个节点）“和”无环（没有回头路）“，所以钉死为 n-1。
空树也是 0 个节点、0 条边，满足 0 = 0 + 1 吗？ 注意，n-1 在 n=0 时是 -1，不成立。所以严格说法是”非空的 n 节点树有 n-1 条边”。很多教材默认”树非空”，因此直接说 n-1；遇到空树时，边数是 0，这个公式不适用。这个小细节在证明题里可能被抠。
证明 n-1 的常用方法：归纳法。 一棵 n 节点的树，去掉一片叶子，剩下 n-1 节点的树，边数也少 1；反复归纳即可。等你学完数学归纳法，可以用它给出严格证明；现在只需要直觉。

11.2 性质二：从根到任意节点，路径唯一

通俗表述：树里任何两个节点之间，恰好只有一条路径；从根到任意一个节点，也恰好只有一条路径。

为什么？因为每个节点只有一个父节点。从任意节点出发往上走，每一步的选择都是唯一的（只能走回它的父节点），所以”往上走到根”的路线唯一；反过来”从根往下走到这个节点”的路线也唯一。如果存在两条不同路径，那么在某处一定会”分叉后又汇合”，形成一个环；而树没有环，所以不可能。

图 26：路径唯一（反例）——E 有两个父节点形成环，所以这不是树。

如果从 R 到 E 有两条路（R→A→C→E 和 R→B→D→E），那么 R、A、C、E、D、B 之间就出现了环，图中 E 有两个父节点（C 和 D），这已经违反了”每个节点只有一个父节点”——所以它不是一棵树。把图 26 当成”反例”看：有两条路径的图，必然不是树。

直觉解释： 树像一家公司的汇报链，每个员工只有一个直接上级，所以”向 CEO 汇报的链条”是唯一的；你不可能既向 A 经理汇报又向 B 经理汇报（那样就出现双重领导，组织结构图就乱了）。文件夹系统也一样：一个文件只能在一个文件夹里（硬链接先不管），所以从根到它的”绝对路径”唯一。

这个性质有什么用？ 所有”找路径”的问题在树上都变得简单：从根往下走，每到一个节点，选择通往目标的那条分支；没有环意味着不会走回头路。树的查找、LCA（最近公共祖先）、路径求和等算法，全都依赖”路径唯一”。

易错点：

路径唯一说的是”节点不重复的简单路径”。 在无环的树里，任何”从 A 到 B 再回到 A”的走法都会重复节点，那不是我们说的路径。
有环就不是树。 判断一个结构是不是树，可以从三个等价角度：没有环、连通（任意两点可达）、边数 = 节点数 - 1。满足任意两个，第三个自动成立。这是图论里的经典结论，先记下，以后学图时再严格证明。
路径唯一和”根到节点的路径”是同一件事。 从根到任意节点唯一，是”任意两点唯一”的特例；由于树上任意两点往上都会汇到同一个祖先，任意两点的路径 = “A 到祖先” + “祖先到 B”，也是唯一的。

12 收尾：一张速查表，把全篇装进口袋

在进入自测题之前，先用一张表格把全篇 20 个核心术语浓缩起来。建议你把这张表截图存下来，或者抄一遍贴在手边；以后读任何树相关的文章，遇到不认识的词先回来查表。

术语	一句话定义	关键数字/约定	常见别名
节点	树里存数据的基本单位	一棵非空树至少 1 个节点	顶点、结点
边	连接父节点与子节点的线，表示父子关系	n 个节点的树有 n-1 条边	连线、分支
根	没有父节点的节点，树的入口	唯一；深度 0；第 1 层	根节点
父节点	直接位于某节点上方、通过一条边相连的节点	每个非根节点恰好 1 个	双亲节点
子节点	直接挂在某节点下方的节点	数量不限	孩子节点
兄弟节点	拥有同一个父节点的节点们	不看层，只看父	同胞、姊妹结点
祖先	沿父指针往上能到达的所有节点（不含自己）	根没有祖先	先辈
后代	沿子指针往下能到达的所有节点（不含自己）	叶子没有后代	子孙
叶子节点	没有子节点的节点	度 0；高度 0	叶节点、终端节点
内部节点	有至少一个子节点的节点	有孩子的根也是内部节点	分支节点、非终端节点
子树	某节点及其全部后代组成的树	叶子也有一节点子树	局部树
路径	从一节点沿边走到另一节点经过的节点序列	树上任意两点路径唯一	路线
路径长度	路径经过的边数	数边不数点：节点数 = 长度 + 1	距离（无权树）
深度	从根到某节点经过的边数	根深度 0；深度 = 层 - 1	节点深度
高度	从某节点到其最远叶子经过的边数	叶子高度 0；空树高度 -1（本系列约定）	节点高度
层	离根同样远的节点组成的一层	本系列根为第 1 层	层级、level
节点的度	某节点的子节点个数	叶子度 0	度数
树的度	所有节点度的最大值	度 m 的树每个节点最多 m 个孩子	树的阶、m 叉
有序树	孩子有固定左右顺序的树	交换孩子顺序 = 变成不同的树	定位树
无序树	孩子顺序无关紧要的树	孩子是集合	自由树
森林	若干互不相交的树的集合	根的个数 = 树的棵数；删根变森林，加公共根变树	树的集合
空树	一个节点都没有的树	0 节点 0 边；递归的终点	空结构

这张表里还有两个”隐藏要求”需要提醒你：第一，度和层在不同教材里约定不同，做题前先看题干的定义；第二，深度和高度不是一回事，前者从根往下量，后者从叶子往上量。把这两条记在心上，术语关就算过了。

12.1 五个最常被问的问题（FAQ）

在自测之前，我再集中回答五个初学者最爱问的问题，它们也是老师们最爱在课上强调的点。

问题一：树的节点到底叫”节点”还是”结点”？ 两个都对。这是同一英文单词 node 的不同译法，大陆教材两种写法都常见。你只需要记住它们完全相同；写文章、写代码注释时选一种并保持一致即可。

问题二：深度和高度到底哪个大？ 没有固定答案。深度从根往下量，根深度为 0，越往下越大；高度从叶子往上量，叶子高度为 0，越往上越大。同一棵树里，根的高度最大，叶子的深度最大。如果你问的是”最大深度和树的高度谁大”，它们数值相等。

问题三：根是叶子吗？ 只有一棵树只有一个节点时，根才是叶子（因为它没有子节点）。只要根有至少一个孩子，它就不是叶子，而是内部节点。判断任何节点是不是叶子，永远只看”有没有子节点”。

问题四：兄弟节点之间可以画边吗？ 不可以。树里的边只存在于父子之间。兄弟之间没有边，这是树和”图”的重要区别之一。如果你看到一张图里两个兄弟之间也连了线，那它已经多了一条边，不再是树，而是一张带环的图。

问题五：树的度、节点的度，为什么都用”度”这个字？ 因为它们确实是同一个概念在不同范围上的应用：节点的度是”这个节点有几个孩子”，树的度是”所有节点中最大的孩子数”。你可以把”树的度”理解为”这棵树最宽的地方有多宽”。同理，“度是 2 的树”意味着每个节点最多两个孩子，这正是二叉树的名字来源（二叉树 = 度 ≤ 2 的有序树）。

如果这五个问题你都能不看答案说出来，那么术语这一关你已经稳了。下面进入自测题环节。

13 自测题：检验你这一篇是否真的读懂了

已作答 0 / 5

题目 1（送分题）

一棵树有 12 个节点，请问它有多少条边？如果这棵树的度是 3，请问”度是 3”这句话是什么意思？

题目 2（画图题）

画一棵树：根节点叫 R，R 有 3 个孩子 A、B、C；A 有两个孩子 D、E；D 有一个孩子 F；C 有一个孩子 G。请回答：

这棵树有多少个叶子节点？请一一列出。
F 的深度是多少？F 的高度是多少？
以 A 为根的子树里一共有几个节点？
D 的兄弟节点是谁？D 的祖先节点是谁？

题目 3（判断题）

判断以下说法是否正确，并说明理由：

“树的深度就是树的高度。”
“叶子节点一定在同一层。”
“根节点一定是内部节点。”
“在有序树里交换两个孩子的位置，树的结构没有改变。”
“空树的高度是 -1（按本系列约定），所以空树不是树。”

题目 4（计算题）

一棵树的根为第 1 层（层从 1 开始），有一个节点在第 4 层。请问：

这个节点的深度是多少（深度从 0 开始）？
从根到这个节点的路径长度是多少？
从根到这个节点至少经过多少个节点（含根和它自己）？

题目 5（综合题）

有同学说：“我给一棵树加了一条边，连接了两个本来不相连的节点，结果这棵树变成了森林。“请分析这句话哪里错了。再回答：如果一片森林里有 3 棵树，总共有 10 个节点，请问总边数是多少？如果给这片森林加一个虚拟根，把 3 个根都连到虚拟根上，会得到一棵有几个节点、几条边的树？

叶子节点是 E、F、B、G。逐个数：E 没有孩子；F 没有孩子；B 没有孩子；G 没有孩子。A、R、C、D 都有孩子，不是叶子。
F 的深度：从根 R 到 F 的路径是 R→A→D→F，经过 3 条边，所以深度为 3。F 的高度：F 是最远的叶子（也是它自己），从 F 到最远叶子走 0 条边，所以高度为 0。
以 A 为根的子树包含 A、D、E、F 共 4 个节点。注意 F 是 D 的孩子，D 是 A 的孩子，F 在 A 的子树里；B、C、G 不在。
D 的兄弟是 E（它们有同一个父节点 A）。D 的祖先是 A 和 R（往上走 1 步到 A，再走 1 步到 R）。C 不是 D 的兄弟，因为父节点不同。

错。树的深度如果指”最大深度”，数值上等于树的高度；但”深度”是节点属性，树里不同节点的深度不同，而”高度”以叶子为参照。说”树的深度”通常指最大深度，可以等于树高；但”深度”和”高度”作为概念不是一回事，一个往上一个往下。若题目考察概念辨析，应判错；若只问数值，则可能相等。
错。叶子只要求”没有子节点”，不要求同层。比如根有孩子 A（内部）和 B（叶子），B 在第 2 层，而 A 的孩子 C 是叶子在第 3 层，B 和 C 都是叶子但不同层。
错。根节点有没有孩子不确定：单节点树的根没有孩子，是叶子而不是内部节点。只有当根有至少一个子节点时，根才是内部节点。
错。有序树的孩子顺序是结构的一部分，交换两个孩子的左右位置会得到一棵不同的树。无序树才无所谓顺序。
错。空树按约定高度为 -1，但它依然是一棵树（0 个节点的树）。“高度为 -1”只是度量约定，不改变”空树是树”的身份。其实最后半句也可以换一种说法：如果你所在的教材约定空树高度为 0，那 -1 就不对；但无论如何，空树不是”不是树”。

深度 = 层 - 1 = 4 - 1 = 3（本系列深度从 0 开始）。
路径长度 = 从根到该节点经过的边数 = 深度 = 3。
节点数 = 边数 + 1 = 3 + 1 = 4，即根、第 2 层节点、第 3 层节点和它自己，共 4 个节点。

第二问：森林共 10 个节点、3 棵树。设三棵树的节点数分别为 n1、n2、n3，则 n1 + n2 + n3 = 10；每棵树的边数为节点数减 1，所以总边数 = (n1-1) + (n2-1) + (n3-1) = 10 - 3 = 7。给这片森林加一个虚拟根，把 3 个根都连到虚拟根上，节点数变成 10 + 1 = 11，新增 3 条边，总边数变成 7 + 3 = 10，恰好等于 11 - 1，符合”n 个节点的树有 n-1 条边”，说明加虚拟根后确实变成了一棵树。这个”森林加虚拟根变树”的小把戏，后面学森林与二叉树转换时还会再用。

14 下一篇预告：二叉树，一切树的”主角”

术语讲完了，从下一篇开始，我们进入树系列的重头戏。

《树系列第 3 篇：二叉树》 将回答这些问题：为什么计算机科学家在所有树里最偏爱”每个节点最多两个孩子的有序树”？二叉树有哪些独特的术语——左孩子、右孩子、左子树、右子树、满二叉树、完全二叉树、完美二叉树？二叉树为什么能放进数组里用下标访问？为什么中序遍历、前序遍历、后序遍历只有在二叉树上才这么自然？你还会看到，本篇学的”度”和”有序”两个概念，在二叉树里是如何合并成”左/右”这个精确结构的。

在下一篇到来之前，请你做一件事：把本篇的速查表抄一遍，然后看着一棵真实的目录树，把每一个术语都指认一遍。 当你能够指着屏幕说”这是根、这是叶子、这是子树、它的深度是 2、它的高度是 1”时，你就已经完成了从”听过树”到”懂树”的第一步。下一棵更精彩的树，正在等你。