树 | 自在学

树与二叉搜索树：从层级表示到动态集合操作

数组和链表擅长表达一条线上的先后关系，树则用来表达层级。一个节点可以管理若干子节点，子节点又可以继续向下展开。目录、语法结构、索引和搜索状态都能用这种形状组织。

学习树时，最容易混在一起的是三件事：树本身怎样定义、树怎样存进内存、某种特殊树允许怎样查找。本文先把层级术语和表示方法说清楚，再讨论二叉树的遍历，最后完整实现二叉搜索树的查询、插入与删除。所有操作都围绕同一个量分析：树高 $h$ 。

有根树中的根、父子、兄弟、深度与高度

从一组层级关系认识树

一棵有根树由有限个节点组成，其中有一个指定节点叫根。除根以外，每个节点恰好有一个父节点；从根到任意节点都存在唯一的一条向下路径。最后这句话同时排除了环和“一个节点有两个父节点”的情况。

如果树有 $n$ 个节点，那么它恰好有 $n-1$ 条父子边。原因很直接：根没有父边，其余 $n-1$ 个节点各贡献一条从父节点连来的边。

必须分清的术语

假设根是“课程”，它有“基础篇”和“进阶篇”两个孩子，“基础篇”下面又有“数组”和“链表”。那么：

“课程”是根，也是“数组”的祖先；
“基础篇”是“数组”的父节点；
“数组”和“链表”有同一个父节点，因此互为兄弟；
没有孩子的“数组”“链表”“进阶篇”都是叶节点；
以“基础篇”为根，连同它的全部后代，构成一棵子树。

节点 $x$ 的深度是根到 $x$ 的路径包含的边数，所以根的深度为 $0$ 。节点 $x$ 的高度是从 $x$ 向下到叶节点的最长路径所含边数，所以叶节点的高度为 $0$ 。整棵树的高度就是根的高度，也等于所有节点深度的最大值：

\operatorname{height}(T)=\max_{x\in T}\operatorname{depth}(x)

只有一个根节点的树，高度是 $0$ ，不是 $1$ 。有些工程文档会用“节点层数”定义高度，使单节点树高度为 $1$ 。两种约定都能使用，但公式、代码和复杂度分析必须从头到尾保持同一约定。本文一律按边数计算。

路径唯一带来的递归结构

取任意节点 $x$ 。删去 $x$ 与各孩子之间的边，每个孩子下面仍是一棵独立的树。这让树天然适合递归：处理 $x$ ，再用同一个过程处理 $x$ 的每棵子树。

很多树算法都依赖下面这个递归不变式：

当过程开始处理节点 $x$ 时，以 $x$ 为根的整棵子树仍未处理；过程结束时，这棵子树中的每个节点都恰好处理一次，子树之外的节点没有被碰到。

证明时先处理空树或叶节点，再假设每棵更小的子树都能正确处理，最后把孩子子树的结果与根 $x$ 合并即可。这种证明方式比按节点编号逐个讨论更贴合树的结构。

树高和节点数不是同一个量。含 n 个节点的二叉树，高度最小是 Θ(log n)，最大可以是 n−1；孩子数不受限的普通有根树甚至可以让根直接连接其余所有节点。二叉搜索树的基本操作花费 O(h)，只有在树高受控时才能把它写成 O(log n)。

小测

一棵有根树有 18 个节点，它有多少条父子边？

按边数定义高度时，叶节点的深度和高度都一定为 0。

怎样把树存进内存

树的数学形状只规定父子关系，不规定对象里要放哪些指针。表示方法应根据常用操作来选：要频繁向下找孩子，就保存孩子指针；只向上追溯，就可能只需父指针；若树恰好是完全二叉树，甚至可以不用任何链接。

二叉链接、孩子数组与左孩子右兄弟三种表示

二叉树的三个链接

二叉树的每个节点都有两个有次序的位置：左孩子和右孩子。常见节点对象包含：

text

节点:
    key       // 关键字或主要数据
    parent    // 父节点；根的 parent = NIL
    left      // 左孩子；不存在时为 NIL
    right     // 右孩子；不存在时为 NIL
 
树:
    root      // 根；空树时 root = NIL

