1
上节内容回顾
?树的基本概念
?二叉树的基本概念和性质
?两种特殊的二叉树
2
问题 1：什么是二叉树？简述树和二叉树的不同点。
答：
(1)树 (2)二叉树 (3)二叉树
二叉树是由 n(n≥0) 个结点的有限集合构成，此集合或
者为空集，或者由一个根结点及两棵互不相交的左右子树组
成，并且左右子树都是二叉树。
树与二叉树是 两类不同 的树型结构。树中并没有限定每
个子树的位置，通常是无序的，即使在有序树中，也只是限
定了各子树之间的相次序，而没有限定子树所在的位置；而
二叉树的每个结点至多有两个子树，且每个结的子树有严格
的左、右位置。
a
b c d
a
b c
a
b
e f d
3
问题 2：二叉树的性质？
答,性质 1:在一棵非空二叉树的第 i层上至多有 2i个结点（ i≥ 0）。
性质 2:深度为 k的二叉树至多有 2k+1-1个结点 (k≥ -1)。
性质 3,对于任何一棵非空的二叉树，若度为 2的结点数有 n2个，
则叶子数（ n0）必定为 n2＋ 1 （即 n0=n2+1）
性质 4,具有 n个结点的完全二叉树的深度 k必为 ?log2(n+1)?-1
性质 5:对于一棵有 n个结点的完全二叉树的结点按照从上至下
和从左至右的顺序对所有结点从 0开始顺序编号,则对于序号为
i的结点 (0≤i≤n),有：
(1)如果 i=0，则结点 i无双亲，是二叉树的根；如果 i>0，则
其双亲是结点 (i-1)/2(“/”表示整除）。
(2)如果 2i+1≥ n，则结点 i为叶子结点，无左孩子；否则，其左孩子是结点 2i+1。
(3)如果 2i＋ 2≥ n，则结点 i无右孩子；否则，其右孩子是结点 2i＋ 2。
4
问题 3：什么是两种特殊形态的二叉树？ 它们 的区别？
答,满二叉树 与完全二叉树。
在一棵二叉树中，如果所有分支结点都
存在左子树和右子树，并且所有叶子结点都
在同一层上，这样的二叉树称为 满二叉树 。
如果一棵深度为 k，有 n个结点的二叉树
中各结点能够与深度为 k的顺序编号的满二叉
树从 1到 n标号的结点相对应的二叉树称为 完
全二叉树。其特点,
(1)所有的叶结点都出现在第 k层或 k－ 1层。
(2)若任一结点，如果其右子树的最大层次为 i，
则其左子树的最大层次为 i或 i＋ 1。
a
b
d
c
e f g
1
2 3
5 64
5
满二叉树与完全二叉树的区别是：
满二叉树是叶子一个也不少的树，而完全二叉树虽然前
k-1层是满的，但最底层却允许在右边缺少连续若干个结点。
满二叉树是完全二叉树的一个特例。
6
问题 4,对于任何一棵非空的二叉树，若度为 2的结点数有
n2个，叶子数 n0必定为 n2＋ 1。试证明此结论是正确的。
证明,∵ 二叉树中全部结点数 n＝ n0+n1+n2
(叶子数＋ 1度结点数＋ 2度结点数 =全部结点数 )
又 ∵ 二叉树中全部结点数 n＝ B+1 ( 总分支数＋根结点 )
（ 除根结点外, 每个结点必有一个直接前趋, 即一个分支 ）
而 总分支数 B= n1+2n2 (1度结点必有 1个直接后继, 2度结点必
有 2个 )
由此可得,n0+n1+n2=n1+2n2 +1,即 n0=n2+1
7
问题 5、针对二叉树，回答下列问题：
(1)具有 n个结点的非空二叉树的最小深度是多少？最
大深度是多少？
（ 2）具有 n个结点的完全二叉树中有多少个叶子结点？
有多少个度为 2的结点？
（ 3）具有 n0个叶子结点的完全二叉树中共有多少个结
点？
答,(1)其 最小深度是 ?log2(n+1)?-1,最大深度是 n。
(2)具有 n个结点的完全二叉树中有 ?n/2?叶子结点，
有 ?n/2?-1个度为 2的结点。
（ 3）具有 n0个叶子结点的完全二叉树中共有 2n0
个结点或 2n0-1个结点。
8
一棵完全二叉树有 1000个结点，则它必有 个
叶子结点，有 个度为 2的结点，有 个结点只
有非空左子树，有 个结点只有非空右子树。
练习：
正确答案：
全部叶子数＝ ?1000/2? =500个。
度为 2的结点＝ 叶子总数－ 1=499个。
因为最后一个结点坐标是偶数，所以必为左子树。 有 1
个结点只有非空左子树，有 0 个结点只有非空右
子树。
9
7.3 二叉树的设计和实现
7.3.1 二叉树的顺序存储结构
二叉树的存储结构主要有三种：顺序存储结构、链式存储
结构和仿真指针存储结构。
1,二叉树的顺序存储结构
完全二叉树的结点可按从上至下和从左至右的次序存储在
一维数组中, 其结点之间的关系可由公式计算得到, 这就是二
叉树的顺序存储结构 。 图 7-4在数组中的存储结构为：
数组
下标 0 1 2 3 4 5 6
a b c d e f g
10
问题：对于一般的二叉树如何存储呢？
显然不能直接使用二叉树的顺序存储结构 。 我们可以采取
下面这种办法：首先在非完全二叉树中增添一些并不存在的空结
点使之变成完全二叉树的形态, 然后再用顺序存储结构存储 。
数组
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 (c)
(a)一般二叉树 (b)完全二叉树 （ c)在数组中的存储形式
图 7.6 一般二叉树的顺序存储结构
A B C Λ D E Λ Λ Λ F Λ Λ G
11
2,二叉树的链式存储结构
二叉树的链式存储结构是用指针建立二叉树中结点之间的
关系。 二叉树最常用的的链式存储结构是二叉链。 二叉链存储结
构的每个结点包含三个域，分别是数据域 data、左孩子指针域
leftChild和右孩子指针域 rightChild。二叉链存储结构中每个
结点的图示结构为,
leftChild data rightChild
二叉链存储结构的二叉树也有不带头结点和带头结点两种。
带头结点的二叉链存储结构的二叉树见图 7.7(b)，不带头结点
的二叉链存储结构的二叉树如图 7.7（ a）所示。
12
图 7.7 二叉链存储结构的二叉树
13
3,二叉树的仿真指针
二叉树的仿真指针存储 结构 是用数组存储二叉树中的结点，
数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常
规指针建立二叉树中结点之间的关系。
图 7.8 二叉树的仿真二叉链存储结构
14
7.3.2 二叉链存储结构的二叉树操作实现
在二叉链存储结构下, 针对一棵二叉树, 主要涉及如下几
个功能模块：
?二叉树的初始化操作；
?二叉树中给某结点插入一个左结点的操作；
?二叉树中给某结点插入一个右结点的操作；
?删除二叉树中某结点的左子树操作；
?删除二叉树中某结点的右子树操作 。
各算法的基本思想及程序实现如下：
typedef struct Node
{ DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode; /*结点的结构体定义 */
15
1.二叉树的初始化
算法的基本思想,创建二叉树的头结点。
程序实现：
void Initiate(BiTreeNode **root)
{
*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
16
2.二叉树中给某结点插入一个左结点的操作
算法的基本思想,
若当前结点 (假设为 curr）非空，在 curr的左子
树插入元素值为 x的新结点,原 curr所指结点的左
子树成为新插入结点的左子树。若插入成功返回新
插入结点的指针，否则返回空指针。
17
程序实现：
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x)
{ BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}
18
4.删除二叉树中某结点的左子树操作
算法的基本思想,若 curr非空，删除 curr所指结点的左子树。
若删除成功，返回删除结点的双亲结点指针，否则返回空指针。
程序实现：
BiTreeNode *DeleteLeftTree(BiTreeNode *curr)
{
if(curr==NULL||curr->leftChild==NULL)
return NULL;
Destroy(&curr->leftChild);
curr->leftChild=NULL;
return curr;
}
19
例：编写一个建立图 7-7(b)所示的带头结点的二叉链存
储结构二叉树的程序。
设计：假设上述二叉树结点结构体定义和二叉树操作实现函数
存放在文件, Bitree.h” 中,程序设计如下：
#include <stdlib.h>
#include <stdio.h>
typedef char DataType;
#include "Bitree.h "
20
void main(void)
{ BiTreeNode *root,*p,*pp;
Initiate(&root);
p=InsertLeftNode(root,'A');
p=InsertLeftNode(p,'B');
p=InsertLeftNode(p,'D');
p=InsertRightNode(p,'G');
p=InsertRightNode(root->leftChild,'C');
pp=p;
InsertLeftNode(p,'E');
InsertRightNode(pp,'F');
}
21
小节
?内容回顾；
?7.3 二叉树的设计和实现
? 7.3.1 二叉树的存储结构
? 7.3.2 二叉链存储结构的二叉树操作实现
下节课内容
二叉树遍历和线索二叉树
上节内容回顾
?树的基本概念
?二叉树的基本概念和性质
?两种特殊的二叉树
2
问题 1：什么是二叉树？简述树和二叉树的不同点。
答：
(1)树 (2)二叉树 (3)二叉树
二叉树是由 n(n≥0) 个结点的有限集合构成，此集合或
者为空集，或者由一个根结点及两棵互不相交的左右子树组
成，并且左右子树都是二叉树。
树与二叉树是 两类不同 的树型结构。树中并没有限定每
个子树的位置，通常是无序的，即使在有序树中，也只是限
定了各子树之间的相次序，而没有限定子树所在的位置；而
二叉树的每个结点至多有两个子树，且每个结的子树有严格
的左、右位置。
a
b c d
a
b c
a
b
e f d
3
问题 2：二叉树的性质？
答,性质 1:在一棵非空二叉树的第 i层上至多有 2i个结点（ i≥ 0）。
性质 2:深度为 k的二叉树至多有 2k+1-1个结点 (k≥ -1)。
性质 3,对于任何一棵非空的二叉树，若度为 2的结点数有 n2个，
则叶子数（ n0）必定为 n2＋ 1 （即 n0=n2+1）
性质 4,具有 n个结点的完全二叉树的深度 k必为 ?log2(n+1)?-1
性质 5:对于一棵有 n个结点的完全二叉树的结点按照从上至下
和从左至右的顺序对所有结点从 0开始顺序编号,则对于序号为
i的结点 (0≤i≤n),有：
(1)如果 i=0，则结点 i无双亲，是二叉树的根；如果 i>0，则
其双亲是结点 (i-1)/2(“/”表示整除）。
(2)如果 2i+1≥ n，则结点 i为叶子结点，无左孩子；否则，其左孩子是结点 2i+1。
(3)如果 2i＋ 2≥ n，则结点 i无右孩子；否则，其右孩子是结点 2i＋ 2。
4
问题 3：什么是两种特殊形态的二叉树？ 它们 的区别？
答,满二叉树 与完全二叉树。
在一棵二叉树中，如果所有分支结点都
存在左子树和右子树，并且所有叶子结点都
在同一层上，这样的二叉树称为 满二叉树 。
如果一棵深度为 k，有 n个结点的二叉树
中各结点能够与深度为 k的顺序编号的满二叉
树从 1到 n标号的结点相对应的二叉树称为 完
全二叉树。其特点,
(1)所有的叶结点都出现在第 k层或 k－ 1层。
(2)若任一结点，如果其右子树的最大层次为 i，
则其左子树的最大层次为 i或 i＋ 1。
a
b
d
c
e f g
1
2 3
5 64
5
满二叉树与完全二叉树的区别是：
满二叉树是叶子一个也不少的树，而完全二叉树虽然前
k-1层是满的，但最底层却允许在右边缺少连续若干个结点。
满二叉树是完全二叉树的一个特例。
6
问题 4,对于任何一棵非空的二叉树，若度为 2的结点数有
n2个，叶子数 n0必定为 n2＋ 1。试证明此结论是正确的。
证明,∵ 二叉树中全部结点数 n＝ n0+n1+n2
(叶子数＋ 1度结点数＋ 2度结点数 =全部结点数 )
又 ∵ 二叉树中全部结点数 n＝ B+1 ( 总分支数＋根结点 )
（ 除根结点外, 每个结点必有一个直接前趋, 即一个分支 ）
而 总分支数 B= n1+2n2 (1度结点必有 1个直接后继, 2度结点必
有 2个 )
由此可得,n0+n1+n2=n1+2n2 +1,即 n0=n2+1
7
问题 5、针对二叉树，回答下列问题：
(1)具有 n个结点的非空二叉树的最小深度是多少？最
大深度是多少？
（ 2）具有 n个结点的完全二叉树中有多少个叶子结点？
有多少个度为 2的结点？
（ 3）具有 n0个叶子结点的完全二叉树中共有多少个结
点？
答,(1)其 最小深度是 ?log2(n+1)?-1,最大深度是 n。
(2)具有 n个结点的完全二叉树中有 ?n/2?叶子结点，
有 ?n/2?-1个度为 2的结点。
（ 3）具有 n0个叶子结点的完全二叉树中共有 2n0
个结点或 2n0-1个结点。
8
一棵完全二叉树有 1000个结点，则它必有 个
叶子结点，有 个度为 2的结点，有 个结点只
有非空左子树，有 个结点只有非空右子树。
练习：
正确答案：
全部叶子数＝ ?1000/2? =500个。
度为 2的结点＝ 叶子总数－ 1=499个。
因为最后一个结点坐标是偶数，所以必为左子树。 有 1
个结点只有非空左子树，有 0 个结点只有非空右
子树。
9
7.3 二叉树的设计和实现
7.3.1 二叉树的顺序存储结构
二叉树的存储结构主要有三种：顺序存储结构、链式存储
结构和仿真指针存储结构。
1,二叉树的顺序存储结构
完全二叉树的结点可按从上至下和从左至右的次序存储在
一维数组中, 其结点之间的关系可由公式计算得到, 这就是二
叉树的顺序存储结构 。 图 7-4在数组中的存储结构为：
数组
下标 0 1 2 3 4 5 6
a b c d e f g
10
问题：对于一般的二叉树如何存储呢？
显然不能直接使用二叉树的顺序存储结构 。 我们可以采取
下面这种办法：首先在非完全二叉树中增添一些并不存在的空结
点使之变成完全二叉树的形态, 然后再用顺序存储结构存储 。
数组
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 (c)
(a)一般二叉树 (b)完全二叉树 （ c)在数组中的存储形式
图 7.6 一般二叉树的顺序存储结构
A B C Λ D E Λ Λ Λ F Λ Λ G
11
2,二叉树的链式存储结构
二叉树的链式存储结构是用指针建立二叉树中结点之间的
关系。 二叉树最常用的的链式存储结构是二叉链。 二叉链存储结
构的每个结点包含三个域，分别是数据域 data、左孩子指针域
leftChild和右孩子指针域 rightChild。二叉链存储结构中每个
结点的图示结构为,
leftChild data rightChild
二叉链存储结构的二叉树也有不带头结点和带头结点两种。
带头结点的二叉链存储结构的二叉树见图 7.7(b)，不带头结点
的二叉链存储结构的二叉树如图 7.7（ a）所示。
12
图 7.7 二叉链存储结构的二叉树
13
3,二叉树的仿真指针
二叉树的仿真指针存储 结构 是用数组存储二叉树中的结点，
数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常
规指针建立二叉树中结点之间的关系。
图 7.8 二叉树的仿真二叉链存储结构
14
7.3.2 二叉链存储结构的二叉树操作实现
在二叉链存储结构下, 针对一棵二叉树, 主要涉及如下几
个功能模块：
?二叉树的初始化操作；
?二叉树中给某结点插入一个左结点的操作；
?二叉树中给某结点插入一个右结点的操作；
?删除二叉树中某结点的左子树操作；
?删除二叉树中某结点的右子树操作 。
各算法的基本思想及程序实现如下：
typedef struct Node
{ DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode; /*结点的结构体定义 */
15
1.二叉树的初始化
算法的基本思想,创建二叉树的头结点。
程序实现：
void Initiate(BiTreeNode **root)
{
*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
16
2.二叉树中给某结点插入一个左结点的操作
算法的基本思想,
若当前结点 (假设为 curr）非空，在 curr的左子
树插入元素值为 x的新结点,原 curr所指结点的左
子树成为新插入结点的左子树。若插入成功返回新
插入结点的指针，否则返回空指针。
17
程序实现：
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x)
{ BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}
18
4.删除二叉树中某结点的左子树操作
算法的基本思想,若 curr非空，删除 curr所指结点的左子树。
若删除成功，返回删除结点的双亲结点指针，否则返回空指针。
程序实现：
BiTreeNode *DeleteLeftTree(BiTreeNode *curr)
{
if(curr==NULL||curr->leftChild==NULL)
return NULL;
Destroy(&curr->leftChild);
curr->leftChild=NULL;
return curr;
}
19
例：编写一个建立图 7-7(b)所示的带头结点的二叉链存
储结构二叉树的程序。
设计：假设上述二叉树结点结构体定义和二叉树操作实现函数
存放在文件, Bitree.h” 中,程序设计如下：
#include <stdlib.h>
#include <stdio.h>
typedef char DataType;
#include "Bitree.h "
20
void main(void)
{ BiTreeNode *root,*p,*pp;
Initiate(&root);
p=InsertLeftNode(root,'A');
p=InsertLeftNode(p,'B');
p=InsertLeftNode(p,'D');
p=InsertRightNode(p,'G');
p=InsertRightNode(root->leftChild,'C');
pp=p;
InsertLeftNode(p,'E');
InsertRightNode(pp,'F');
}
21
小节
?内容回顾；
?7.3 二叉树的设计和实现
? 7.3.1 二叉树的存储结构
? 7.3.2 二叉链存储结构的二叉树操作实现
下节课内容
二叉树遍历和线索二叉树
