第 4.0 章树

Tree

引入

这是文件系统中的一个目录：

/course/chapter4/examples/TreeDemo.java

文件系统要回答：

chapter4 的父目录是谁
chapter4 下有哪些直接子目录
course 下面一共有多少层
删除 chapter4 时，哪些内容属于它的整个子树

如果只用“前一个 / 后一个”的线性关系，这些问题会变得非常别扭。真正需要表达的是：一个对象可以同时拥有多个直接后继，而且这些关系会继续递归展开。

当关系从“一前一后”变成“一对多”，数据应该怎样组织？

层级关系远不止文件目录

同一种结构模式还反复出现在：

编译器抽象语法树（Abstract Syntax Tree，AST）：一个表达式节点拥有多个子表达式
HTML 文档对象模型（Document Object Model，DOM）：页面元素形成嵌套层级
数据库索引：上层索引节点把查询引向不同子范围
大语言模型 / 智能体追踪：一次运行下可能包含模型调用、工具调用和子智能体运行，常按父子关系形成执行树

这些场景都需要表示递归的层级关系。

本章将从普通树和二叉树（binary tree）出发，进一步研究树怎样存储、怎样遍历、怎样由遍历序列恢复，以及如何利用树的结构设计更高效的算法。

学习目标

掌握普通树和二叉树的定义
掌握根（root）、父结点（parent）、子结点（child）、兄弟结点（sibling）、叶结点（leaf node）、度（degree）、层次（level）、高度（height）等术语
理解二叉树的基本性质和完全二叉树（complete binary tree）数组公式
掌握二叉树的链式、数组和游标表示
掌握先序（preorder）、中序（inorder）、后序（postorder）、层序（level-order）遍历
根据先序+中序或后序+中序构造二叉树
理解树、森林与二叉树的转换
理解线索二叉树（threaded binary tree）和 Huffman 树的核心思想

本章路线图

树
层次结构

树的语言
根 · 父子 · 层次 · 高度二叉树
结构约束与基本性质存储表示
链式 · 数组 · 游标遍历
先序 · 中序 · 后序 · 层序由遍历重建
序列如何恢复结构树与森林
孩子兄弟表示（child-sibling representation）与转换结构扩展
线索化 · Huffman 最优编码

树

树定义

树 \(T\) 是结点的有限集合。

树可以为空。

若树非空，则存在一个特殊结点 \(r\)，称为根；其余结点被划分为若干棵互不相交的非空子树：

\(T_1,T_2,\cdots,T_k\)

递归定义是树结构的核心。

树也是一种图：连通且无环

从图论角度看，非空树就是一个无向、连通、无环图。

连通：任意两个结点之间都有路径
无环：不存在从某点出发又回到该点的简单环
两点之间的简单路径是唯一的

若树有 \(n\) 个结点，则边数一定是

\(|E|=n-1\)

原因：除根结点外，每个结点恰好有一条来自父结点的边。

树一定是二部图

以根为起点，按深度奇偶性给结点分组：

偶数层放入集合 \(U\)
奇数层放入集合 \(V\)

树中每条边都连接相邻两层，因此总是跨越 \(U\) 与 \(V\)：树一定是二部图。

这里“无环”很关键：从根到每个结点的简单路径唯一，因此结点的深度奇偶不会产生冲突。

因为树原本没有环，加一条边会产生唯一一个环；如果这个环是奇环，图就不再是二部图。

树的术语

树的术语：度

结点的度：一个结点拥有的孩子个数。

若结点 \(v\) 有 \(k\) 个孩子，则 \(\deg(v)=k\)。

因此：

度为 \(0\)：叶结点

树的度：整棵树中所有结点度数的最大值，即 \(\deg(T)=\max_{v\in T}\deg(v)\)。

注意：结点的度和树的度

线性结构与树结构

维度	线性结构	树结构
关系	一对一前后关系	一对多父子关系
入口	通常是表头或栈顶	根
移动方向	前驱/后继	父、孩子、兄弟
典型遍历	从左到右	深度优先或广度优先、二叉树的前序中序后序

二叉树

二叉树定义

递归定义： 二叉树或者是空树，或者由一个根结点和两棵互不相交的二叉树——左子树与右子树——构成。

左、右子树有顺序：只有左孩子和只有右孩子是不同结构。

递归定义，对应递归操作

二叉树与普通树的区别

