2.2.3 树和二叉树

1．树

树是一种常用的非线性结构。树是n(n≥0)个结点的有限集合。若n = 0，则称为空树，如图2-14(a)所示；否则，有且仅有一个特定的结点被称为根，n = 1时，如图2-14(b)所示，n>1时，其余结点被分成m(m>0)个互不相交的子集T₁，T₂，…，T_m，每个子集又是一棵树，如图2-14(c)所示。可以看出，树的定义是递归。

树结构包括以下基本概念。

☢ 结点：数据元素的内容及其指向其子树根的指针统称为结点。

☢ 结点的度：结点的分支数，或者说子树的数目。

☢ 终端结点（或叶子结点）：度为0的结点。

☢ 非终端结点（或非叶子结点）：度不为0的结点。

☢ 结点的层次：树中根结点的层次为1，根结点子树的根为第2层，以此类推。

☢ 树的度：树中所有结点度的最大值。

☢ 树的深度：树中所有结点层次的最大值。

☢ 森林：m(m≥0)棵互不相交的树的集合。

在树结构中，结点之间的关系又可以用家族关系描述，定义如下。

☢ 孩子结点、父结点。结点子树的根被称为这个结点的孩子，而这个结点又被称为孩子的双亲。在图2-14(c)中，结点B、C、D是结点A的子结点，而A是B、C、D的父结点。

☢ 子孙结点。以某结点为根的子树中的所有结点都被称为该结点的子孙。比如，结点E、F、K和L是B的子孙结点，当然也是A的子孙结点。

☢ 祖先结点。从根结点到该结点路径上的所有结点被称为祖先结点。例如，结点A、B和F是L的祖先结点。

☢ 兄弟结点。同一个父结点的孩子结点之间互为兄弟结点。例如，结点H、I和J则互为兄弟结点。

树的存储有三种典型的方法：双亲表示法、孩子表示法和孩子兄弟表示法。

（1）双亲表示法

树的双亲表示法主要描述的是结点的双亲关系，如图2-15所示。

双亲表示法的树结构定义如下：

这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。

（2）孩子表示法

孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，因此利用链式存储结构更适合，如图2-16所示。

孩子表示法的树结构定义如下：

这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域parent，用来指示结点的双亲在一维数组中的位置。

（3）孩子兄弟表示法

孩子兄弟表示法也是一种链式存储结构，通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其结构如下：

其中，FirstChild为指向该结点第一个孩子的指针，NextSibling为指向该结点的下一个兄弟，item是数据元素内容。图2-17为树结构的孩子兄弟表示法示例。

孩子兄弟表示法的树结构定义如下：

2．二叉树

二叉树是另一种树结构。它与树结构的区别是：每个结点最多有两棵子树，子树有左右之分。

二叉树也可以用递归的形式来定义，即二叉树是n(n≥0)个结点的有限集合，当n = 0时，称为空二叉树；当n > 0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。

二叉树包括5种基本形态，如图2-18所示。

（1）二叉树的性质

二叉树具有下列5个重要的性质。

【性质2-1】 在二叉树的第i层上最多有2i−1个结点（i≥1）。

证明：二叉树的第1层只有1个根结点，所以，i=1时，2i−1=21-1=20=1成立。

假设对所有的j，1≤j<i成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2i−1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，因此可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2×2=2i−1。

【性质2-2】 深度为k（k≥1）的二叉树最多有2k-1个结点。

证明：由性质2-1可以得出，1～k层各层最多的结点个数分别为20,21,22,23,…,2k-1。这是一个以2为比值的等比数列，可以得到，该数列前k项之和为2k-1。

【性质2-3】 对于任意一棵二叉树BT，如果度为0的结点个数为n₀，度为2的结点个数为n₂，则n₀=n₂+1。

证明：假设度为1的结点个数为n₁，结点总数为n，二叉树中的分支数为b。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为

再查看分支数。在二叉树中，除了根结点，每个结点都有一个从上向下的分支指向，所以总的结点个数n与分支数b之间的关系为n=b+1。

