树（Tree）

树是一种非线性的数据结构，它是以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的目录、现实生活中的家谱、公司的组织架构，以及编译器里的语法树。

和数组、链表这类“排成一列”的结构不同，树里的每个元素通常只有一个前驱（父节点），却可以有零个或多个后继（子节点）。这种一对多的关系，让它特别适合表达嵌套、从属、分支这类结构。

树的基本概念

一棵树由 节点（Node） 和连接节点的 边（Edge） 组成。下面是几个最常用的术语：

术语	含义
根节点（Root）	树的顶端，整棵树只有一个节点是没有父节点的，这个节点就是根节点
父节点 / 子节点	若 A 在 B 的上一层且直接相连，则 A 是 B 的父节点，B 是 A 的子节点
叶子节点（Leaf）	没有子节点的节点
子树（Subtree）	以某个节点为根，包含其所有后代的树
度（Degree）	一个节点拥有的子节点个数；树中所有节点的最大度，称为树的度
深度（Depth）	从根到该节点所经过的边数；根节点深度为 0
高度（Height）	从该节点到其子树最远叶子所经过的边数；整棵树的高度即根节点的高度

可以把树想象成倒置的组织架构图：老板在最上面是根，各级主管往下展开，最底层干活的员工往往是叶子节点。文件系统也类似：/ 是根，/home/user/docs 是从根到某个文件的一条路径。

路径是从一个节点到另一个节点所经过的节点序列；路径长度是路径上边的条数。树有一个重要性质：任意两个节点之间，路径唯一。不会出现图里那种“绕圈子”的情况——这也是树和图最根本的区别之一。

多叉树的表示法

多叉树在内存里怎么存，取决于你更常做哪种操作：找父节点、找孩子、还是按层遍历。

孩子链表（多叉树）

多叉树在代码里不好直接写“可变数量的指针”，经典做法是把任意多叉树转成二叉树： 每个节点保存一个指向第一个孩子的指针，同层兄弟再用链表串起来。这是表达多叉树最直接的方式，AST、文件系统目录树都常用类似思路。这种方式也被称为 左孩子右兄弟（Child-Sibling） 表示法。

struct TreeNode {
    int value;
    TreeNode* first_child;   // 第一个子节点
    TreeNode* next_sibling;  // 右兄弟
};

同一层的节点像链表一样挂在右指针上。LLVM、许多编译器 AST 都采用这种结构，详见 语法树模型的基本结构。

数组表示（完全二叉树）

若一棵二叉树除了最后一层外都是满的，且最后一层从左到右连续，则称为完全二叉树。它可以用数组紧凑存储：下标 i 的左孩子在 2i+1，右孩子在 2i+2，父节点在 (i-1)/2。堆（优先队列的底层结构）就经常用这种表示。

二叉树

二叉树（Binary Tree）是每个节点最多有两个子节点的树，通常称为左子树和右子树。即使某个孩子为空，概念上的“左/右”位置仍然保留——左右是有区别的，不能简单当成“有两个可选槽位”。

几种特殊二叉树：

类型	特点
满二叉树	每一层的节点数都达到该层能容纳的最大值
完全二叉树	除最后一层外满，最后一层从左到右填
二叉搜索树（BST）	左子树所有值 < 根 < 右子树所有值，中序遍历有序
平衡二叉树	左右子树高度差受限（如 AVL、红黑树），保证查找效率

树的遍历

遍历就是按某种顺序访问树中每个节点一次。二叉树最常见的遍历方式如下。

深度优先遍历

沿着一条路径尽量走深，再回溯。对二叉树有三种经典顺序，区别只在于根节点何时被访问：

遍历	顺序	记忆
前序（Pre-order）	根 → 左 → 右	先处理根
中序（In-order）	左 → 根 → 右	根在中间；BST 中序即升序
后序（Post-order）	左 → 右 → 根	根在最后；适合先处理子再处理父

深度优先一般用栈或递归实现——递归本质上就是系统帮你维护了调用栈。这与 栈 一章里“深度遍历时栈的变化”是同一套机制。

广度优先遍历

层序遍历（Level-order）从根开始，先访问同一层的所有节点，再访问下一层。实现上通常用队列：当前节点出队时，将其孩子按从左到右顺序入队。需要按层处理的问题（如打印每层节点、求树宽）很适合这种遍历。

二叉搜索树

二叉搜索树（Binary Search Tree，BST），也叫排序二叉树：对任意节点，左子树所有键值小于该节点，右子树所有键值大于该节点（通常不允许重复；若允许，需约定放左还是放右）。

在理想情况下，查找、插入、删除的平均时间复杂度都是 O(log n)——每次比较都能排除大约一半的子树。但如果插入顺序恰好是有序的（如依次插入 1, 2, 3, …, n），BST 会退化为一根链，复杂度变成 O(n)。工程上会用 AVL 树、红黑树等自平衡结构来避免这种极端情况。

BST 的核心操作思路：

• 查找：从根出发，比根小走左，比根大走右，直到找到或走到空指针
• 插入：按查找路径走到空位，在那里挂新节点
• 删除：分三种情况——叶子直接删；只有一个孩子则用孩子顶替；有两个孩子则一般用中序后继（或前驱）替换再删后继

树在编译中的应用

树可能是编译原理里出现频率最高的数据结构之一。

语法分析的结果往往是一棵语法树（Parse Tree）或更精简的抽象语法树（AST）。Flex 和 Bison 归约时，每个产生式对应一次“拼 subtree”；最终整份源程序被归约成开始符号那一棵大树。自顶向下分析从根开始展开，自底向上分析从叶子开始合并——详见 语法分析。

表达式天然是树形：1 + 2 * 3 中，* 的优先级更高，在树里位置更低；+ 在更高层把结果组合起来。语义分析、中间代码生成、优化，大多在这棵树上做遍历和改写。

控制流也可以树化或图化：if-else、循环嵌套形成层次；更完整的跳转关系则用 图 里的控制流图（CFG）表示——树擅长表达嵌套，图擅长表达跳转，二者经常配合使用。

DOM树是编译器中分析Domination关系的重要数据结构。父亲节点可以支配子节点，意味着所有到达子节点的路径，都必须经过父亲节点。这样就可以帮助我们快速决定一个节点中的变量，会被哪些结点中的变量修改所影响。

常见操作复杂度（参考）

操作	一般二叉树	二叉搜索树（平均）	二叉搜索树（最坏）
查找	O(n)	O(log n)	O(n)
插入	O(1)（已知父节点）	O(log n)	O(n)
删除	O(1)（已知节点）	O(log n)	O(n)
遍历全部节点	O(n)	O(n)	O(n)

这里的 n 是节点总数。实际选型时，除了复杂度，还要考虑是否需平衡、是否需顺序访问、内存布局是否友好等因素。

小结

树用分层、一对多的方式组织数据：有唯一的根，有清晰的路径，没有环。掌握基本术语、几种存储方式（孩子链表、左孩子右兄弟、数组堆式存储）以及遍历顺序（前/中/后序、层序），就能读懂大多数编译器前端和系统软件里的树形结构。更复杂的平衡树、B 树、Trie 等，都是在这一基础上为特定场景（查找、磁盘、字符串前缀）做的延伸。