有根树

概述

有根树（Rooted Tree） 是一种层次化的树形数据结构，每个节点有且仅有一个父节点（根节点除外）。有根树广泛用于表示层次关系，如文件系统目录、组织架构、语法分析树等。

定义

有根树（Rooted Tree）

有根树 $T$ 由节点集合和有向边集合构成，满足：

• 恰有一个节点 $r$ 称为根（root），没有父节点。
• 其余每个节点有且仅有一个父节点。
• 从根到任意节点有且仅有一条路径。

相关术语：

• 叶子（leaf）：无子节点的节点。
• 子节点（child）：若 $p$ 是 $c$ 的父节点，则 $c$ 是 $p$ 的子节点。
• 深度（depth）：从根到该节点的边数。
• 高度（height）：从该节点到其最深后代叶子的边数。

核心性质

二叉树表示法

二叉树（Binary Tree）

二叉树中每个节点最多有两个子节点：左子节点和右子节点。节点 $x$ 包含三个域：

• $x.parent$：指向父节点（根节点为 $\text{NIL}$）。
• $x.left$：指向左子节点（无左子节点为 $\text{NIL}$）。
• $x.right$：指向右子节点（无右子节点为 $\text{NIL}$）。

二叉树是 CLRS 中最常用的树表示法，二叉堆、二叉搜索树（BST）、红黑树等均基于此结构。

Left-Child Right-Sibling（LCRS）表示法

LCRS 表示

对于任意有根树（不限于二叉树），可用左子-右兄弟表示法将其转化为等价的二叉树结构。每个节点 $x$ 包含：

• $x.parent$：指向父节点。
• $x.left-child$：指向 $x$ 的第一个（最左）子节点。
• $x.right-sibling$：指向 $x$ 的紧邻右侧兄弟节点。

转换规则：对于每个节点的子节点列表，最左子节点成为 $left-child$，其余兄弟通过 $right-sibling$ 链接。

LCRS 示例：一般树（根有3个子节点 A, B, C）转换为二叉树后：

一般树:          LCRS 二叉树:
    root            root
   / | \              |
  A  B  C             A
                       \
                        B
                         \
                          C

表示法对比

特性	parent/left/right	LCRS
适用范围	二叉树	任意有根树
每节点指针数	3	3
空间效率	二叉树最优	任意树均可，无浪费
遍历子节点	直接访问 left/right	沿 right-sibling 链遍历
在 CLRS 中的使用	二叉堆、BST、红黑树	有根树的一般表示

树遍历基础

对有根树的遍历是许多树算法的基础操作：

• 先序遍历（Preorder）：访问根 → 递归遍历子树。
• 后序遍历（Postorder）：递归遍历子树 → 访问根。
• 中序遍历（Inorder）：仅适用于二叉树，左子树 → 根 → 右子树。

遍历的时间复杂度为 $O(n)$，其中 $n$ 为节点数。

章节扩展

第10章：树的表示

CLRS 第10.3节介绍了有根树的两种主要表示方法。二叉树的 parent/left/right 表示是后续章节中高级树结构（第12章二叉搜索树、第13章红黑树）的基础。LCRS 表示法则展示了如何用固定数量的指针统一表示任意分支度的树，体现了”用二叉树表示一般树”的核心思想。

有根树也是图论中树概念的特例——一棵有根树本质上是一棵无向树的某个节点被选为根后的定向版本。

参见

• 链表 — LCRS 表示中 right-sibling 指针本质上形成了一条链表
• 栈 — 树的深度优先遍历（DFS）使用栈（或递归调用栈）
• 队列 — 树的广度优先遍历（BFS）使用队列
• 二叉堆 — 基于数组实现的完全二叉树，对比指针表示与数组表示的取舍