5.1 树的基本概念

树的递归定义、基本术语，以及结点数、度、高度之间的数量关系。

考查要求 ★★☆ 理解树的定义度与高度结点数与度的关系m 叉树性质

树的定义

显然，树的定义是递归的——树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

因此 $n$ 个结点的树中有 $n - 1$ 条边。

在下面的树中点击任意结点，观察它的各项属性：

交互演示树的基本术语——点击任意结点

树的度 = 3，树的高度 = 4，结点数 = 13，叶子数 = 7

选中结点祖先子孙兄弟

结点 D 的信息

术语	含义
祖先 / 子孙	从根到结点 K 的唯一路径上的任意结点都是 K 的祖先；K 是它们的子孙
双亲 / 孩子	路径上最接近 K 的结点 E 称为 K 的双亲，K 为 E 的孩子
兄弟 / 堂兄弟	有相同双亲的结点称为兄弟；双亲在同一层的结点互为堂兄弟
结点的度	树中一个结点的孩子个数
树的度	树中结点的最大度数
分支结点 / 叶结点	度大于 0 的结点称为分支结点（非终端结点）；度为 0 的结点称为叶结点（终端结点）
层次	从树根开始定义，根结点为第 1 层，它的子结点为第 2 层……
深度 / 高度	结点的深度是从根结点开始自顶向下逐层累加的；结点的高度是从叶结点开始自底向上逐层累加的；树的高度（深度）是树中结点的最大层数
有序树 / 无序树	结点的各子树从左到右是有次序的、不能互换，称为有序树，否则称为无序树
路径 / 路径长度	两个结点之间的路径是由它们之间所经过的结点序列构成的；路径长度是路径上所经过的边的个数
森林	$m$ （ $m \ge 0$ ）棵互不相交的树的集合

性质 1 是解题的”万能钥匙”。设树中度为 $i$ 的结点有 $n_i$ 个，则：

\begin{aligned} n &= n_0 + n_1 + n_2 + \cdots + n_m &\text{（按度数分类）}\\ n &= 1 \cdot n_1 + 2 \cdot n_2 + \cdots + m \cdot n_m + 1 &\text{（总度数 + 1）} \end{aligned}

联立即可求出任意未知量。

例题

在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是多少？

查看解答

总结点数 $n = n_0 + 20 + 10 + 1 + 10 = n_0 + 41$ ；又 $n = 4 \times 20 + 3 \times 10 + 2 \times 1 + 1 \times 10 + 1 = 123$ 。所以 $n_0 = 123 - 41 = 82$ 。

即时练习4 题

点击选项即可作答

学完了吗？

标记完成后，侧栏会显示进度。进度仅保存在本浏览器中。