二叉树及其基本性质

    2.6.2　二叉树及其基本性质

    1．什么是二叉树

    二叉树（Binary Tree）是一种很有用的非线性结构。二叉树不同于前面介绍的树结构。但它与树结构很相似。并且，树结构的所有术语都可以用到二叉树这种数据结构上。

    二叉树具有以下两个特点：

    ①非空二叉树只有一个根节点；

    ②每一个节点最多有两棵子树，且分别称为该节点的左子树与右子树。

    由以上特点可以看出，在二叉树中，每一个节点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个节点的度可以是任意的。另外，二叉树中的每一个节点的子树被明显地分为左子树与右子树。在二叉树中，一个节点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个节点既没有左子树也没有右子树时，该节点即是叶子节点。

    如图2-30(a)所示是一棵只有根节点的二叉树，如图2-30(b)所示是一棵深度为4的二叉树。

    

    

    图2-30　二叉树例

    2．二叉树的基本性质

    二叉树具有以下几个性质：

    性质1　在二叉树的第k层上，最多有2^k-1（k≥1）个节点。

    根据二叉树的特点，这个性质是显然的。

    性质2　深度为m的二叉树最多有2^m-1个节点。深度为m的二叉树是指二叉树共有m层。

    根据性质1，只要将第l层到第m层上的最大节点数相加，就可以得到整个二叉树中节点数的最大值，即2^1-1+2^2-1+…+2^m-1=2^m-1

    性质3　在任意一棵二叉树中，度为0的节点（即叶子节点）总是比度为2的节点多一个。

    对于这个性质说明如下：

    假设二叉树中有n₀个叶子节点，n₁个度为1的节点，n₂个度为2的节点，则二叉树中总的节点数为

    n=n₀+n₁+n₂　　（1）

    由于在二叉树中除了根节点外，其余每一个节点都有唯一的一个分支进入。设二叉树中所有进入分支的总数为m，则二叉树中总的节点数为

    n=m+1　　（2）

    又由于二叉树中这m个进入分支是分别由非叶子节点射出的。其中度为1的每个节点射出1个分支，度为2的每个节点射出2个分支。因此，二叉树中所有度为l与度为2的节点射出的分支总数为n₁+2n₂。

    而在二叉树中，总的射出分支数应与总的进入分支数相等，即

    m=n₁+2n₂　　（3）

    将式（3）代入式（2）有

    n=n₁+2n₂+1　　（4）

    最后比较式（1）和式（4）有

    n₀+n₁+n₂=n_l+2n₂+1

    化简后得n₀=n₂+1

    即：在二叉树中，度为0的节点（即叶子节点）总是比度为2的节点多一个。

    例如，在如图2-30(b)所示的二叉树中，有3个叶子节点，有2个度为2的节点，度为0的节点比度为2的节点多一个。

    性质4　具有n个节点的二叉树，其深度至少为[log₂n]+1，其中[log₂n]表示取log₂n的整数部分。

    这个性质可以由性质2直接得到。

    3．满二叉树与完全二叉树

    满二叉树与完全二叉树是两种特殊形态的二叉树。

    （1）满二叉树

    所谓满二叉树是指：除最后一层外，每一层上的所有节点都有两个子节点。这就是说，在满二叉树中，每一层上的节点数都达到最大值，即在满二叉树的第k层上有2_k-1个节点，且深度为m的满二叉树有2m-1个节点。

    如图2-31(a)、(b)、(c)所示分别是深度为2、3、4的满二叉树。

    

    

    图2-31　满二叉树

    （2）完全二叉树

    所谓完全二叉树是指：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。

    更确切地说，如果从根节点起，对二叉树的节点自上而下、自左至右用自然数进行连续编号。则深度为m、且有n个节点的二叉树，当且仅当其每一个节点都与深度为m的满二叉树中编号从1到n的节点一一对应时，称之为完全二叉树。

    如图2-32(a)、(b)所示分别是深度为3、4的完全二叉树。

    

    

    图2-32　完全二叉树

    对于完全二叉树来说，叶子节点只可能在层次最大的两层上出现；对于任何一个节点，若其右分支下的子节点的最大层次为p，则其左分支下的子节点的最大层次或为p，或为p+1。

    由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。

    完全二叉树还具有以下两个性质：

    性质1　具有n个节点的完全二叉树的深度为[log₂n]+1。

    性质2　设完全二叉树共有n个节点。如果从根节点开始，按层序（每一层从左到右）用自然数1，2，…，n给节点进行编号。则对于编号为k（k=1，2，…，n）的节点有以下结论：

    ①若k=1，则该节点为根节点，它没有父节点；若k＞1，则该节点的父节点编号为INT（k/2）。

    ②若2k≤n，则编号为k的节点的左子节点编号为2k；否则该节点无左子节点（显然也没有右子节点）。

    ③若2k+1≤n，则编号为k的节点的右子节点编号为2k+1；否则该节点无右子节点。

    根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各节点，则很容易确定每一个节点的父节点、左子节点和右子节点的位置。