维度	普通树	二叉树
孩子数	任意多个	最多两个
子树是否有序	常视为无序	左右有序
空子树	通常不显式出现	左空与右空要区分
存储方式	孩子链表、长子兄弟	左右孩子指针

表达式二叉树

该树表示：

\[ (a*b)+(c/d) \]

第 i 层结点上界

设根在第 \(0\) 层，第 \(i\) 层最多有：

\(2^i\)

个结点。

高度为 \(h\) 的二叉树最多有：

\(1+2+\cdots+2^h=2^{h+1}-1\)

个结点。

叶结点与二度结点

在一棵非空二叉树中，记 \(n_0\)、\(n_1\)、\(n_2\) 分别为叶结点、一度结点、二度结点的个数。

要验证： \(n_0=n_2+1\)。

从只有根结点的树开始逐步扩展，可以直接观察一度结点和二度结点对叶结点数量的不同影响。

满二叉树（perfect binary tree）与完全二叉树

完全二叉树数组公式：0-based 与 1-based

本课程后续涉及数组下标时统一使用 0-based；1-based 只在这里作为常见写法进行对照。

存储表示

二叉树存储一：数组表示

二叉树存储二：链式表示

static class BinaryNode<T> {
  T element;
  BinaryNode<T> left;
  BinaryNode<T> right;

  BinaryNode(T element) {
    this.element = element;
  }
}

BinaryNode 保存一个元素和左右孩子引用，是二叉树所有结构关系的基本单元。

一个二叉节点只需保存元素和左右两个孩子入口；整棵子树通过这两个引用递归可达，不需要为不存在的孩子预留数组位置。

BinaryNode(element) 创建一个尚未连接孩子的新结点；元素先确定，左右孩子默认保持为空，之后再由树操作建立链接。

新节点开始时左右孩子自然为空；先建立元素，之后再通过改写两个孩子引用把已有子树接到它下面。

二叉树存储三：游标表示

index	data	left	right
0	A	1	-1
1	B	2	3
2	C	-1	-1
3	D	4	5
4	E	-1	6
5	F	-1	-1
6	G	-1	-1

游标表示用数组下标模拟指针。

运行时性能：树的表示会影响机器代价

树的渐近复杂度常写成 \(O(h)\) 或 \(O(n)\)，但真实运行还取决于结点如何放在内存里。

数组表示连续，父子下标可直接计算，硬件预取和缓存局部性较好
链式表示灵活，但指针跳转可能跨越多个缓存行
游标表示把“指针”换成数组下标，能减少碎片并便于序列化

`BinaryTree` 类接口

二叉树作为一个ADT，我们需要三类能力：管理树的结构、按不同顺序遍历、询问树的结构属性。

`BinaryTree` 类接口代码

interface BinaryTreeApi<T> {
  boolean isEmpty();
  T rootElement();

  void makeTree(T element, BinaryTree<T> left, BinaryTree<T> right);
  TreeParts<T> breakTree();

  List<T> preorder();
  List<T> inorder();
  List<T> postorder();
  List<T> levelOrder();

  int height();
}

接口把二叉树需要支持的操作一次列全：基本查询、结构组合与拆分、四种遍历，以及树高查询。

isEmpty() 与 rootElement() 只读取当前根入口，不改变树的结构。

makeTree(…) 和 breakTree() 改变树的组成关系，分别负责组合与拆分。

四种遍历访问的是同一批结点，区别只在访问顺序；后面会分别跟踪它们的执行过程。

height() 返回结构性质；它取决于左右子树的高度。

`BinaryTree` 基本实现：根入口与查询

static class BinaryTree<T> implements BinaryTreeApi<T> {
  private BinaryNode<T> root;

  BinaryTree() {}

  private BinaryTree(BinaryNode<T> root) {
    this.root = root;
  }

  public boolean isEmpty() {
    return root == null;
  }

