数据结构 教学课件 作者 宗大华 宗杰 黄芳 《数据结构》大本课件-5.ppt

《数据结构 教学课件 作者 宗大华 宗杰 黄芳 《数据结构》大本课件-5.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第5章二叉树5.15.25.3本章讲述内容：5.4二叉树概述二叉树的存储结构遍历二叉树哈夫曼树及哈夫曼编码5.5线索二叉树二叉树上的每个结点最多可以有两棵子树，这两棵子树是不相交的。二叉树上一个结点的两棵子树有左、右之分，次序是不能颠倒的。所以，二叉树是有序的。5.1二叉树概述5.1.1二叉树的基本概念二叉树的定义1.二叉树具有的特征2..所谓“二叉树”，是一个由结点组成的有限集合。这个集合或者为空，或者由一个称为根的结点以及两棵不相交的二叉树组成，这两棵二叉树分别称为这个根结点的左子树和右子树。AABCABCФ根结点根结点

2、根结点左子树右子树左子树ABC根结点左子树右子树DEF(空二叉树)..二叉树可以是空的，空二叉树没有任何结点，仍用符号“Ф”表示。..当二叉树非空时，是通过结点之间的一条边来表示从一个结点到它的两个子结点（如果有的话）间的联系的，这个结点称为父结点，两个子结点称为父结点的孩子。一棵二叉树的“高度”，是指该二叉树的最大层次数值。二叉树的高度，有时也称为是二叉树的深度。从二叉树的一个结点往下，到达它的某个子、孙结点时所经由的路线，称为一条“路径”。对于一条路径来说，从开始结点到终止结点，中间经过的结点个数，称为路径的“长度”。特

3、别地，从根结点开始、到达某个结点的路径长度，称为该结点的“深度”。ABC根结点右子树DEF第0层第1层第2层第3层二叉树的基本概念3...在二叉树中，由于每个非根结点只有一个父结点，所以从二叉树的任一结点到它的子、孙结点的路径都是唯一的。.二叉树是一种层次结构。通常，把一棵二叉树的根算作第0层，其余结点的层次值，为其父结点所在层值加1。..所谓一个结点的“度”，是指该结点拥有子树的个数。对于二叉树来说，任何一个结点的度最多是2。通常，把二叉树中那些度为0的结点，称作是“叶结点”。.叶结点—没有非空子树（即度为0）的结点。(1

4、)一棵一般的二叉树，是由如下的3类结点组成的：根结点—二叉树的起始结点；(2)分支（或内部）结点—至少有一个非空子树（即度为1或2）的结点；(3)左子树满二叉树和完全二叉树4..所谓“满二叉树”，是指该二叉树的每一个结点，或者有两个非空子树，或者是叶结点，并且每层都必须含有最多的结点个数。DHIEJKBFLMGNOCA根结点分支结点叶结点不是满二叉树的例子.DEFGBCADHIEJKBFLMGCA.所谓“完全二叉树”，是指该二叉树除最后一层外，其余各层的结点都必须是满的，最后一层的结点都必须集中在左边，右边可以连续缺少若干个

5、结点。DHIEJKBFLGCADHEBFGCA.满二叉树与完全二叉树间的关系是：满二叉树一定是一棵完全二叉树，但完全二叉树却不一定是一棵满二叉树。如果一棵二叉树不是完全二叉树，那么它绝不可能是一棵满二叉树。二叉树的第0层只有一个结点。所以，当i=0时，2i=20=1成立。假设第i层最多有2i个结点。那么，由于二叉树每个结点的度最多为2，因此第i+1层结点的个数，最多应该是第i层结点个数的2倍，即22i=2i+1，命题得证。5.1.2二叉树的性质下面的性质5-1～性质5-3对任何二叉树都成立，性质5-4只对完全二叉树成立。由

6、于满二叉树一定是完全二叉树，因此性质4既适用于完全二叉树，也适用于满二叉树。性质5-1在任何一棵二叉树的第i（i≥0）层上，最多有2i个结点。.【证明】性质5-2【证明】树高为k（k≥0）的二叉树，最多有2k+1−1个结点。由性质5-1可知，在树高为k的二叉树里，第0层有20个结点，第1层有21个结点，第2层有22个结点，……，第k层有2k个结点。因此，要求出树高为k的二叉树的结点个数，就是求和：20+21+22+…+2k这是一个等比数列，求前k+1项的和Sk+1的求和公式为：Sk+1=（a0–akq）/（1−q）其中a0

7、为第1项，ak为第k+1项，q为公比。于是，该数列前k+1项之和Sk+1为：Sk+1=(20−2k2)/(1−2)=(1−2k+1)/(1−2)=2k+1−1一棵高度为9的满二叉树有多少个叶结点？有多少个度为2的结点？总共有多少个结点？如果一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则有关系：n0=n2+1。二叉树中度为1的结点个数为n1，那么二叉树总的结点个数n应是：n=n0+n1+n2(1)另一方面，二叉树中除根结点外，其余结点都将在某个分支边下面。设这个分支边数为m，那么二叉树总的结点个数应该是分支

8、边数加上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)，立即可