树与二叉树的基本概念

树

树（Tree）是 n（n≥0）个结点的有限集。n=0 时为空树。在任意一棵非空树中：

有且仅有一个根结点（root）
其余结点可分为 m（m>0）个互不相交的有限集 $T_1, T_2, \ldots, T_m$ ，每个集合本身又是一棵树，称为根的子树

树的常用术语

结点的度：结点拥有的子树个数
树的度：树内各结点度的最大值
叶子结点（终端结点）：度为 0 的结点
分支结点（非终端结点）：度大于 0 的结点
层次：根为第 1 层，根的孩子为第 2 层，依此类推
深度（高度）：结点的最大层次数
森林：m（m≥0）棵互不相交的树的集合

树的性质

树中的结点数等于所有结点的度数之和加 1
度为 m 的树中，第 i 层上至多有 $m^{i-1}$ 个结点（i≥1）
深度为 h 的 m 叉树至多有 $\frac{m^h-1}{m-1}$ 个结点

二叉树的定义

二叉树

二叉树（Binary Tree）是 n（n≥0）个结点的有限集，每个结点至多有两个孩子（左孩子、右孩子），且左右子树有严格的次序，不能颠倒。

二叉树的性质

非空二叉树的第 i 层上至多有 $2^{i-1}$ 个结点
深度为 h 的二叉树至多有 $2^h-1$ 个结点
对任意二叉树，叶子结点数 $n_0$ 与度为 2 的结点数 $n_2$ 满足： $n_0 = n_2 + 1$
具有 n 个结点的完全二叉树的深度为 $\lfloor \log_2 n \rfloor + 1$

性质 3（

n_0 = n_2 + 1

）是 408 常考结论。证明：设结点总数为 n，则

n = n_0 + n_1 + n_2

；又

n = B + 1

（B 为分支数），

B = n_1 + 2n_2

，联立得

n_0 = n_2 + 1

。

特殊二叉树

满二叉树：每层结点数都达到最大，叶子都在最底层
完全二叉树：除最后一层外每层都满，最后一层的结点都集中在左侧连续位置
二叉排序树（BST）：左子树所有结点值 < 根 < 右子树所有结点值
平衡二叉树（AVL）：任意结点左右子树高度差不超过 1

习题

习题 1

在一棵二叉树中，度为 2 的结点数为 5，则叶子结点数为（）

A. 4 B. 5 C. 6 D. 无法确定

答案与解析

答案：C

解析：由二叉树性质 $n_0 = n_2 + 1$ ，叶子结点数 = 5 + 1 = 6。

习题 2

简述树和二叉树的主要区别。

答案与解析

树：每个结点可以有任意多个孩子，结点的子树无左右之分（无序）。

二叉树：每个结点最多有两个孩子（左、右），且左右子树有严格的次序，不能颠倒。二叉树不是树的特殊情况，而是另一种独立的结构。

上一章节树与二叉树掌握树和二叉树的基本概念、存储结构、遍历方法及其应用。

下一章节存储结构二叉树的顺序存储与链式存储。