5.2 二叉树及其基本性质

 

5.2  二叉树及其基本性质

二叉树（Binary Tree）也称为二分树、二元树、对分树等，是树形结构中一种最常见的类型，许多实际问题抽象出来的数据结构往往就是二叉树，即使一般的树也能简单地转化为二叉树，而且二叉树的存储结构及其运算的实现都较为简单，因此二叉树就显得特别重要。

二叉树是一种特殊的树，在树中，每个节点可以有任意个后继节点，但二叉树中每个节点最多只有两个后继节点，这样二叉树的存储和操作更易于实现。

5.2.1  什么是二叉树

二叉树是指树的度为2的有序树。它是一种最简单、最重要的树，在计算机领域有着广泛的应用。

二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的分别称做根节点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。

在二叉树中，每个节点左子树的根节点被称为左孩子节点，右子树的根节点被称为右孩子节点。

二叉树与一般树不同的地方是：

·    二叉树的节点个数可以是零，而一般树至少由一个节点组成。

·    二叉树有排列顺序的关系，而一般树则没有。

·    二叉树中每一节点的度至多为2，而一般树无此限制。

二叉树的逻辑表示法与树的逻辑表示法相同，即可以采用树形表示法、文氏图表示法、凹入表示法和括号表示法来表示二叉树的逻辑结构。

归纳起来，二叉树的5种形态如图5-6所示。

图5-6  二叉树的5种形态

【例5-2】给出由3个节点A、B和C构成的所有形态的二叉树（不考虑节点值的差异）。

解：含有3个节点A、B和C的所有形态的二叉树如图5-7所示。

图5-7  含有3个节点的所有形态的二叉树

5.2.2  二叉树的基本性质

二叉树具有如下重要的性质。

性质1：二叉树上叶子节点数等于度为2的节点数加1。

证明：设n₀为二叉树中叶子节点个数，n₁为二叉树中度为1的节点个数，n₂为二叉树中度为2的节点个数，n为所有节点个数（除特殊说明外，以下均采用这种表示法）。由于二叉树中所有节点的度≤2，则其节点总数为：

n=n₀+n₁+n₂

图5-8  二叉树

再看二叉树中的分支数：除根节点外，其余节点都有一个分支进入（在二叉树的树形表示中一个分支对应为该节点与双亲的一条连线），设b为分支数，则n=b+1。由于这些分支是由度1或2的节点射出的，因此有b=n₁+2n₂，于是得：

n=n₁+2n₂+1

由上述两式得：

n₀=n₂+1

例如，在图5-8所示的二叉树中，度为2的节点数为3个，度为0的节点数为4个，它比度为2的节点数正好多1个。

性质2：二叉树上第i层上至多有2^i-1个节点（i≥1）。

证明：用数学归纳法证明。

当i=1时，只有一个根节点。显然2^i-1=2⁰=1，成立。

现在假定对所有的k（1≤k≤i-1），命题成立，即第k（1≤k≤i-1）层上至多有2^k-1个节点。

由于二叉树的每个节点的度至多为2，故第i层上最大节点数为i-1层上最大节点数的2倍，即2×2^i-2=2^i-1。至此，命题证毕。

性质3：深度为h的二叉树至多有2^h-1个节点。

证明：由性质2可知，深度为h的二叉树的最大节点数为：

命题证毕。

5.2.3  满二叉树与完全二叉树

在一棵二叉树中，当第i层的节点数为2^i-1个时，则称此层的节点数是满的，当一棵二叉树中的每一层都满时，则称此树为满二叉树。满二叉树具有这样的特性：除叶子节点以外的其他节点的度皆为2，且叶子节点在同一层上。

由二叉树性质3可知，深度为h的满二叉树中的节点数为2^h-1个。图5-9（a）为一棵深度为4的满二叉树，其节点数为2⁴-1=15。图中每个节点的值是利用该节点的编号来表示的，编号从树根为1开始，按照层次从小到大、同一层从左到右的次序顺序编号。

在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个节点，则称此树为完全二叉树。由此可知，满二叉树是完全二叉树的特例。完全二叉树具有这样的特性：二叉树中至多只有最下边两层节点的度数小于2，且若二叉树中任意一个节点其右子树的高度为h，则其左子树的高度只能是h或h+1。因此深度为h的完全二叉树若按层次从上到下、从左到右并按自然数编号，它与深度为h的满二叉树中节点的编号一一对应。

图5-9（b）是一棵完全二叉树，它与等高度的满二叉树相比，在最后一层的右边缺少了3个节点。该树中每个节点上面的数字为对该节点的编号，编号的方法同满二叉树。

图5-9  满二叉树和完全二叉树

完全二叉树将在很多场合下出现，下面介绍完全二叉树的两个重要特性。

特性1：具有n个节点的完全二叉树的深度为?log₂n?+1。

证明：假设深度为k，则根据二叉树性质2和完全二叉树的定义有如下表达式。

于是k-1≤log₂n＜k，因为k是整数，所以k=?log₂n?+1。

特性2：对完全二叉树中编号为i的节点（1≤i≤n，n≥1，n为节点数）有如下叙述。

（1）若i≤?n/2?^①，即2i≤n，则编号为i的节点为分支节点，否则为叶子节点。

（2）若n为奇数，则每个分支节点都既有左孩子，又有右孩子；若n为偶数，则编号最大的分支节点（编号为?n/2?，由于C/C++中n/2为整除，故?n/2?与n/2相同）只有左孩子，没有右孩子，其余分支节点左、右孩子都有。

（3）若编号为i的节点有左孩子，则左孩子节点的编号为2i；若编号为i的节点有右孩子，则右孩子节点的编号为2i+1。

（4）除树根节点外，若一个节点的编号为i，则它的双亲节点的编号为i/2，也就是说，当i为偶数时，其双亲节点的编号为i/2，它是双亲节点的左孩子，当i为奇数时，其双亲节点的编号为(i-1)/2，它是双亲节点的右孩子。