树的定义与基本术语

树的定义

树（Tree） 是 $n$（$n \ge 0$）个结点的有限集合。当 $n = 0$ 时称为空树。在任意一棵非空树中：

1. 有且仅有一个特定的结点称为根（Root）。
2. 当 $n > 1$ 时，其余结点可分为 $m$（$m > 0$）个互不相交的有限集 $T_1, T_2, \dots, T_m$，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）。

基本术语

术语	英文	解释
结点	Node	树中的基本元素，包含数据项和指向子树的指针。
度	Degree	结点拥有的子树个数。树的度是树内各结点度的最大值。
叶子（终端结点）	Leaf	度为 0 的结点。
分支结点（非终端结点）	Branch Node	度大于 0 的结点。
孩子	Child	结点子树的根称为该结点的孩子。
双亲	Parent	该结点称为其孩子的双亲（父结点）。
兄弟	Sibling	同一双亲的孩子之间互称兄弟。
祖先	Ancestor	从根到该结点路径上的所有结点。
子孙	Descendant	以该结点为根的子树中的所有结点。
层次	Level	根为第 1 层，其孩子为第 2 层，依此类推。
深度（高度）	Depth / Height	树中结点的最大层次数。
森林	Forest	$m$（$m \ge 0$）棵互不相交的树的集合。

逻辑结构

树是一种非线性结构，结点之间存在一对多的关系，具有层次性。

存储结构

常用存储方式包括：

• 双亲表示法（数组）
• 孩子表示法（数组 + 链表）
• 孩子兄弟表示法（左孩子右兄弟，可转换为二叉树）

应用场景

• 文件系统目录结构
• 网页 DOM 树
• 编译器的语法树
• 数据库索引（B/B+ 树）