5.2 二叉树的概念与存储

二叉树的定义与五种形态，满二叉树、完全二叉树等特殊二叉树，二叉树的性质，以及顺序与链式存储。

二叉树的定义

二叉树也以递归的形式定义：二叉树是 $n$（$n \ge 0$）个结点的有限集合，或者为空二叉树；或者由一个根结点和两个互不相交的、被称为根的左子树和右子树组成，左子树和右子树又分别是一棵二叉树。

二叉树有五种基本形态：

几种特殊的二叉树

1. 满二叉树：一棵高度为 $h$，且有 $2^h - 1$ 个结点的二叉树，即树中的每层都含有最多的结点。满二叉树的叶结点都集中在二叉树的最下一层，并且除叶结点之外的每个结点度数均为 2。
2. 完全二叉树：高度为 $h$、有 $n$ 个结点的二叉树，当且仅当其每个结点都与高度为 $h$ 的满二叉树中编号为 $1 \sim n$ 的结点一一对应时，称为完全二叉树。
3. 二叉排序树：左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左右子树又各是一棵二叉排序树（见第 7 章）。
4. 平衡二叉树：树上任意一个结点的左子树和右子树的深度之差不超过 1（见第 7 章）。
5. 正则二叉树：树中每个分支结点都有 2 个孩子，即树中只有度为 0 或 2 的结点。

完全二叉树的特点

对满二叉树按层序编号：从根结点起（编号为 1），自上而下、自左向右。完全二叉树有如下特点：

• 若 $i \le \lfloor n/2 \rfloor$，则结点 $i$ 为分支结点，否则为叶结点；
• 叶结点只可能在层次最大的两层上出现，且最大层次中的叶结点都依次排列在该层最左边的位置上；
• 若有度为 1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子；
• 按层序编号后，一旦出现某结点（编号为 $i$）为叶结点或只有左孩子，则编号大于 $i$ 的结点均为叶结点；
• 若 $n$ 为奇数，则每个分支结点都有左孩子和右孩子；若 $n$ 为偶数，则编号最大的分支结点（编号为 $n/2$）只有左孩子，没有右孩子。

拖动滑块改变结点数，点击任意结点观察编号规律：

二叉树的性质

性质 1 的证明：设度为 0、1、2 的结点个数分别为 $n_0, n_1, n_2$，结点总数 $n = n_0 + n_1 + n_2$。再看分支数：除根结点外，其余结点都有一个分支进入，设 $B$ 为分支总数，则 $n = B + 1$；而这些分支是由度为 1 或 2 的结点射出的，所以 $B = n_1 + 2n_2$。于是 $n_0 + n_1 + n_2 = n_1 + 2n_2 + 1$，即 $n_0 = n_2 + 1$。

二叉树的存储结构

顺序存储

用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 $i$ 的结点元素存储在一维数组下标为 $i - 1$（或 $i$，若 0 号单元不用）的分量中。

• 完全二叉树和满二叉树采用顺序存储比较合适，既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系。
• 对于一般的二叉树，为了让数组下标能反映结点之间的逻辑关系，只能添加一些并不存在的空结点。在最坏情况下，一个高度为 $h$ 且只有 $h$ 个结点的单支树却需要占据近 $2^h - 1$ 个存储单元。

链式存储

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构。二叉链表至少包含 3 个域：数据域 data、左指针域 lchild 和右指针域 rchild。

typedef struct BiTNode {
    ElemType data;                       // 数据域
    struct BiTNode *lchild, *rchild;     // 左、右孩子指针
} BiTNode, *BiTree;

即时练习