6.2　二叉树

在有序树中有一类最特殊,也是最重要的树,称为二叉树（binary tree）。二叉树是树结构中最简单的一种,但却有着十分广泛的应用。

6.2.1　二叉树的定义

1.定义

二叉树是有n（n≥0）个结点的有限集合,它有如下一些特点。

（1）该集合可以为空（n＝0）。

（2）该集合可以由一个根结点及两个不相交的子树组成非空树,这两个子树分别称为左子树和右子树。

（3）左子树和右子树同样又都是二叉树。

在一棵非空二叉树中,每个结点至多只有两棵子树,分别称为左子树和右子树,并且左、右子树的次序不能任意交换。因此,二叉树是特殊的有序树。

2.二叉树的形态

根据定义,二叉树可以有5种基本形态,如图6－4所示。

图6－4　二叉树的基本形态

其中:图6－4（a）所示为空二叉树；图6－4（b）所示为仅有根结点的二叉树；图6－4（c）所示为右子树为空的二叉树；图6－4（d）所示为左子树为空的二叉树；图6－4（e）所示为左、右子树均非空的二叉树。

3.二叉树的基本操作

二叉树的基本操作通常有以下几种。

（1）CreateBT（）　创建一棵二叉树。

（2）ShowTree（BT＊T）　按凹入法（或圆括号法等方法）显示二叉树。

（3）Preorder（BT＊T）　按先序（根、左、右）遍历二叉树上所有结点。

（4）Inorder（BT＊T）　按中序（左、根、右）遍历二叉树上所有结点。

（5）Postorder（BT＊T）　按后序（左、右、根）遍历二叉树上所有结点。

（6）Levelorder（BT＊T）　按层次遍历二叉树上所有结点。

（7）Leafnum（BT＊T）　求二叉树叶结点总数。

（8）TreeDepth（BT＊T）　求二叉树的深度。

6.2.2　二叉树的性质

性质1　一棵非空二叉树的第i层上最多有2^i－1个结点（i≥1）。

一棵非空二叉树的第一层有1个结点,第二层最多有2个结点,第三层最多有4个结点,依此类推,利用归纳法即可证明第i层上最多有个2^i－1结点。

性质2　深度为h的二叉树中,最多具有2^h－1个结点（h≥1）。

【证明】　根据性质1,当深度为h的二叉树每一层都达到最多结点数时,它的和（n）最大,即

所以,命题正确。

（1）满二叉树　一棵深度为h,且有2^h－1个结点的二叉树称为满二叉树。如图6－5所示的是一棵深度为4的满二叉树,其特点是每一层上的结点都具有最大的结点数。如果对满二叉树的结点进行连续的编号,约定编号从根结点起,从上往下,自左向右（见图6－5）,由此可以引出完全二叉树的定义。

图6－5　满二叉树

（2）完全二叉树　深度为h,有n个结点的二叉树,当且仅当其每个结点的编号都与深度为h的满二叉树中从1至n的结点的编号一一对应时,称此二叉树为完全二叉树。如图6－6（a）所示为一棵完全二叉树,而图6－6（b）则不是完全二叉树。

图6－6　两种二叉树

完全二叉树除最后一层外,其余各层都是满的,并且最后一层或者为满,或者仅在右边缺少连续的若干个结点。

性质3　对于一棵有n个结点的完全二叉树,若按满二叉树的方法对结点进行编号（见图6－5）,则对于任意序号为i的结点,有以下性质。

（1）若i＝1,则序号为i的结点是根结点；若i＞1,则序号为i的结点的父结点的序号为i/2。

（2）若2i≤n,则序号为i的结点的左孩子结点的序号为2i；若2i＞n,则序号为i的结点无左孩子。

（3）若2i＋1≤n,则序号为i的结点的右孩子结点的序号为2i＋1；若2i＋1＞n,则序号为i的结点无右孩子。

证明略。

性质4　具有n（n＞0）个结点的完全二叉树（包括满二叉树）的深度（h）为?log₂n」＋1。

【证明】　由性质2和完全二叉树的定义可知,当完全二叉树的深度为h且结点个数为n时有

2^h－1－1＜n≤2^h－1

2^h－1≤n＜2^h

即

对不等式取对数则有

h－1≤log₂n＜h

由于h是整数,所以有h＝?log₂n」＋1。

注:?log₂n」表示不大于log₂n的最大整数,「log₂n?表示不小于log₂n的最小整数。例如,当n＝10时,?log₂n」≈3.32,则?log₂n」＝3,「log₂n?＝4。

性质5　对于一棵非空的二叉树,设n₀、n₁、n₂分别表示度为0、1、2的结点个数,则有:n₀＝n₂＋1。

【证明】　（1）设n为二叉树的结点总数,则有

（2）由二叉树的定义可知,除根结点外,二叉树其余结点都有唯一的父结点,那么,父结点的总数（F）为

（3）根据假设,各结点的子结点总数（C）为

