数据结构 教学课件 作者 宗大华 陈吉人 05二叉树.ppt

《数据结构 教学课件 作者 宗大华 陈吉人 05二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第5章二叉树5.1二叉树概述5.2二叉树的存储结构5.3遍历二叉树5.4哈夫曼树及哈夫曼编码本章讨论二叉树，它是一种重要的非线性数据结构，有着广泛的用途。本章主要介绍以下几个方面的内容：二叉树的定义及性质；二叉树的存储实现（顺序存储和链式存储）；遍历二叉树（即对二叉树存储结点访问的各种形式）；哈夫曼树及编码。5.1二叉树概述所谓“二叉树”，是一个由结点组成的有限集合。这个集合或为空，或由一个称为根的结点以及两棵不相交的二叉树组成，这两棵二叉树分别称为根结点的左子树和右子树。5.1.1二叉树的基本概念当二叉树非空时，通过结点间的边来表示从一个结点到它的两

2、个子结点间的联系，这个结点称为父结点，两个子结点称为父结点的孩子。二叉树有如下的特征：二叉树可以是空的，空二叉树没有任何结点；二叉树上的每个结点最多可以有两棵子树，这两棵子树是不相交的；二叉树上一个结点的两棵子树有左、右之分，次序是不能颠倒的。图5-2两棵不同的二叉树从二叉树中的一个结点往下，到达它的某个子、孙结点时所经由的路线，称为一条“路径”。对于路径来说，从开始结点到终止结点，中间经过的结点个数，称为路径的“长度”。从根结点开始、到某个结点的路径长度，称为该结点的“深度”。在二叉树中，由于每个非根结点只有一个父结点，所以从二叉树的任一结点到它的子、

3、孙结点的路径都是唯一的。二叉树是一种层次结构。通常，把它的根算作第0层，其余结点的层次值，为其父结点所在层值加1。在二叉树里位于相同层的结点的深度都是相同的。一棵二叉树的“高度”，是指该二叉树的最大层次数值。由4个结点构成的二叉树总共有14种，其中8棵树的高度为3，6棵树的高度为2。图5-3大小为4的所有二叉树例5-4试分析由5个结点构成的二叉树一共有多少棵。解：大小为5的不同的二叉树总共有14+5+4+5+14=42种。所谓一个结点的“度”，是指该结点拥有子树的个数。对于二叉树来说，任何一个结点的度最多是2。通常，把二叉树中那些度为0的结点，称作是“叶”结点

4、。所谓“满二叉树”，是指该二叉树的每一个结点，或是有两个非空子树的结点，或是叶结点，且每层都必须含有最多的结点个数。图5-4一棵满二叉树图5-5所示的两棵二叉树都不是满二叉树。虽然它们都满足“每个结点或都有两个非空子树，或是叶结点”的条件，但却违背了“每层都必须含有最多的结点个数”的要求。图5-5非满二叉树所谓“完全二叉树”，是指该二叉树除最后一层外，其余各层的结点都是满的，且最后一层的结点都集中在左边，右边可连续缺少若干结点。图5-6两棵完全二叉树由完全二叉树的定义可知，满二叉树一定是一棵完全二叉树，但完全二叉树却不一定是一棵满二叉树。性质5-1～性质5-3

5、对任何二叉树都成立，性质5-4只是针对完全二叉树的。5.1.2二叉树的性质性质5-1在任何一棵二叉树的第i（i≥0）层上，最多有2i个结点。【证明】二叉树的第0层只有一个结点。所以，当i=0时，2i=20=1成立。假设结论对第i层成立，即第i层最多有2i个结点。由于二叉树每个结点的度最多为2，因此第i+1层结点的个数，最多应该是第i层结点个数的2倍，即22i=2i+1，命题得证。性质5-2树高为k（k≥0）的二叉树，最多有2k+1−1个结点。【证明】由性质5-1可知，在树高为k的二叉树里，第0层有20个结点，第1层有21个结点，第2层有22个结点，……，第k

6、层有2k个结点。因此，要求出树高为k的二叉树的结点个数，就是求和：20+21+22+…+2k这是一个等比数列，求前k+1项的和Sk+1的求和公式为：Sk+1=（a0–akq）/（1−q）其中a0为第1项，ak为第k+1项，q为公比。于是，该数列前k+1项之和Sk+1为：Sk+1=(20−2k2)/(1−2)=(1−2k+1)/(1−2)=2k+1−1性质5-3如果一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则有关系：n0=n2+1。【证明】设二叉树中度为1的结点个数为n1，那么二叉树总的结点个数n应该是：n=n0+n1+n2（1）另一方面

7、，二叉树中除根结点外，其余每个结点都将在一个分支边的下面。设这个分支边数为m，那么二叉树总的结点个数应该是分支边数加上1（这个1是根结点），即：n=m+1（2）注意到每一条分支边或是由度为1的结点发出，或是由度为2的结点发出，度为1的结点发出一条边，度为2的结点发出两条边。因此，又有关系：m=n1+2×n2（3）把式（3）代入式（2），得：n=n1+2×n2+1（4）综合式（1）和式（4），立即可以得出所需要的结论。性质5-4对于有n个结点的完全二叉树，将其所有的结点按照从上到下、从左到右的顺序进行编号。那么，二叉树中任意一个结点的序号i（1≤i≤n）满足下面

8、的关系：（1）如果i=1，则该结点为这