第二节 二叉树

3．二叉树与树的关系

（1）二叉树与无序树不同

二叉树中，每个结点最多只能有两棵子树，并且有左右之分。

二叉树并非是树的特殊情形，它们是两种不同的数据结构。

（2）二叉树与度数为2的有序树不同

在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。

图（a），它是一棵度为2的有序树，由于根结点的子树没有左右之分，所以它不是二叉树。另外，具有三个结点的度为2的有序树有一种形态，如图（b）所示。具有三个结点的树有两种形态，如图（b）和（c）所示。具有三个结点的二叉树有五种形态，如图（b）、（d）、（e）、（f）、（g）所示。

【真题选解】

性质一：二叉树第i（i≥1）层最多有2^i-1个结点。

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

（1）当i=1时，有2^i-1=2⁰=1。因为第1层上只有一个根结点，所以命题成立。

（2）假设对所有的j(1≤j<i)命题成立，即第j层上至多有2^j-1个结点。

（3）根据归纳假设，第i-1层上至多有2^i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2^i-2=2^i-1个结点，故命题成立。

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

证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：

2⁰+2¹+…+2^k-1=2^k-1

故命题正确。

性质三：任意非空二叉树中，若叶结点的数目为n₀，度为2的结点数目为n₂，则有关系n₀=n₂ + 1。

证明：

设度为1的结点数目为n₁，二叉树的结点总数为n，有　n=n₀ + n₁ + n₂

设B表示分支数，具有n个结点的二叉树的分支总数为n-1。则有　B=n - 1

而所有这些分支不是来自于度为1的结点就是来自于度为2的结点，即每一个度为1的结点发出一个分支，每一个度为2的结点发出两个分支。于是有

B=n₁ + 2n₂

联立上面三个等式可以得到

n₀=n₂ +1

故命题正确。

【真题选解】

满二叉树：一棵深度为k且有2^k-1个结点的二又树称为满二叉树。

满二叉树的特点：

（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。满二叉树的结点总数一定是奇数。

（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且叶结点都在最下一层上。

完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

完全二叉树特点：

（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。

（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。

（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

【真题选解】

性质4： 具有n个结点的完全二叉树的深度为

证明：设所求完全二叉树的深度为k。由完全二叉树定义可得：

深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2^k-1-1个结点。

由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：

n>2^k-1-1

另一方面，由性质2可得：

n≤2^k-1

即：2^k-1-l<n≤2^k-1

由此可推出：2^k-1≤n<2^k，取对数后有：

k-1≤log₂n<k

又因k-1和k是相邻的两个整数，故有

【真题选解】

性质五： 如果将一棵有n个结点的完全二叉树按层从1开始编号，则对任一编号为i （l≤i≤n）的结点X有：

若i=1，则结点X是根；若i> l，则X的双亲的编号为 。

若2i>n，则结点X无左孩子（且无右孩子）；否则，X的左孩子编号为2i。

若2i+1>n，则结点X无右孩子；否则，X的右孩子的编号为2i+1。

二、二叉树的存储结构

1、顺序存储结构

（1）完全二叉树的顺序存储

性质五修改为：如果将一棵有n个结点的完全二叉树按层从0开始编号，则对任一编号为i （0≤i<n）的结点X有：

若i=0，则结点X是根；若i> 0，则X的双亲的编号为 。

若2i+1<n，则结点X的左孩子编号为2i+1，否则，结点X无左孩子（且无右孩子）。

若2i+2<n，则结点X的右孩子的编号为2i+2，否则，X无右孩子。

（2）一般二叉树的顺序存储

（3）顺序存储二叉树的优点和缺点

① 对完全二叉树而言，顺序存储结构既简单又节省存储空间。

② 一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。最坏的情况下，一个深度为k且只有k个结点的右单支树需要2^k-1个结点的存储空间（相当于满二叉树）。

③在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。

2、链式存储结构

（1）二叉链结点结构

说明：

①数据域data，用以存放元素值。

②指针域lchild和rchild，分别指向该结点的左孩子和右孩子。没有左孩子时lchild=NULL, 没有右孩子时rchild=NULL,

【例】画出下图所示的二叉树的二叉链表表示图。

【解答】该二叉树的二叉链表表示如下图所示。

当二叉树有n个结点时，其二叉链表上共有2n个指针域，其中只有n-1个指针域用于存放其左、右孩子的指针（n个结点的二叉树一共有n-1个分支），剩下的n+l个指针域为空。

（2）二叉链结点类型定义

typedef struct node

　　{　DataType data；

　　　 Struct node *lchild，*rchild；　　　　 //左右孩子指针

　　}BinTNode；　　　　　　　　　　　 //结点类型

typedef BinTNode *BinTree；　　　　　　　//BinTree为指向BinTNode类型结点的指针类型

（3）三叉链结点结构

说明：增加的parent域指向其双亲

【例】画出图所示的二叉树的三叉链表表示图

【解答】

三叉链表结构与二叉链表结构的区别是它的结点多了一个指向双亲的指针域。当二叉树有n个结点时，其三叉链表上共有3n个指针域，其中只有n-1个指针域用于存放其左、右孩子的指针，有n-1个指向双亲，剩下的n+2个指针域为空。