  public T rootElement() {
    if (root == null) {
      throw new NoSuchElementException("tree is empty");
    }
    return root.element;
  }

BinaryTree 的整个结构只由一个根入口拥有；从 root 可达的全部结点就是这棵树。

root 是唯一结构入口；无参构造器让它保持 null，于是自然得到一棵空树。

BinaryTree(root) 用已有根结点接管一棵树；之后所有操作都从这个入口出发。

无论空树还是已有根的树，都只维护一个入口；构造过程不需要复制任何子树。

isEmpty() 只检查 root 是否为空，时间复杂度为 O(1)。

根入口不存在时整棵树为空；入口存在时无需遍历左右子树就能完成判断。

rootElement() 读取根结点元素，不改变树的结构。

读取根元素前必须排除空树；入口存在后，根值可以直接取得。

`MakeTree`

makeTree(A, left, right) 把两颗子树的拥有权转移到一个新根下面。

`MakeTree` 代码

public void makeTree(T element, BinaryTree<T> left, BinaryTree<T> right) {
  Objects.requireNonNull(left, "left");
  Objects.requireNonNull(right, "right");
  if (this == left || this == right || left == right) {
    throw new IllegalArgumentException("trees must be distinct owners");
  }
  BinaryNode<T> newRoot = new BinaryNode<>(element);
  newRoot.left = left.root;
  newRoot.right = right.root;
  root = newRoot;
  left.root = null;
  right.root = null;
}

makeTree(…) 把一个根元素和两棵子树连接成新树，同时转移子树所有权。

三棵 BinaryTree 必须是不同拥有者；否则组合会让同一结构既当输入又当输出，造成别名和重复所有权。

新根把两棵输入树的入口接成左右孩子；这一刻新树已经能到达两边全部节点，不需要复制任何子树。

输出树取得新根后，必须清空原左右树的入口；节点只保留一个逻辑拥有者，所有权转移才真正完成。

`BreakTree`

breakTree 做的是 makeTree 的逆过程：把根数据、左子树、右子树分别交还出去，同时让原树变空。

`BreakTree` 代码

public TreeParts<T> breakTree() {
  if (root == null) {
    throw new NoSuchElementException("tree is empty");
  }
  BinaryNode<T> oldRoot = root;
  BinaryTree<T> left = new BinaryTree<>(oldRoot.left);
  BinaryTree<T> right = new BinaryTree<>(oldRoot.right);
  oldRoot.left = null;
  oldRoot.right = null;
  root = null;
  return new TreeParts<>(oldRoot.element, left, right);
}

breakTree(…) 拆出根元素和左右子树，使原树清空而结点关系仍由返回结果保留。

空树没有可拆出的根和左右子树，因此必须在任何所有权变更前拒绝操作。

先把旧根的左右入口分别交给两个新的 BinaryTree；这一步只是重新指定拥有者，并没有复制节点。

断开旧根与两棵子树，再把原树入口清空；返回值于是包含根元素和两个独立子树，原树不再拥有任何节点。

遍历

二叉树遍历

遍历的核心问题是：根结点相对左、右子树，什么时候访问？ 先序是“根→左→右”，中序是“左→根→右”，后序是“左→右→根”；层序不按递归子树，而是按距离根的层次推进。

递归先序遍历

先用同一棵具体树走一遍调用栈。重点看：进入一个非空结点时立刻访问，然后才递归左右子树。

递归先序代码

五行正好对应“空就返回 → 访问根 → 左 → 右”。

void preorder(BinaryNode<T> node) {
  if (node == null) {
    return;
  }
  output.add(node.element);
  preorder(node.left);
  preorder(node.right);
}

preorder(…) 按“根→左→右”访问每个结点；递归边界只在空子树处停止。

空子树对先序序列没有贡献；这个基本情形同时保证递归会在叶子下面停止。

非空子树先输出根，因此当前根一定早于自己的全部后代出现，这就是“先序”最关键的顺序约束。

根处理完后再依次递归左、右子树；两个子问题沿用同一规则，最终得到完整的“根→左→右”序列。

递归中序遍历

中序最容易混淆，因为进入结点时不能马上访问。必须先把左子树处理完，返回到当前结点后才访问它。

递归中序代码

visit(node) 恰好夹在两次递归之间。

void inorder(BinaryNode<T> node) {
  if (node == null) {
    return;
  }
  inorder(node.left);
  output.add(node.element);
  inorder(node.right);
}

inorder(…) 按“左→根→右”访问；对二叉搜索树（Binary Search Tree，BST）而言输出顺序就是关键字升序。

空子树对中序序列没有贡献；基本情形让递归在叶子下面停止，不引入任何额外元素。

非空节点严格执行“左子树→根→右子树”；根被夹在两次递归之间，这个相对位置就是中序遍历的定义。

递归后序遍历

后序与先序正好相反：当前结点要一直等到左右子树都处理完才访问，因此特别适合“先得到孩子结果，再计算父结点”的问题。

递归后序代码

visit(node) 放在两次递归之后。

void postorder(BinaryNode<T> node) {
  if (node == null) {
    return;
  }
  postorder(node.left);
  postorder(node.right);
  output.add(node.element);
}

postorder(…) 按“左→右→根”访问；父结点只在两个子树都处理完以后出现。

空子树直接结束，不向结果贡献元素；这个基本情形保证递归在叶子下面停止。

非空节点先递归左右子树，最后才访问根；父节点因此晚于全部后代出现，正适合“先算孩子、再汇总父节点”的任务。

层序遍历

层序不靠递归，而是靠队列保持“这一层先于下一层”。先看队列如何随访问过程变化：

层序遍历代码

重复执行：出队一个结点、访问、把非空孩子接到队尾。

void levelOrder(BinaryNode<T> root) {
  if (root == null) {
    return;
  }
  Deque<BinaryNode<T>> queue = new ArrayDeque<>();
  queue.offer(root);
  while (!queue.isEmpty()) {
    BinaryNode<T> node = queue.poll();
    output.add(node.element);
    if (node.left != null) {
      queue.offer(node.left);
    }
    if (node.right != null) {
      queue.offer(node.right);
    }
  }
}

levelOrder(…) 用队列按层访问结点；孩子只在父结点出队后加入后续待访问集合。

空树直接结束；非空时只把根放入先进先出队列，建立“已发现但尚未访问”的初始待访问集合。

每轮只取队头并输出它；先进先出规则保证更早发现、也就是更浅层的节点总会先被访问。

存在左孩子时先把它接到队尾；同一父节点的左右顺序因此固定为从左到右。

右孩子随后入队，但仍排在当前层其他已发现节点之后；队列顺序因此自然维持逐层扩展。

非递归中序遍历

递归版其实一直在借用系统调用栈。非递归版只是把这件事显式写出来：stack 保存“已经走到、但要等左子树完成后才能访问”的结点。

非递归中序代码

能向左就压栈；走到空以后弹栈访问，再转向右子树。

void inorderIterative(BinaryNode<T> root) {
  Deque<BinaryNode<T>> stack = new ArrayDeque<>();
  BinaryNode<T> current = root;
  while (current != null || !stack.isEmpty()) {
    while (current != null) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    output.add(current.element);
    current = current.right;
  }
}

inorderIterative(…) 用显式栈保存尚未访问的祖先，模拟递归中序遍历的返回路径。

显式栈承担递归调用栈的职责；current 指向正在继续向左探索的子树入口。

只要还能向左，就把当前节点压栈后继续左移；栈中的节点都是“左子树尚未完成，因此自己还不能访问”的暂停现场。

走到空链接后弹出最近暂停的节点并访问，再转向它的右子树；这一“左到底→根→右”的循环与递归中序完全等价。

树高

树高也是一个典型的“先得到孩子结果，再计算父结点”的递归问题，所以计算顺序本质上是后序的。

树高代码

空树取 -1 后，叶结点会自然得到 0。

static <T> int height(BinaryNode<T> node) {
  if (node == null) {
    return -1;
  }
  return 1 + Math.max(height(node.left), height(node.right));
}

height(…) 返回子树高度；空树给出基值，非空结点取两个孩子高度的较大者再加 1。

约定空树高度为 -1，递归边界就与“叶子高度为 0”自然衔接，不需要额外判断叶节点。

非空树必须等左右子树高度都算完，再取较大者加 1；因此树高计算本质上是一次后序式的自底向上汇总。

由遍历重建

由先序和中序构造二叉树：问题是什么

现在把遍历问题反过来：树已经丢了，只剩两条遍历序列，能不能把原来的树恢复出来？

已知同一棵二叉树的：

先序：A B D E C F G
中序：D B E A F C G

要求恢复每个结点的左右孩子关系。难点在于：序列里只有访问顺序，没有任何括号或指针告诉我们“哪一段属于左子树、哪一段属于右子树”。

为什么“先序 + 中序”足够

先序：A B D E C F G
中序：D B E A F C G

先序和中序分别提供了什么：

先序的第一个元素一定是当前子树的根。 所以这里根只能是 A。
在中序里找到根，就能把结点集合切成左、右两部分。 D B E | A | F C G，所以左子树只可能由 D B E 构成，右子树只可能由 F C G 构成。
左子树有 3 个结点，因此先序中根 A 后面的前 3 个元素 B D E 必须属于左子树；剩余 C F G 属于右子树。
对左右两段重复同样的问题，原问题就变成两个更小的同类问题。

所以真正的递归依据是：先序负责找根，中序负责切边界，左子树大小负责把先序也切成两段。

具体执行：一步一步恢复结构

当前递归子问题的 Pre / In 两段，以及这一轮如何确定根和左右范围。

构造算法：代码如何对应递归切分

代码只是在机械地实现刚才的三个信息：根在哪里、左子树有多大、左右递归区间分别是什么。

static BinaryNode<Character> build(String preorder, String inorder) {
  Objects.requireNonNull(preorder, "preorder");
  Objects.requireNonNull(inorder, "inorder");
  if (preorder.length() != inorder.length()) {
    throw new IllegalArgumentException("traversals must have the same length");
  }
  if (preorder.isEmpty()) {
    return null;
  }

  Map<Character, Integer> inorderIndex = new HashMap<>();
  for (int i = 0; i < inorder.length(); i++) {
    if (inorderIndex.put(inorder.charAt(i), i) != null) {
      throw new IllegalArgumentException("keys must be unique");
    }
  }
  return build(preorder, 0, preorder.length() - 1, 0, inorder.length() - 1, inorderIndex);
}

private static BinaryNode<Character> build(
    String preorder,
    int preLeft,
    int preRight,
    int inLeft,
    int inRight,
    Map<Character, Integer> inorderIndex) {
  if (preLeft > preRight) {
    return null;
  }
  char rootValue = preorder.charAt(preLeft);
  Integer split = inorderIndex.get(rootValue);
  if (split == null || split < inLeft || split > inRight) {
    throw new IllegalArgumentException("inconsistent traversals");
  }
  int leftSize = split - inLeft;
  BinaryNode<Character> root = new BinaryNode<>(rootValue);
  root.left = build(
      preorder, preLeft + 1, preLeft + leftSize, inLeft, split - 1, inorderIndex);
  root.right = build(
      preorder, preLeft + leftSize + 1, preRight, split + 1, inRight, inorderIndex);
  return root;
}

build(…) 根据遍历序列确定根并递归划分左右子树，重建出的边界必须与序列位置一致。

两条遍历必须等长；空序列直接对应空树。先排除这两类全局边界，后面的切分才有一致的节点集合。

中序位置必须唯一，才能把每个根精确切成左右两侧；建立索引后，递归查根位置从线性扫描降为常数时间。

递归子问题由一对闭区间定义；先序区间为空时，这一支就是空子树，不再继续切分。

当前先序首元素确定根；它在中序中的位置必须落在当前区间内，否则两条遍历无法描述同一棵树。

leftSize 把中序切分转换成先序长度；左右递归因此拿到同一批节点，返回后再接到当前根即可。

哪些序列能唯一构造

下面结论默认所有结点关键字唯一。如果允许重复关键字，而又没有额外的结点身份信息，即使带中序也可能无法唯一定位根的位置。

已知序列	是否唯一	真正提供的信息
先序 + 中序	是	先序给根；中序切左右子树
后序 + 中序	是	后序给根；中序切左右子树
先序 + 后序	通常否	都能给根，但通常不能判断单个孩子在左还是右
层序 + 中序	是	层序先给当前根；中序切分后再按结点归属过滤左右层序

例 1：先序 + 中序为什么唯一

继续沿用前一页已经恢复出的那棵树，直接检查两条序列如何把结构唯一确定：

Pre = A B D E C F G：第一个 A 唯一确定根。
In = D B E | A | F C G：A 左边只能属于左子树，右边只能属于右子树。
左边有 3 个结点，因此先序中 A 后面的 3 个元素只能是左子树的 B D E。

例 2：后序 + 中序为什么也唯一

对同一棵树：

Post = D E B F G C A
In = D B E A F C G

后序与先序只是在“根在哪里”这一点不同：后序最后一个元素一定是当前根，所以这里先确定 A。

在中序中仍然得到：

D B E | A | F C G

因此左子树结点集合是 {D,B,E}，右子树是 {F,C,G}。再到后序中按这两个集合切分：

D E B | F G C | A

左段最后一个 B 是左子树根，右段最后一个 C 是右子树根，递归继续，结构仍然唯一。

反例：先序 + 后序为什么通常不唯一

只要两个结点就足够构造反例。已知：

Pre = A B
Post = B A

下面两棵树的两条序列完全相同：

树 1：B 是左孩子

