梳理树的基本术语、性质和常见存储结构,掌握孩子兄弟表示法以及树、森林与二叉树之间的转换和遍历关系。
# 一、树的基本概念
树是 个结点组成的有限集合。当 时为空树;当 时有且仅有一个根结点,其余结点分成若干个互不相交的子集,每个子集本身又是一棵树,称为根的子树。树中不存在环,任意两个结点之间有且只有一条简单路径。
树与线性表的主要差别是:一个结点可以有多个孩子,除根结点外每个结点有且只有一个双亲。结点、边和层次关系可用下列术语描述。
| 术语 | 含义 |
|---|---|
| 结点的度 | 该结点的孩子数 |
| 树的度 | 树中所有结点度的最大值 |
| 叶子结点 | 度为 的结点,也称终端结点 |
| 分支结点 | 度大于 的结点 |
| 祖先、子孙 | 根到结点路径上的上层结点及其后代 |
| 兄弟 | 具有相同双亲的结点 |
| 结点的深度 | 从根到该结点经过的边数,根的深度为 |
| 结点的高度 | 从该结点到最远叶子经过的边数,叶子的高度为 |
有的教材把深度和高度按 “经过的结点数” 定义,此时上述数值整体相差 。计算题必须先声明约定。整棵树的深度与高度都由根到最远叶子的最长路径确定,只是观察方向不同。
# 树的基本性质
若一棵树有 个结点,则边数为
这是因为除根结点外,每个结点恰有一条连接其双亲的边。对于度为 的结点数记为 的树,还有
第二式表示所有结点的孩子数之和等于边数。树的度为 时,每个结点最多有 个孩子;若树是有序树,孩子之间的左右次序也属于结构的一部分。
# 二、树的存储结构
一般树的结点孩子数不固定,常见表示方式各有取舍。
| 存储方式 | 结点主要信息 | 适用特点 |
|---|---|---|
| 双亲表示法 | 每个结点保存双亲下标 | 找双亲方便,找所有孩子需扫描 |
| 孩子表示法 | 每个结点维护孩子链表 | 遍历孩子方便,找双亲通常较慢 |
| 孩子兄弟表示法 | 保存第一个孩子和下一个兄弟 | 结点字段固定,可将树映射为二叉链表 |
孩子兄弟表示法的结点可写为:
1 | typedef struct CSNode { |
firstChild 指向本结点的第一个孩子,nextSibling 指向同一双亲的下一个孩子。若按有序树从左到右排列孩子,这种表示保留了孩子次序。
# 三、树、森林与二叉树的转换
孩子兄弟表示法给出树与二叉树之间的对应关系:
- 树中每个结点的第一个孩子成为对应二叉树结点的左孩子。
- 同一双亲的下一个兄弟成为对应二叉树结点的右孩子。
- 删除一般树中的根到各孩子的连接后,森林中各棵树的根按原顺序作为同一二叉树根的右兄弟链。
- 从二叉树恢复森林时,根的右链依次给出森林各树的根;每棵树内部仍按左孩子、右兄弟解释。
转换时容易混淆的是 “右孩子” 和 “右兄弟”:在孩子兄弟表示法中,右指针保存的是下一个兄弟,不是原树中双亲的第二个直接孩子关系以外的新层级。
# 四、树和森林的遍历
对于有序树,常见遍历定义如下。
- 先根遍历:先访问根,再按次序遍历各子树。
- 后根遍历:先按次序遍历各子树,最后访问根。
- 层序遍历:从根开始逐层访问,同层结点按次序处理;可用队列实现。
森林的先根遍历依次处理每棵树;后根遍历则先处理一棵树的子树和根,再处理下一棵树。采用孩子兄弟二叉树表示时,树的先根遍历对应二叉树先序遍历,后根遍历对应二叉树中序遍历;森林的先根、后根遍历也分别对应转换后二叉树的先序、中序遍历。这个对应关系依赖 “左链接表示第一个孩子、右链接表示下一个兄弟” 的约定。
# 五、考场检查清单
- 树中除根外每个结点恰有一个双亲, 个结点有 条边。
- 结点的度是孩子数;无向图中的顶点度则是关联边数。
- 树高和结点深度的定义有 “边数” 与 “结点数” 两种口径,题目中要统一。
- 孩子兄弟表示法中,左指针指第一个孩子,右指针指下一个兄弟。
- 森林转换为二叉树时,各棵树的根形成右兄弟链。