（4）因为父子关系是相互对应的,即F＝C,也即

综合式（6－1）、式（6－2）、式（6－3）、式（6－4）可以得到

n₀＋n₁＋n₂＝n₁＋2n₂＋1

n₀＝n₂＋1

即

所以,命题正确。

6.2.3　二叉树的存储

二叉树的存储结构也分为顺序存储和链接存储两种存储结构。

1.顺序存储结构

二叉树的顺序存储,就是用一组连续的存储单元存放二叉树中的结点。一般可以采用一维数组或二维数组的方法进行存储。

1）一维数组存储法

二叉树中各结点的编号与等深度的完全二叉树中对应位置上结点的编号相同。其编号过程为:首先把根结点的编号定为1,然后按照层次从上至下、从左到右的顺序,对每一个结点进行编号。当双亲结点为i时,其左孩子的编号为2i,其右孩子的编号为2i＋1。在图6－7（a）中,各结点右边的数字就是该结点的编号。

对于一般的二叉树,如果按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中,则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系,只有增加一些并不存在的空结点,使之成为一棵完全二叉树的形式,才能用一维数组进行存储。如图6－7（a）所示为一棵一般二叉树,经过改造以后成为图6－7（b）所示的完全二叉树。其顺序存储状态示意图如图6－7（c）所示。

图6－7　一般二叉树的顺序存储示意图

显然,这种存储结构会造成大量的空间浪费。如图6－8（a）所示,一棵4个结点的二叉树,却要分配14个存储单元。可以证明,深度为h的（右向）单支二叉树,虽然只有h个结点,却需分配2^h－1个存储单元。

对于完全二叉树和满二叉树,这种顺序存储结构既能够最大限度地节省存储空间,又可以利用数组元素的下标值确定结点在二叉树中的位置,因为完全二叉树上编号为i的结点元素存储在一维数组中下标为i－1的分量中,如图6－8（c）所示。

图6－8　改造二叉树的顺序存储示意图

2）静态链表存储法

用数组描述的链表,称为静态链表。静态链表这种存储结构与顺序表一样,需要预先为其分配一个较大的数组空间,但与顺序表不同的是,静态链表在插入和删除操作时不需移动元素,仅需修改指针的指向关系即可,故仍具有链式存储结构的主要优点。

静态链表除了可以用来描述线性结构之外,也可以用来存储二叉树这种非线性结构。静态链表的二叉树结点结构可定义如下。

设二叉树的结点数为n,则静态链表的预设长度MAXLEN≥n。

仍以图6－7（a）的二叉树为例,则其静态链表的存储形式如图6－9所示。

图6－9　二叉树的静态链表存储

顺序存储结构小结:

（1）当二叉树为满二叉树或完全二叉树时,采用一维数组存储可以节省存储空间。

（2）当二叉树层数高而结点较少时,采用静态链表存储比较好,并且这种结构插入或删除结点时均不需移动任何结点,比较方便。

（3）一维数组存储的优点是查找父子结点的位置非常方便,其缺点是进行插入或删除操作要进行大量的数据移动。

（4）静态链表存储结构便于在没有指针类型的高级程序设计语言中使用链表结构。

（5）顺序存储的这两种实现方式的共同缺点是均需要预设结点存储空间,并且存储空间的扩充不太方便。

2.链式存储结构

二叉树的链式存储结构是用链表来表示二叉树,即用链指针来指示结点的逻辑关系。通常有下面两种形式。

1）二叉链表存储

二叉链表结点由一个数据域和两个指针域组成,其具体结构如下。

其中,data为数据域,用于存放结点的数据信息；lchild为左指针域,用于存放该结点左子树根结点的地址；rchild为右指针域,用于存放该结点右子树根结点的地址。

当左子树或右子树不存在时,相应的指针域值为空,用符号“∧”表示。

设一棵二叉树如图6－10所示,其二叉链表的存储形式如图6－11所示。

图6－10　二叉树

图6－11　二叉树的链式存储示意图

容易证明,在含有n个结点的二叉链表中有n＋1个空指针域。利用这些空指针域存储其他有用信息,从而可以得到另外一种存储结构——线索化链表,关于这一概念将在6.3.3节中介绍。

二叉链表是二叉树最常用的存储方式,本书后面涉及的二叉树的链式存储结构一般都是指二叉链表结构。下面给出二叉树的二叉链表描述。

2）三叉链表存储

三叉链表结点由一个数据域和三个指针域组成,其具体结构如下。

其中:data为数据域,用于存放结点的数据信息；lchild为左指针域,用于存放该结点左子树根结点的地址；rchild为右指针域,用于存放该结点右子树根结点的地址；parent为父指针域,用于存放该结点的父结点的存储地址。

这种存储结构既便于查找左、右子树中的结点,又便于查找父结点及其祖先结点,但付出的代价是增加了存储空间的开销。

图6－12给出了图6－10所示的二叉树的三叉链表存储示意图。

图6－12　二叉树的三叉链表存储示意图