left = NIL, right ≠ NIL 和 left ≠ NIL, right = NIL 是两种不同形状，不能把唯一孩子笼统存成“第一个孩子”。父指针不是表达树形所必需的，但它能让前驱、后继和删除操作从节点向上走。若省略父指针，就要在调用栈、显式栈或额外查询中保留祖先信息。

孩子数量有上界时

如果每个节点最多有固定的 $k$ 个孩子，可以保存 child[0..k-1]。访问第 $i$ 个孩子是 $O(1)$ ，但当 $k$ 很大、绝大多数节点只有少量孩子时，大量位置会一直是 NIL。

若孩子数没有固定上界，就不能在节点结构里预先写出无限多个指针。把每个节点的孩子放进动态数组或链表是一种办法；另一种只需固定两个向下/横向指针的方法，是左孩子—右兄弟表示。

左孩子—右兄弟表示

每个节点保存三项链接：

parent 指向父节点；
firstChild 指向最左边的孩子，没有孩子则为 NIL；
nextSibling 指向右边紧邻的兄弟，自己是最右孩子则为 NIL。

要枚举节点 $x$ 的全部孩子，先到 x.firstChild，再沿 nextSibling 一直走。若 $x$ 有 $d$ 个孩子，枚举代价为 $\Theta(d)$ 。每个节点只保存常数个指针，所以 $n$ 个节点的总空间是 $\Theta(n)$ 。

text

打印任意有根树(x):
    if x == NIL:
        return
    输出 x.key
    child = x.firstChild
    while child != NIL:
        打印任意有根树(child)
        child = child.nextSibling

这里最关键的不变式是：child 之前的兄弟子树已经全部打印，child 及其右侧兄弟尚未打印。每个节点通过父节点的孩子链被进入一次，因此总时间是 $\Theta(n)$ ，不是“层数乘孩子数”。

点击节点检查三个指针

小测

关于左孩子—右兄弟表示，下列哪些说法正确？

一个节点有 d 个孩子，使用左孩子—右兄弟表示枚举完这些孩子需要的时间是 ____。

二叉树、完全二叉树与数组映射

二叉树不是“每个节点有不超过两个孩子”的无序树。它的左、右位置有明确区别：只有一个左孩子与只有一个右孩子是不同的二叉树。这个次序也是中序遍历和二叉搜索树能够定义的前提。

一般二叉树、满形态与完全二叉树的区别

几种容易混淆的形状

二叉树：每个节点有左、右两个可选位置。
每个内部节点都有两个孩子的二叉树：节点的孩子数只能是 $0$ 或 $2$ ，但叶节点不必处在同一深度。
各层全部填满的二叉树：所有内部节点都有两个孩子，并且叶节点深度相同。高度为 $h$ 时共有 $2^{h+1}-1$ 个节点。
完全二叉树：除最底层外每层都填满，最底层节点从左到右连续出现。

中文资料有时会把前两种都叫“满二叉树”，命名并不稳定。阅读接口或题目时，应优先检查它给出的结构条件，不要只靠名称判断。

完全二叉树为什么能直接放进数组

完全二叉树按层序从左到右编号时，中间没有空洞。若数组使用从 $1$ 开始的下标，节点 $i$ 的位置关系是：

\operatorname{parent}(i)=\left\lfloor\frac{i}{2}\right\rfloor,\qquad \operatorname{left}(i)=2i,\qquad \operatorname{right}(i)=2i+1

根节点 $i=1$ 没有父节点；只有当计算出的孩子下标不超过当前元素数 $n$ 时，孩子才真实存在。

程序数组通常从 $0$ 开始。此时对应公式变为：

