梳理树的基本术语、性质和常见存储结构,掌握孩子兄弟表示法以及树、森林与二叉树之间的转换和遍历关系。

# 一、树的基本概念

树是 nn 个结点组成的有限集合。当 n=0n=0 时为空树;当 n>0n>0 时有且仅有一个根结点,其余结点分成若干个互不相交的子集,每个子集本身又是一棵树,称为根的子树。树中不存在环,任意两个结点之间有且只有一条简单路径。

树与线性表的主要差别是:一个结点可以有多个孩子,除根结点外每个结点有且只有一个双亲。结点、边和层次关系可用下列术语描述。

术语含义
结点的度该结点的孩子数
树的度树中所有结点度的最大值
叶子结点度为 00 的结点,也称终端结点
分支结点度大于 00 的结点
祖先、子孙根到结点路径上的上层结点及其后代
兄弟具有相同双亲的结点
结点的深度从根到该结点经过的边数,根的深度为 00
结点的高度从该结点到最远叶子经过的边数,叶子的高度为 00

树的基本术语示意:以结点 D 展示双亲、孩子、兄弟、祖先、子孙、度、深度、高度与路径长度

有的教材把深度和高度按 “经过的结点数” 定义,此时上述数值整体相差 11。计算题必须先声明约定。整棵树的深度与高度都由根到最远叶子的最长路径确定,只是观察方向不同。

# 树的基本性质

若一棵树有 nn 个结点,则边数为

∣E∣=n−1.|E|=n-1.

这是因为除根结点外,每个结点恰有一条连接其双亲的边。对于度为 ii 的结点数记为 nin_i 的树,还有

n=∑i≥0ni,n−1=∑i≥1ini.n=\sum_{i\ge0}n_i,\qquad n-1=\sum_{i\ge1} i n_i.

第二式表示所有结点的孩子数之和等于边数。树的度为 mm 时,每个结点最多有 mm 个孩子;若树是有序树,孩子之间的左右次序也属于结构的一部分。

# 二、树的存储结构

一般树的结点孩子数不固定,常见表示方式各有取舍。

存储方式结点主要信息适用特点
双亲表示法每个结点保存双亲下标找双亲方便,找所有孩子需扫描
孩子表示法每个结点维护孩子链表遍历孩子方便,找双亲通常较慢
孩子兄弟表示法保存第一个孩子和下一个兄弟结点字段固定,可将树映射为二叉链表

同一棵有序树的双亲表示法、孩子表示法和孩子兄弟表示法

孩子兄弟表示法的结点可写为:

1
2
3
4
5
typedef struct CSNode {
int data;
struct CSNode *firstChild;
struct CSNode *nextSibling;
} CSNode;

firstChild 指向本结点的第一个孩子,nextSibling 指向同一双亲的下一个孩子。若按有序树从左到右排列孩子,这种表示保留了孩子次序。

# 三、树、森林与二叉树的转换

孩子兄弟表示法给出树与二叉树之间的对应关系:

  1. 树中每个结点的第一个孩子成为对应二叉树结点的左孩子。
  2. 同一双亲的下一个兄弟成为对应二叉树结点的右孩子。
  3. 删除一般树中的根到各孩子的连接后,森林中各棵树的根按原顺序作为同一二叉树根的右兄弟链。
  4. 从二叉树恢复森林时,根的右链依次给出森林各树的根;每棵树内部仍按左孩子、右兄弟解释。

树与森林转换为二叉树:第一个孩子映射为左孩子,后续兄弟及森林树根映射为右链接

转换时容易混淆的是 “右孩子” 和 “右兄弟”:在孩子兄弟表示法中,右指针保存的是下一个兄弟,不是原树中双亲的第二个直接孩子关系以外的新层级。

# 四、树和森林的遍历

对于有序树,常见遍历定义如下。

  • 先根遍历:先访问根,再按次序遍历各子树。
  • 后根遍历:先按次序遍历各子树,最后访问根。
  • 层序遍历:从根开始逐层访问,同层结点按次序处理;可用队列实现。

同一棵树的先根与后根遍历顺序,结点旁数字表示访问次序

森林的先根遍历依次处理每棵树;后根遍历则先处理一棵树的子树和根,再处理下一棵树。采用孩子兄弟二叉树表示时,树的先根遍历对应二叉树先序遍历,后根遍历对应二叉树中序遍历;森林的先根、后根遍历也分别对应转换后二叉树的先序、中序遍历。这个对应关系依赖 “左链接表示第一个孩子、右链接表示下一个兄弟” 的约定。

# 五、考场检查清单

  1. 树中除根外每个结点恰有一个双亲,nn 个结点有 n−1n-1 条边。
  2. 结点的度是孩子数;无向图中的顶点度则是关联边数。
  3. 树高和结点深度的定义有 “边数” 与 “结点数” 两种口径,题目中要统一。
  4. 孩子兄弟表示法中,左指针指第一个孩子,右指针指下一个兄弟。
  5. 森林转换为二叉树时,各棵树的根形成右兄弟链。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