数据结构(中)清华大学出版社ppt

《数据结构(中)清华大学出版社ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构(中)1第6章树与二叉树第7章图2第六章树与二叉树3学习重点：☆树的定义及其基本术语☆二叉树的定义及性质☆二叉树的存储方法☆二叉树的遍历☆树的存储方法☆树的遍历☆二叉树与树、森林的转换☆二叉树的应用46.1树的概念及术语6.2二叉树6.3二叉树的遍历6.4二叉树与树、森林的转换6.5树的存储结构6.6树的遍历6.7二叉树的应用56.1树的概述所谓“树（Tree）”是指由n（n≥0）个结点构成的有限数据元素的集合T。当n=0时，称其为“空树”。当n≠0时，树中诸结点应该满足下面的两个条件：6.1.1树的定义6（1）有且仅有一个特定的结点，它没有前驱，是该树的根，称为树的根结点；（2

2、）除根结点外的其余结点，可分为m（m≥0）个互不相交的有限集合：T1，T2，…，Tm，每一个集合Ti（0≤i≤m）又是一棵树，被称为是根的子树。7有关树的术语（1）结点：它不仅有数据本身，还有指向其孩子的若干分支孩子结点：某结点的各子树的根，称为这个结点的孩子结点双亲结点兄弟结点：有相同双亲的孩子称为兄弟结点祖先结点：从根结点到该结点的双亲结点，都是此结点的祖先结点8有关树的术语（2）结点的度：指该结点的子树的个数叶子结点：度为0的结点，也称为终端结点分支结点：度不为0的结点，也称为非终端结点树的层数：树的根所在结点的层数为1，其他结点的层数等于它的双亲结点的层数加19有关树的术语（3）树

3、的深度：树中结点的最大层数称为树的深度（也称高度）森林：零棵或有限棵互不相交的树的集合称为森林有序树和无序树：如果树中结点的各子树从左到右是有次序的（即位置不能互换），那么这样的树称为有序树；否则是无序树。106.1.2树的基本操作1．初始化一棵空树；2．销毁一棵已存在的树；3．求树的根结点；4．求结点的的双亲结点；5．求树的深度；6．前序遍历树；7．中序遍历树；8．后序遍历树；9．层序遍历树。116.1.3树的表示方式（A（B（E，F），C（G），D（H，I（K），J））（c）树形表示法(d)广义表表法法图6.4二叉树的表示126.2二叉树二叉树，它是一种非常重要的非线性数据结构，有着广

4、泛的用途。主要介绍以下几个方面的内容：二叉树的定义及性质；二叉树的存储实现（顺序和链式存储）；遍历二叉树（即对二叉树存储结点访问的各种形式）；哈夫曼树及编码。136.2.1二叉树的定义所谓“二叉树”，是一个由结点组成的有限集合。这个集合或为空，或由一个称为根的结点以及两棵不相交的二叉树组成，这两棵二叉树分别称为根结点的左子树和右子树。14二叉树有如下的特征：二叉树可以是空的，空二叉树没有任何结点；二叉树上的每个结点最多可以有两棵子树，这两棵子树是不相交的；二叉树上一个结点的两棵子树有左、右之分，次序是不能颠倒的。15图6.6二叉树的五种基本形态(a)(b)(c)(d)(e)166.2.2二

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

6、2+…+2k-1=2k-1.证毕18性质3:如果一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则有关系：n0=n2+1。【证明】设二叉树中度为1的结点个数为n1，那么二叉树总的结点个数n应该是：n=n0+n1+n2（1）19另一方面，二叉树中除根结点外，其余每个结点都有一个向上的分支指向其父结点。如设二叉树种分支边数为m，那么二叉树总的结点个数n应该是分支边数m加上1（这个1是根结点），即：n=m+1（2）20注意到每一条分支边或是由度为1的结点发出，或是由度为2的结点发出，度为1的结点发出一条边，度为2的结点发出两条边。因此，又有关系：m=n1+2×n2（3）把式（3）代

7、入式（2），得：n=n1+2×n2+1（4）综合式（1）和式（4），立即可以得出所需要的结论。21两种特殊形态的二叉树满二叉树：深度为k并且含有2k-1个结点的二叉树称，如图6.7所示。对满二叉树的结点可以从根结点开始自上向下，自左至右顺序编号，图6.7中每个结点上的数字即是该结点的编号。完全二叉树：深度为k，含有n个结点的二叉树，当且仅当每个结点的编号与相应满二叉树结点顺序编号从1到n相对应时，则称此二叉树为完全二叉树