      A
     /
    B

A.left = B，A.right = null

树 2：B 是右孩子

      A
       \
        B

A.left = null，A.right = B

先序只能告诉我们 A 在 B 前面，后序只能告诉我们 B 在 A 前面；两条序列都没有提供信息说明 B 到底是 A 的左孩子还是右孩子。

所以“先序 + 后序通常不能唯一构造”不是口诀，而是因为它们缺少像中序那样的左右分界信息。

例 4：层序 + 中序为什么唯一

同一棵树的序列为：

Level = A B C D E F G
In = D B E A F C G

层序的第一个元素 A 是整棵树的根。中序按 A 切开：

左子树结点集合 {D,B,E}
右子树结点集合 {F,C,G}

然后不需要猜连续区间，而是按集合过滤剩余层序：

从 B C D E F G 中保留左集合 → B D E
保留右集合 → C F G

于是左子树的层序首元素 B、右子树的层序首元素 C 又分别成为两个子问题的根；配合各自的中序区间继续递归，结构唯一。

树和森林转二叉树

普通树的长子兄弟表示

普通树的问题是：一个结点可能有很多孩子，而普通二叉结点只有两个指针。长子兄弟表示把它们重新解释为 firstChild（进入自己的第一个孩子）和 nextSibling（移动到同一父结点的下一个兄弟），也就是：左边深入孩子，右边沿兄弟移动。

长子兄弟表示代码

static class TreeNode<T> {
  T element;
  TreeNode<T> firstChild;
  TreeNode<T> nextSibling;

