教学资料.doc

一、二叉树的定义

A是整棵树的根结点，是B和E的双亲结点；

B和E分别是A的左、右孩子，所在的子树分别是左子树和右子树；

D、F、G是三个叶子结点

二叉树：每个结点至多只有两棵子树，并且子树有左右之分，其次序不能任意颠倒。

二叉树可以有五种基本形态：或为空，或是由一个根结点加上两棵分别为左子树和右子树的、互不相交的二叉树组成。

二叉树的基本操作:

InitBiTree(&T); 构造空二叉树T

CreateBiTree(&T); 构造二叉树T

DestroyBiTree(&T); 销毁二叉树T

ClearBiTree(&T); 将二叉树T清为空树

BiTreeEmpty(T); 若T为空二叉树，返回TRUE，否则FALSE

BiTreeDepth(T); 返回T的深度

Root(T); 返回T的根

二、二叉树的性质

性质1 在二叉树的第层上至多有个结点（）。

性质2 深度为的二叉树至多有个结点（）。

性质3 对任何一棵二叉树，如果其叶子结点数为,度为2的结点数为，则。

例题1：在一棵二叉树第5层上的结点数最多是多少？

根据性质1，=5，==16

例题2：某二叉树中，度为2的结点有18个，则该二叉树的叶子结点是多少个？

根据性质3，=18，=18+1=19

一棵深度为且有个结点的二叉树称为满二叉树。如下图:

一棵深度为的，有个结点的二叉树，当且仅当其每一个结点都与深度为的满二叉树中编号从1至的结点一一对应时，称之为完全二叉树。如下图:

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

性质5 如果对一棵有个结点的完全二叉树（其深度为）的结点按层序编号（从第一层到层，每层从左到右），则对任一结点（）有

1. 如果，则结点是二叉树的根，无双亲；如果>1,则其双亲结点是。

2. 如果2>,则结点无左孩子（结点为叶子结点）；否则其左孩子是结点2。

3. 如果2>,则结点无右孩子；否则其右孩子是结点2。

例3：一棵完全二叉树共有699个结点，则该二叉树中的叶子结点个数是？

根据性质2 深度为的二叉树至多有个结点

可以判断，该完全二叉树深度为10

（或者根据性质4，深度为=）

则前九层构成了一个满二叉树，共有==511个结点，699-511=188就是第十层上的结点数，也就是叶子结点。

第九层的叶子结点=第九层所有结点数-第十层双亲结点数

第九层的结点共有==256个，

第十层的双亲结点数=188/2=94个

该完全二叉树的叶子结点数=第十层的叶子结点+第九层的叶子结点=188+（256-94）=350个

考虑另一种更简单的做法：

完全二叉树只有度为0和度为2的两种结点，则=699

根据性质3 可得，+1=699，=349

=349+1=350

总结：树和二叉树是数据结构课程的重点之一，也是后续章节的基础。二叉树是最简单也是最重要的树形结构，需要重点掌握。

《数据结构》中“二叉树的定义和性质”的学习成果目标设计

在本单元结束时，你将能够:

1、 “判断二叉树是否是树的一种”

2、 “可以准确地辨别一棵二叉树、满二叉树以及完全二叉树”

3、 “证明二叉树的五种性质”

4、 “计算与性质相关的习题，比如：已知二叉树中度为2的结点个数，可以计算该二叉树的叶子结点个数；在一棵二叉树第5层上的结点数最多个数””

简要说明：

1、树型结构是非常重要的一类非线性数据结构，其中以树和二叉树最为常用。学生应该首先清楚二叉树和树之间的区别和联系，然后再牢牢掌握二叉树的定义和性质。本单元的学习是后续学习遍历二叉树、线索二叉树以及树、森林与二叉树转换等重要知识的基础。

2、树结构在计算机领域中得到广泛应用，所以在本章内容学习后，学生在数据库系统或编译程序等其他课程学习时，可以更好地理解关于树形结构的课程内容。

任务评价设计：

1、简述：二叉树是一种特殊的树吗？     （10分）

2、判断下图中的树是否是二叉树，如果是，判断是否是完全二叉树。（20分）

3、已知二叉树中度为2的结点为18个，计算该二叉树的叶子结点个数，并给出运算过程。（20分）

4、一棵完全二叉树共有699个结点，则该二叉树中的叶子结点个数是？ （50分）

学习活动设计:

 活动设计模板