\operatorname{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor,\qquad \operatorname{left}(i)=2i+1,\qquad \operatorname{right}(i)=2i+2

parent(0) 不应套公式，而应直接报告“根没有父节点”。混用两套编号是堆实现中最常见的下标错误。

对于非空的 $n$ 节点完全二叉树，最后一个节点的深度是 $\lfloor\lg n\rfloor$ ，也就是树高：

h=\lfloor\lg n\rfloor

数组表示节省了每个节点的指针，但它依赖“层序编号连续”这一条件。一般二叉树若缺口很多，仍按完全形状分配数组，会产生大量空槽；这时链接表示更合适。

数组映射只描述完全二叉树的形状，不等于二叉搜索树性质。堆通常用完全二叉树保证高度，并用“父节点不小于或不大于孩子”约束关键字；二叉搜索树则要求左、右整棵子树相对根有序。两者不能互相替代。

小测

从 0 开始编号的完全二叉树中，下标 4 的左孩子下标是多少？

只要每个节点最多有两个孩子，这棵树就一定适合用紧凑数组且没有空洞地保存。

遍历：让每个节点恰好被访问一次

遍历的目标不是“尽量多走节点”，而是按规定顺序让每个节点恰好被访问一次。对二叉树，深度优先遍历有三种经典顺序，区别只在访问根的时机。

前序、中序、后序与层序遍历的访问顺序

三种深度优先顺序

对以 $x$ 为根的子树：

前序：根 → 左子树 → 右子树；
中序：左子树 → 根 → 右子树；
后序：左子树 → 右子树 → 根。

text

前序(x):
    if x == NIL: return
    访问(x)
    前序(x.left)
    前序(x.right)
 
中序(x):
    if x == NIL: return
    中序(x.left)
    访问(x)
    中序(x.right)
 
后序(x):
    if x == NIL: return
    后序(x.left)
    后序(x.right)
    访问(x)

三段代码都先处理空指针，这是递归的边界。对非空节点，它们只把左右子树的处理顺序与根的访问位置组合起来。因为左右子树不相交，归纳假设保证两边各访问一次，再加上根的一次，整棵子树便恰好访问一次。

若左子树有 $k$ 个节点、右子树有 $n-k-1$ 个节点，遍历时间满足：

T(n)=T(k)+T(n-k-1)+\Theta(1)=\Theta(n)

这个结论与树是否平衡无关。递归额外空间取决于同时存在的调用帧数，是 $O(h)$ ：平衡树为 $O(\log n)$ ，链状树为 $O(n)$ 。

不递归的中序遍历

显式栈保存“已经到达但还没访问”的祖先：

text

迭代中序(root):
    stack = 空栈
    current = root
    while current != NIL or stack 非空:
        while current != NIL:
            stack.push(current)
            current = current.left
        current = stack.pop()
        访问(current)
        current = current.right

外层循环的不变式是：栈里从底到顶是一条祖先路径，各节点的左侧已部分展开，但节点自身和右子树仍待处理。每个节点入栈、出栈各一次，时间仍是 $\Theta(n)$ ，额外空间仍是 $O(h)$ 。

层序遍历

层序遍历按深度从小到大访问，用队列保存已经发现、尚未处理的节点：

text

层序(root):
    if root == NIL: return
    queue = 空队列
    queue.enqueue(root)
    while queue 非空:
        x = queue.dequeue()
        访问(x)
        if x.left  != NIL: queue.enqueue(x.left)
        if x.right != NIL: queue.enqueue(x.right)

每个节点入队、出队各一次，时间为 $\Theta(n)$ 。队列最大长度取决于树的最大宽度，记作 $w$ ，所以额外空间是 $O(w)$ 。链状树的 $w=1$ ；接近完整的二叉树，最宽一层可以包含 $\Theta(n)$ 个节点。

自己切换四种访问顺序

小测

关于遍历复杂度，下列哪些说法正确？

若需要先释放左右子树，再释放父节点，最合适的遍历顺序是什么？

二叉搜索树的不变式

二叉搜索树是在二叉树形状上增加关键字次序。对任意节点 $x$ ，它的左子树所有关键字不大于 $x.key$ ，右子树所有关键字不小于 $x.key$ 。这个条件必须对每个节点的整棵子树成立，只比较一个节点与两个直接孩子还不够。

重复键必须先定策略

允许重复键时，仅写“左边小、右边大”是不完整的。工程实现常选下面一种策略：

节点另存计数，同键只增加计数；
每个键只存一个节点，节点里挂同键值列表；
重复键也建节点，并固定放到右侧或固定放到左侧。

本文的代码采用“严格小于走左边，否则走右边”：

y\in x.left\Rightarrow y.key<x.key, \qquad y\in x.right\Rightarrow y.key\geq x.key

这里的 $y$ 表示相应子树中的任意节点，不只表示孩子。固定策略让插入路径可复现。普通查找在遇到相等关键字时返回某一个匹配节点；如果接口要求取出全部重复记录，还要继续枚举相等区间或改用计数/列表方案。

中序为什么得到非递减序列

对任意节点 $x$ ，中序先输出左子树，再输出 $x$ ，最后输出右子树。假设两个更小子树的中序结果已经各自有序；左侧所有值都不大于 $x.key$ ，右侧所有值都不小于 $x.key$ ，三段拼接后仍非递减。

若有 $n$ 个节点，中序遍历花费 $\Theta(n)$ 。它能得到有序结果，却不表示建树成本也是线性：逐个插入的总代价取决于每次插入时的树高。

形状决定操作速度

同一组关键字可以形成不同形状。如果依次插入 2, 4, 6, 8, 10，每个新键都落在右侧，树退化成长度为 $n$ 的链，高度为 $n-1$ 。若插入顺序让根接近中位数，树可能保持较矮。

BST 的查找、最小值、最大值、前驱、后继、插入和删除都沿一条或常数条根到叶路径工作，因此统一为 $O(h)$ ：

O(h)= \begin{cases} O(\log n), & \text{树高受控时},\\ O(n), & \text{最坏退化为链时}. \end{cases}

“二叉搜索树操作是 O(log n)”缺少前提。普通 BST 不会自动平衡；严格递增或严格递减的插入序列就能制造高度 n−1。需要稳定最坏 O(log n) 时，应选择带平衡规则的搜索树。

小测

只要每个节点都满足左孩子小于自己、右孩子大于自己，就一定是合法二叉搜索树。

有重复键时，二叉搜索树的中序遍历结果通常是 ____ 序列，而不一定严格递增。

查询、最值、前驱与后继

BST 查询之所以快，不是因为“二叉”本身，而是每次比较都能排除一整棵不可能包含目标的子树。下面假设 key 可比较，树采用上节约定的重复键策略。

二叉搜索树的查找路径、最值与后继两种情况

查找沿唯一方向下降

text

查找(root, target):
    x = root
    while x != NIL and x.key != target:
        if target < x.key:
            x = x.left
        else:
            x = x.right
    return x

循环开始时的不变式是：如果目标存在于当前尚未排除的子树中，那么它一定在以 $x$ 为根的子树中。目标小于 x.key 时，右子树及 $x$ 都不可能匹配，转向左侧仍保持不变式；大于时对称。遇到相等就成功，遇到 NIL 就说明路径走尽。

查找访问的节点组成一条向下简单路径，最多跨过 $h$ 条边，所以时间为 $O(h)$ ，迭代版本额外空间为 $O(1)$ 。

最小值与最大值

非空子树的最小节点是最左节点，最大节点是最右节点：

text

最小节点(x):
    要求 x != NIL
    while x.left != NIL:
        x = x.left
    return x
 
最大节点(x):
    要求 x != NIL
    while x.right != NIL:
        x = x.right
    return x

为什么可以一直向左？若 $x$ 有左子树，子树中的值都小于或等于 $x.key$ ，最小值不会在右侧；若没有左子树， $x$ 就是当前子树最小节点。两种操作都沿一条路径，花费 $O(h)$ 。对空树应返回 NIL、可选值或明确错误，不能直接解引用根。

后继的两种情况

节点 $x$ 的后继，是中序序列中紧跟在 $x$ 后面的节点。若关键字互异，它也就是大于 x.key 的最小关键字。

有右子树：后继是右子树的最小节点，也就是先向右一步，再一路向左。
没有右子树：向父节点走，跳过所有“当前节点位于其右子树”的祖先。第一次遇到“当前路径来自父节点左侧”的父节点，它就是后继。

text

后继(x):
    if x.right != NIL:
        return 最小节点(x.right)
    y = x.parent
    while y != NIL and x == y.right:
        x = y
        y = y.parent
    return y

若循环最后得到 NIL，说明原节点是整棵树中序序列的最后一个节点，没有后继。前驱完全对称：有左子树时取左子树最大节点；否则向上跳过所有“当前节点位于父节点左侧”的祖先。

后继或前驱只沿一条向下路径或一条向上路径，时间都是 $O(h)$ ，不会同时遍历整棵树。

如果节点只保存 left 和 right、不保存 parent，仍能在 O(h) 时间找后继，但查询时要保存祖先路径，或从根重新搜索并记录“可能的后继”。空间与接口会变，次序性质不会变。

小测

节点 x 有非空右子树时，它的中序后继是哪一个节点？

关于 BST 查询操作，下列哪些说法正确？

插入与删除：修改后仍保持有序

查询只读取结构，插入和删除会改链接。判断实现是否正确，要在每次修改后检查三类不变式：根的父指针是 NIL；每条父子链接双向一致；每个节点的左、右子树仍满足关键字范围。

二叉搜索树插入路径与删除的四种链接调整

插入：找到本应出现的空位置

插入新节点 $z$ 时，从根按查找规则向下走，直到下一步是 NIL。需要一个滞后指针 $y$ 记住最后一个非空节点，因为最终要修改的是它的 left 或 right。

text

插入(T, z):
    y = NIL
    x = T.root
    while x != NIL:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    z.left = NIL
    z.right = NIL
    if y == NIL:
        T.root = z
    else if z.key < y.key:
        y.left = z
    else:
        y.right = z

循环不变式是： $y$ 始终是 $x$ 的父节点，并且当前 $x$ 所在位置是新键仍可能插入的唯一子树。退出时 $x=NIL$ ，把 $z$ 放在这里不会跨过任何比较边界。空树时 $y=NIL$ ，必须单独把设成根。

插入沿一条向下路径，时间为 $O(h)$ ；新节点本身只增加 $O(1)$ 空间。

移植：只负责接上父节点

删除经常需要用一棵子树替换另一棵子树。把这个链接动作抽成 移植(T, u, v)：

text

移植(T, u, v):
    if u.parent == NIL:
        T.root = v
    else if u == u.parent.left:
        u.parent.left = v
    else:
        u.parent.right = v
    if v != NIL:
        v.parent = u.parent

移植只让 $v$ 接管 $u$ 在父节点下面的位置，不会自动设置 v.left 或 v.right。调用方若误以为它会搬好整棵结构，最容易造成丢子树或父指针悬空。

删除分成四种链接形态

设要删除节点 $z$ ：

z.left == NIL：用右子树替换 $z$ 。右子树也可能是 NIL，所以同时覆盖叶节点。
z.right == NIL：用左子树替换 $z$ 。
两个孩子都存在，且后继 $y$ 就是 z.right：直接用 $y$ 替换 $z$ ，再把 z.left 接给 y.left。
两个孩子都存在，且 $y$ 位于右子树更深处：先用 y.right 替换 $y$ ，再让接管；最后用替换并接管。

两孩子情况下， $y$ 是 z.right 的最小节点，因此 y.left 必为 NIL，它至多只有一个右孩子。这正是能够先把 $y$ 从原位置摘出的原因。

text

删除(T, z):
    if z.left == NIL:
        移植(T, z, z.right)
    else if z.right == NIL:
        移植(T, z, z.left)
    else:
        y = 最小节点(z.right)
        if y.parent != z:
            移植(T, y, y.right)
            y.right = z.right
            y.right.parent = y
        移植(T, z, y)
        y.left = z.left
        y.left.parent = y

移植 是 $O(1)$ ，寻找后继最多向下走 $h$ 层，所以删除总时间为 $O(h)$ 。删除根时由移植直接更新 T.root；删唯一节点时，根会变成 NIL。

一份可运行的 TypeScript 实现

下面实现把重复键固定插入右侧。delete 接收节点引用，因此能准确删除某一个重复节点；若只有关键字，应先 search 得到一个匹配节点。

class TreeNode {
  left: TreeNode | null = null;
  right: TreeNode | null = null;
  parent: TreeNode | null = null;
 
  constructor(
    public key: number,
    public value: string = "",
  ) {}

若节点可能来自另一棵树，公开的 delete(node) 还应验证所有权；若比较器允许不可比较值，也应在插入前拒绝它们。这些属于接口防御，不改变树操作的核心逻辑。

动手修改一棵搜索树

小测

删除一个同时有左右孩子的节点 z 时，为什么可以用 z 右子树的最小节点 y 来替换它？

实现 BST 删除时，下列哪些边界必须显式处理？

z.right

z.left