二叉树

在进一步讨论树之前，先讨论一种简单而重要的树结构——二叉树。因为任何树都可以转化为二叉树进行处理，二叉树作为特殊的树，适合于计算机处理，所以二叉树是研究的重点。

本节主要介绍：

一、二叉树的定义与基本操作

定义：把满足以下两个条件的树型结构叫做二叉树（Binary Tree）： （1） 每个结点的度都不大于2；

（2） 每个结点的孩子结点次序不能任意颠倒。

由此定义可看出，一个二叉树中的每个结点只能含有0、1或2个孩子，而且每个孩子有左右之分。位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子。 下给出了二叉树的五种基本形态：

图(a)所示为一棵空的二叉树；图（b）所示为一棵只有根结点的二叉树；图（c）所示为一棵只有左子树的二叉树（左子树仍是一棵二叉树）；图（d）所示为左、右子树均非空的二叉树（左、右子树均为二叉树）；图（e）所示为一棵只有右子树的二叉树（右子树也是一棵二叉树）。二叉树也是树，故前面所介绍的有关树的术语都适用于二叉树。

(a)空二叉树

(b)只有根结 点的二叉树

(c)只有左子 树的二叉树

(e)只有右子树 的二叉树

(d)左右子树均 非空的二叉树

二叉树的五种基本形态

与树的基本操作类似，二叉树有如下基本操作：

⑴ Initiate（bt）：将bt初始化为空二叉树。 ⑵ Create(bt)：创建一棵非空二叉树bt。 ⑶ Destory（bt）： 销毁二叉树bt。 ⑷ Empty（bt）： 若bt为空，则返回TRUE，否则返回FALSE。

⑸ Root(bt)： 求二叉树bt的根结点。若bt为空二叉树，则函数返回“空”。 ⑹ Parent（bt，x）：求双亲函数。求二叉树bt中结点x的双亲结点。若结点x是二叉

树的根结点或二叉树bt中无结点x，则返回“空”。 ⑺ LeftChild（bt，x）：求左孩子。返回结点x的左孩子，若结点x无左孩子或x不在bt中，则返回“空”。 ⑻ RightChild（bt，x）：求右孩子。返回结点x的右孩子，若结点x无右孩子或x不在bt中，则返回“空”。

⑼ Traverse（bt）: 遍历操作。按某个次序依次访问二叉树中每个结点一次且仅一次。 ⑽ Clear（bt）：清除操作。将二叉树bt置为空树。

二、二叉树的性质

i-1

性质1:在二叉树的第i层上至多有2个结点(i≥1)。 证明：用数学归纳法。

i-10

归纳基础：当i=1时，整个二叉树只有一个根结点，此时2=2=1，结论成立。

k-1

归纳假设：假设i=k时结论成立，即第k层上结点总数最多为2个。 欲证明当i=k+1时，结论成立。

因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大

k-1(k+1)-1

数的2倍，即2×2=2，故结论成立。

k

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

证明：因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为

第i层上的最大结点个数=i1

i＝1

kk

２=２-1

i-1k

故结论成立。

性质3:对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0= n2+1 证明：设二叉树中结点总数为n，n1为二叉树中度为1的结点总数。 因为二叉树中所有结点的度小于等于2，所以有

n= n0+ n1+n2

设二叉树中分支数目为B，因为除根结点外，每个结点均对应一个进入它的分支，所以有

n=B+1。

又因为二叉树中的分支都是由度为1和度为2的结点发出，所以分支数目为

B=n1+2n2

整理上述两式，可得到

n=B+1=n1+2n2+1

将n= n0+ n1+n2代入上式，得出n0+ n1+n2=n1+2n2+1，整理后得n0= n2+1，故结论成立。 下面先给出两种特殊的二叉树，然后讨论其有关性质。

k

满二叉树：深度为k且有2-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。如下图(a)所示的二叉树即为一棵满二叉树。

满二叉树的顺序表示，即从二叉树的根开始，层间从上到下，层内从左到右，逐层进行编号（1，2，···，n）。例如下图(a)所示的满二叉树的顺序表示为(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15)。

完全二叉树：深度为k，结点数为n的二叉树，如果其结点1～n的位置序号分别与满二叉树的结点1～n的位置序号一一对应，则为完全二叉树，如下图(b)所示。

可见，满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。

1 1 2 3 2 3

4 5 6 7 4 5 6 7 8 9 10 11 12 13 14 15 8 9 10 11 12 13 14

（a）满二叉树

（b）完全二叉树

满二叉树与完全二叉树

性质4：具有n个结点的完全二叉树的深度为log2n+1。

证明：假设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结

点总数为：

n1=2k-1-1

k层满二叉树的结点总数为：

n2=2k-1

显然有n1将n1=2k-1-1和n2=2k-1代入上式，可得 2k-1≤n<2k，即k-1≤log2n性质5: 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二

叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：

（1）如i=1，则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为i/2。

（2）如2×i>n，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结点的左孩子结点的序号为2×i。

（3）如2×i＋1>n，则序号为i的结点无右孩子；如2×i＋1≤n，则序号为i的结点的右孩子结点的序号为2×i＋1。 可以用归纳法证明其中的（2）和（3）：

当i=1时，由完全二叉树的定义知，如果2×i=2≤n，说明二叉树中存在两个或两个以上的结点，所以其左孩子存在且序号为2；反之，如果2>n，说明二叉树中不存在序号为2的结点，其左孩子不存在。同理，如果2×i+1=3≤n，说明其右孩子存在且序号为3；如果3>n，则二叉树中不存在序号为3的结点，其右孩子不存在。

假设对于序号为j(1≤j≤i)的结点，当2×j≤n时，其左孩子存在且序号为2×j，当2×j>n时，其左孩子不存在；当2×j+1≤n时，其右孩子存在且序号为2×j+1，当2×j+1>n时，其右孩子不存在。

当i=j+1时，根据完全二叉树的定义，若其左孩子存在，则其左孩子结点的序号一定等于序号为j的结点的右孩子的序号加1，即其左孩子结点的序号等于 （2×j+1）+1=2 （j+1）=2×i，且有2×i≤n；如果2×i>n，则左孩子不存在。若右孩子结点存在，则其右孩子结点的序号应等于其左孩子结点的序号加1，即右孩子结点的序号为=2×i+1，且有2×i+1≤n；如果2×i+1>n，则右孩子不存在。

故（2）和（3）得证。

由（2）和（3）我们可以很容易证明（1）。

当i=1时，显然该结点为根结点，无双亲结点。当i>1时，设序号为i的结点的双亲结点的序号为m，如果序号为i的结点是其双亲结点的左孩子，根据（2）有i=2×m，即m=i/2;如果序号为i的结点是其双亲结点的右孩子，根据（3）有i=2×m+1，即m= （i-1）/2=i/2-1/2，综合这两种情况可以得到，当i>1时，其双亲结点的序号等于i/2。证毕。

三、二叉树的存储结构

 顺序存储

对于完全二叉树来说，可以将其数据元素逐层存放到一组连续的存储单元中，如下图所示。用一维数组作存储结构，将二叉树中编号为i的结点存放在数组的第i个分量中。根据二叉树的性质5，可得结点i的左孩子的位置为LChild（i）=2×i；右孩子的位置为RChild（i）=2 ×i＋1。

A

B C

E F D G

I H J K L

（a）完全二叉树

显然，这种存储方式对于一棵完全二叉树来说是非常方便的。因为对完全二叉树采用顺序存

A B C D E F G H I J K L

储结构既不浪费空间，又可以根据公式计算出每一个结点的左、右孩子的位置。但是，对于一般的二叉树，我们必须用“虚结点”将其补成一棵“完全二叉树”来存储，这就会造成空（b）二叉树的顺序存储结构

间浪费。一种极端的情况如下图所示，从中可以看出，对于一个深度为k的二叉树，在最坏

二叉树与顺序存储结构 k

的情况下（每个结点只有右孩子）需要占用2-1个存储单元，而实际该二叉树只有k个结点，空间的浪费太大，这是顺序存储结构的一大缺点。

A

B C A ∧ B ∧ ∧ ∧ C ∧ ∧ ∧ ∧ ∧ ∧ ∧ D

（a）单支二叉树

单支二叉树与其顺序存储结构

 链式存储

对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。可以设计每个结点至少包括三个域：数据域、左孩子域和右孩子域，如下图所示。

LChild Data 结点结构

RChild 其中，LChild域指向该结点的左孩子，Data域记录该结点的信息，RChild域指向该结点的右孩子。此结点结构形成的二叉树称为二叉链表，如下图所示 A

A

B ∧ C B C

∧ E ∧ ∧ D ∧ F ∧ D E F

∧ G ∧ G

（b）二叉树T的二叉链表 （a）二叉树T

二叉树和二叉链表

用C语言定义二叉树的二叉链表结点结构如下： typedef struct Node {

DataType data;

struct Node * LChild; struct Node * RChild;

}BiTNode, *BiTree;

若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n＋1个空的链域。

证明：分支数目B=n-1，即非空的链域有n-1个，故空链域有2n-(n-1)=n+1个。 有时，为了便于找到双亲结点，可以增加一个Parent域，以指向该结点的双亲结点。采用这种结点结构的存放方式称做二叉树的三叉链表存储结构。

不同的存储结构实现二叉树的操作也不同。如要找某个结点的父结点，在三叉链表中很容易实现；在二叉链表中则需从根指针出发一一查找。可见，在具体应用中，要根据二叉树的形态和要进行的操作来决定采用哪种二叉树的存储结构。