又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数b可以表示为b=n₁+2n₂。

代入式(2-1)，得到

用式(2-1)减去式(2-2)，并经过调整后得到

n₀=n₂+1

如果一个深度为k的二叉树拥有2k-1个结点，则它被称为满二叉树。有一棵深度为h、具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下、从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1～n的结点位置一一对应，则称这棵二叉树为完全二叉树。

【性质2-4】 具有n个结点的完全二叉树的深度为⎣log2n⎦+1。其中，⎣log2n⎦的结果是不大于log2n的最大整数。

证明：假设具有n个结点的完全二叉树的深度为k，则根据性质2-1可以得到

2k−1−1<n≤2k−1

将不等式两端加1，则

2k−1≤n<2k

将不等式中的三项同取以2为底的对数，并经过化简后，则

k−1≤log₂ n<k

由此可以得到

⎣log2n⎦ = k-1

整理后得到

k = ⎣log2n⎦+1

【性质2-5】 对于有n个结点的完全二叉树中的所有结点按从上到下、从左到右的顺序进行编号，则对任意一个结点i（1≤i≤n）均有：

① 如果i=1，则结点i是这棵完全二叉树的根，没有双亲，否则其双亲结点的编号为 ⎣i/2⎦。

② 如果2i>n，则结点i没有左孩子，否则其左孩子结点的编号为2i。

③ 如果2i+1>n，则结点i没有右孩子，否则其右孩子结点的编号为2i+1。

其证明请读者自己完成。

学习数据结构中二叉堆的时候，堆的操作就是基于此性质。

（2）二叉树的存储结构

二叉树可以采用两种存储方式：顺序存储结构和链式存储结构。

顺序存储结构适用于完全二叉树，其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容，如图2-19所示。

顺序存储结构的二叉树定义如下：

其特点是空间利用率高、寻找孩子和双亲比较容易。下面给出完全二叉树在这种存储形式下的操作算法。

① 构造一棵完全二叉树。

② 获取给定结点的左孩子。

RightChild(BT, node)与这个操作类似，返回2*node+1即可。读者可自行完成。

③ 获取给定结点的双亲。

特别提醒：顺序存储只对完全二叉树适用，它也是二叉堆的存储方式。

在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系。对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下：

其中，lChild和rChild是分别指向该结点左孩子和右孩子的指针，item是数据元素的内容。在C语言中的类型定义如下：

图2-20为一棵二叉树及相应的链式存储结构。

链式存储结构的特点是寻找孩子结点容易，双亲比较困难。若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下：

有关二叉树在链式存储结构下的操作算法将在随后介绍。

（3）二叉树的遍历

二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树，就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等操作，也可以是自定义的其他复杂处理过程。

二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问，另一类按层次访问。下面分别进行讨论。

按根、左子树和右子树三部分进行遍历，遍历二叉树的顺序存在下面6种可能：TLR（根左右），TRL（根右左），LTR（左根右），RTL（右根左），LRT（左右根），RLT（右左根）。其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此往往不予采用。TLR、LTR和LRT三种顺序根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。

三种遍历方法的流程描述如下。

① 先序遍历。

若二叉树为空，则结束遍历操作；否则

访问根结点；

先序遍历左子树；

先序遍历右子树。

② 中序遍历。

若二叉树为空，则结束遍历操作；否则

中序遍历左子树；

访问根结点；

中序遍历右子树。

③ 后序遍历。

若二叉树为空，则结束遍历操作；否则

后序遍历左子树；

后序遍历右子树；

访问根结点。

分析上述过程可以得出以下结论：

① 遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列。

② 遍历操作是一个递归的过程，因此这三种遍历操作的算法可以用递归函数实现。

先序遍历递归算法：

中序遍历递归算法：

后序遍历递归算法：

其中，Visit函数是一种抽象表示，它代表结点访问操作。图2-20中二叉树的三种遍历序列相应为：先序序列，ABDGCEFH；中序序列，DGBAECHF；后序序列，GDBEHFCA。