  TreeNode(T element) {
    this.element = element;
  }
}

TreeNode 保存结点元素和孩子集合，用引用关系表达一般树的层级结构。

任意度数的树只需两个方向：firstChild 进入自己的孩子链，nextSibling 沿同一父节点的兄弟链前进；因此每个节点仍只需要两个引用。

TreeNode(element) 创建一个尚未接入孩子链或兄弟链的新结点；两个结构链接都从空状态开始。

新节点先保存自身元素，两个结构链接默认为空；之后接孩子或兄弟时只需改变对应入口，不改变这种“孩子/兄弟”解释。

树转二叉树

把长子兄弟结点直接改名即可得到二叉树表示：

普通树语义	二叉树语义
`firstChild`	`left`
`nextSibling`	`right`

例如 A 的第一个孩子是 B，所以 A.left = B；B、C、D 原来是兄弟，所以二叉表示中形成 B.right = C、C.right = D。

这个转换不改变结点集合，只改变边的解释方式。

森林转二叉树

森林可以看作若干棵树的根互为兄弟。

转换规则：

每棵树先转成孩子兄弟二叉树
第一棵树的根作为二叉树根
其余树的根沿右孩子链连接

森林遍历可以转化为二叉树遍历。

普通树遍历

先根遍历：

访问根
依次先根遍历每棵子树

后根遍历：

依次后根遍历每棵子树
访问根

广度优先遍历使用队列。

结构扩展

线索二叉树动机

含 \(n\) 个结点的二叉链表有 \(2n\) 个孩子指针域。

实际边数只有 \(n-1\)。

因此空指针数为：

\[ 2n-(n-1)=n+1 \]

线索二叉树用这些空指针保存遍历序列中的前驱或后继。

中序线索树

中序线索树中：

若 left == null，可让 left 指向中序前驱
若 right == null，可让 right 指向中序后继
需要额外标志位区分孩子指针和线索

线索结点代码

enum Tag { CHILD, THREAD }

static class ThreadNode<T> {
  T element;
  ThreadNode<T> left;
  ThreadNode<T> right;
  Tag leftTag = Tag.CHILD;
  Tag rightTag = Tag.CHILD;

