树的基本概念

**树（Tree）**是 $n$ 个结点的有限集：

• $n = 0$：空树
• $n > 0$：有且仅有一个根结点，其余结点分成 $m$（$m \ge 0$）个互不相交的有限集，每个集合本身又是一棵树，称为根的子树

树描述的是层次关系：一个结点可以有多个孩子，但不能有多个双亲（相对图而言无环、弱连通的有向形态常用来画树）。

本文解决什么问题

• 树的基本术语（度、深度、高度、森林……）
• 常见存储表示
• 为什么后续重点先学二叉树

常用术语

术语	含义
双亲 / 孩子 / 兄弟	上下级与同级关系
结点的度	该结点孩子个数
树的度	树中结点度的最大值
叶子 / 终端结点	度为 0 的结点
分支结点	度不为 0 的结点
路径 / 路径长度	结点序列；边数常作为路径长度
深度	常从根往下数（根深度为 1 或 0，看约定）
高度	常从叶往上，或定义为树中结点深度最大值
有序树 / 无序树	孩子是否区分左右次序
森林	多棵互不相交的树

深度与高度

不同教材对「根的深度是 0 还是 1」「高度是否等于最大深度」约定不一致。读题或读文档时先对齐约定，再写代码。

树的性质（直觉）

• $n$ 个结点的树有 $n - 1$ 条边（把每个非根接到双亲）
• 结点越多、越「胖」或越「歪」，深度分布差很多——这会影响遍历与递归栈深度

常见存储表示

方法	思路
双亲表示法	数组存结点，记录双亲下标，找双亲快、找孩子慢
孩子表示法	每个结点挂孩子链表
孩子兄弟表示法	每个结点：第一个孩子 + 右兄弟指针；可把任意树转成二叉树形态

孩子兄弟法是「任意树 ↔ 二叉树」转换的常用桥梁：左指针当长子，右指针当兄弟。

为什么先学二叉树

1. 任意树可用孩子兄弟法转为二叉树讨论
2. 二叉树每个结点孩子数有上限，算法与存储更整齐
3. 大量经典结构建立在二叉树上：BST、AVL、堆、哈夫曼树……

因此本教程把篇幅集中在二叉树及其变体。

小结

抓住「根 + 若干互不相交子树」和基本术语。下一篇进入 二叉树。