  ThreadNode(T element) {
    this.element = element;
  }
}

Tag 只有 CHILD 与 THREAD 两种取值，用来明确一个引用当前表示真实孩子还是中序线索。

ThreadNode 用标记区分真实孩子与线索，使空链接能够保存遍历前驱/后继。

left/right 不再只表示孩子：每个方向都配一个标记，明确当前引用究竟是 CHILD 还是中序 THREAD；没有标记就无法安全区分两种语义。

ThreadNode(element) 创建一个尚未线索化的结点；左右链接为空且两个标记初始都按真实孩子语义解释。

新节点默认把两个方向都解释为真实孩子；只有在线索化时才把空孩子引用改作前驱/后继，并同步把对应标记改成 THREAD。

中序线索遍历

线索化以后，中序遍历只需要两个动作：first(p) 沿真正的左孩子一直走到当前子树中序序列的第一个结点；next(p) 若右指针是线索就直接到后继，否则进入右子树再找 first。因此遍历从 p = first(root) 开始，再不断执行 p = next(p)。

static <T> ThreadNode<T> first(ThreadNode<T> node) {
  if (node == null) {
    return null;
  }
  while (node.leftTag == Tag.CHILD && node.left != null) {
    node = node.left;
  }
  return node;
}

static <T> ThreadNode<T> next(ThreadNode<T> node) {
  if (node == null) {
    return null;
  }
  if (node.rightTag == Tag.THREAD) {
    return node.right;
  }
  return first(node.right);
}

first(…) 返回线索二叉树中序序列的第一个结点，也就是不断沿真实左孩子到达的最左结点。

空子树没有中序首节点，因此 first 直接返回空；后续逻辑只处理真实节点。

沿 CHILD 类型的左引用一直下降；遇到 THREAD 或空左边时停止，此时当前节点就是该子树中序序列的第一个节点。

next(…) 根据右线索或右子树最左结点找到中序后继，不再依赖递归栈。

next 先看右引用语义：THREAD 直接给出后继；若右边是真实子树，后继就是那棵子树的 first。

Huffman 压缩编码

从文件压缩问题开始

一个文件按字节（byte）看，每个位置都有 256 种可能值。

如果什么都不利用，最直接的方法就是固定长度：

3529475 _2 256 = 8 3529475

但真实文件里的字节通常不是等概率出现。

于是自然的问题是：

经常出现的字节，能不能用更短的位（bit）串表示？

信息量：越少见，单次出现越“意外”

信息论里常用

\[ I(x)=-\log_2 p(x) \]

衡量一个事件的信息量。

若 \(p=1/2\)，信息量是 \(1\) 位
若 \(p=1/16\)，信息量是 \(4\) 位
越少见的符号，单次出现携带的信息越多

平均信息量称为熵：

\[ H(X)=-\sum_x p(x)\log_2p(x) \]

它提示了一个方向：码长应该接近 \(-\log_2p(x)\) 。

变长编码不能随便分配

假设直接规定：

A -> 0
B -> 01

那么看到位串 01 时，开头的 0 到底是完整的 A，还是 B 的开头？

所以变长编码必须保证：

任何一个码字都不是另一个码字的前缀。

把所有符号放在二叉树的叶子上，就会天然得到前缀码（prefix-free code）：左边记 0，右边记 1，根到叶子的路径就是码字。

那到底该多短？看它有多频繁

设符号 \(i\) 的出现次数为 \(w_i\)，码长为 \(l_i\)。

压缩后总位数正比于：

\[ \sum_i w_i l_i \]

在树上，\(l_i\) 就是叶子深度，因此得到带权外路径长度：

\[ WPL=\sum_i w_i l_i \]

这不是“让树尽量矮”，而是：

让高频叶子尽量靠近根，让低频叶子承担更深的路径。

Huffman 算法会自动完成这种分配。

从 256 个字节频率建 Huffman 树

每一轮都做同一件事：取当前权值最小的两棵树 → 合并 → 新根权值求和 → 按权值重新插回候选表。

Huffman 算法

static HuffmanNode buildHuffman(int[] weights) {
  PriorityQueue<HuffmanNode> queue = new PriorityQueue<>(
      Comparator.comparingLong((HuffmanNode node) -> node.weight)
          .thenComparingInt(node -> node.order));
  int nextOrder = 0;
  for (int weight : weights) {
    if (weight <= 0) {
      throw new IllegalArgumentException("weight must be positive");
    }
    queue.offer(new HuffmanNode(weight, nextOrder++, null, null));
  }
  while (queue.size() > 1) {
    HuffmanNode left = queue.remove();
    HuffmanNode right = queue.remove();
    queue.offer(new HuffmanNode(
        left.weight + right.weight, nextOrder++, left, right));
  }
  return queue.poll();
}

buildHuffman(…) 反复合并当前权值最小的两棵树，直到得到总代价最小的 Huffman 树。

优先队列始终按权重取最小候选；order 只在权重相同时稳定打破平局，不改变 Huffman “选两个最小权重”的贪心准则。

每个正权重先成为一棵单节点树；此时队列中的每个元素都代表一棵尚未与其他候选合并的 Huffman 子树。

每轮取出权重最小的两棵树，用权重和建立新父节点再放回队列，候选数恰好减少 1；只剩一个候选时，它就包含全部叶子并成为最终根。

频率、信息量与 Huffman 码长

符号	Huffman 编码	码长（位）	频率	信息量（位）
`0x20 space`	`00`	2	0.1979	2.34
`0x65 e`	`100`	3	0.1302	2.94
`0x74 t`	`010`	3	0.0969	3.37
`0x61 a`	`1111`	4	0.0854	3.55
`0x6F o`	`1110`	4	0.0792	3.66
`0x6E n`	`1101`	4	0.0740	3.76
`0x69 i`	`1011`	4	0.0708	3.82
其余 249 种	-	9–12	0.0001–0.0011	9.77–13.23

\(I(x)=-\log_2 p(x)\)；频率越高 → 信息量越小 → Huffman 码通常越短。

0/1 的具体写法可随左右子树交换而变化，真正关键的是码长。

Huffman 已经是最优了吗？

对已知符号概率、逐符号、二进制前缀码，Huffman 是最优的。

但这个“最优”有明确边界：

码长必须是整数个二进制位
每个符号单独分配一个前缀码
概率模型通常被当作固定分布

如果允许一次编码一段符号，或者让概率随上下文（context）改变，就可能进一步逼近熵极限（entropy limit）。

例子：现代视频编码

现代视频编码通常先做：

帧内 / 帧间预测 → 变换与量化 → 概率建模 → 熵编码（entropy coding）

最后常用算术编码（arithmetic coding）或区间编码（range coding）一类方法；上下文自适应编码（context-adaptive coding）还会让概率随上下文变化。

核心变化是：先去掉可预测结构，再编码剩余不确定性。

更进一步：基于模型预测的视频压缩

如果编码器（encoder）有一个学习得到的预测模型，就可以根据已经看到的内容预测：

\(p(x_t\mid \text{上下文})\)

那么每个位置都可以使用不同的概率分布。

一个典型流程是：

\(\text{预测 / 运动补偿}\rightarrow p(x_t\mid \text{上下文})\rightarrow \text{算术 / 区间编码器}\rightarrow \text{码流}\)

这时真正决定压缩率的，不只是“选哪种编码”，而是：

概率模型预测得有多准，剩下的不确定性就有多小。

Huffman 仍然非常重要，因为它把“频率决定码长”的核心思想讲得最清楚；现代压缩系统则把这个思想推广到了更细粒度、更动态的概率模型。

本章小结

普通树和二叉树都刻画层级关系；区别在于孩子数量、孩子次序和递归子结构约束。
根、父子、兄弟、叶、度、层次和高度是描述树结构与推导性质的基本语言。
二叉树性质连接结点数、叶结点数和高度；完全二叉树还能用数组下标直接定位父子关系。
链式、数组和游标表示分别强调指针灵活性、位置公式和静态存储模拟。
先序、中序、后序和层序遍历对应不同访问时机，递归和队列实现反映不同控制顺序。
由先序+中序或后序+中序重建二叉树时，根的位置把序列稳定切分为左右子树。
树、森林与二叉树的转换使用长子兄弟表示，把多叉层级转成二叉结构。
线索二叉树利用空指针保存遍历后继，Huffman 树利用权值频率构造短平均码长。

下载本章完整 Gradle 工程

本章习题

习题 1：叶结点公式：题目：证明二叉树中 \(n0=n2+1\)。
习题 2：完全二叉树最大结点数：题目：完全二叉树第 6 层有 8 个叶结点，根为第 1 层，结点数最多是多少？
习题 3：树的叶结点数：题目：一棵度为 4 的树中，度为 4、3、2、1 的结点数分别为 20、10、1、10，求叶结点数。
习题 4：递归统计叶结点：编写递归算法统计一棵二叉树的叶结点数，并分析时间复杂度。
习题 5：交换左右子树：编写递归算法交换二叉树中每个结点的左右子树，并说明执行后的结构含义。
习题 6：Huffman 性质判断：判断题目给出的 Huffman 树性质哪些必然成立，并逐条说明理由。

致谢

谢谢

sqlite@nju.edu.cn
https://slab-nju.cn

石守谦

第 4.0 章 树

引入