数据结构之树和二叉树(.ppt

《数据结构之树和二叉树(.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树6.4线索二叉树6.5树和森林6.6哈夫曼树教学目的、要求1．领会树和二叉树的类型定义，理解树和二叉树的结构差别。2．熟记二叉树的主要特性，并掌握它们的证明方法。3．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。4．理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5．熟练掌握二叉树和树的各种存储结构及其建立的算法。6．学会编写实现树的各种操作的算法。7．了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。6.1树的定义和基本术语6.1.1树的定义树

2、是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则：①有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；②除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。树的结构参见下图：图6.1树的结构在图6.1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，其中T0={B，E，

3、F，J，K，L}，T1={C，G}，T2={D，H，I，M}，其中的T0，T1，T2都是树，称为图6.1(C)中树的子树，而T0，T1，T2又可以分解成若干棵不相交子树。如T0可以分解成T00，T01两个不相交子集，T00={E，J，K，L}，T01={F}，而T00又可以分为三个不相交子集T000，T001，T002，其中，T000={J}，T001={K}，T002={L}。树的抽象数据类型定义见教材P118-1196.1.2基本术语1.结点指树中的一个数据元素，一般用一个字母表示。2.度一个结点包含子树的数目，称为该结点的度。3.树叶（叶子）度为0的结点，称

4、为叶子结点或树叶，也叫终端结点。4.孩子结点若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6.1（c）中A的孩子为B，C，D。5.双亲结点若结点X有子女Y，则X为Y的双亲结点。6.祖先结点从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D，H。7.子孙结点某一结点的子女及子女的子女都为该结点子孙。8.兄弟结点具有同一个双亲的结点，称为兄弟结点。9.分枝结点除叶子结点外的所有结点，为分枝结点，也叫非终端结点。10.层数根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。11.树

5、的深度（高度）树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。12.树的度树中结点度的最大值称为树的度。13.有序树若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。14.无序树若一棵树中所有子树的次序无关紧要，则称为无序树。15．森林若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。6.1.3树的表示1.树形结构表示法2.凹入法表示法图6.1（c）的树的凹入法表示3.嵌套集合表示法图6.1（c）的嵌套集合表示4.广义表表示法对图6-1（c）的树结构，广义表表示法可表示为：（A（B（E（J

6、，K，L），F），C（G），D（H（M），I）））6.1.4树的性质性质1树中的结点数等于所有结点的度加1。证明：根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个直接前驱，也就是说，每个结点与指向它的一个分支一一对应，所以，除根结点以外的结点数等于所有结点的分支数（即度数），而根结点无直接前驱，因此，树中的结点数等于所有结点的度数加1。性质2度为k的树中第i层上最多有ki-1个结点（i≥1）。下面用数学归纳法证明：对于i=1，显然成立，假设对于i-1层，上述条件成立，即第i-1层最多有ki-2个结点，对于第i层，结点数最多为第i-1层结点数的k倍（因为

7、度为k），故第i层的结点数为ki-2*k=ki-1。性质3深度为h的k叉树最多有个结点。证明：由性质2可知，若每一层的结点数最多，则整个k叉树结点数最多，共有当一棵K叉树上的结点数达到时，称为满K叉树。性质4具有n个结点的k叉树的最小深度为。（表示取不小于x的最小整数）证明：设具有n个结点的k叉树的深度为h，在该树的前面h-1层都是满的，即每一层的结点数等于ki-1个(1≤i≤h-1)，第h层（即最后一层）的结点数可能满，也可能不满，这时，该树具有最小的深度。由性质3知道，结点数n应满足下面条件：通过转换为：kh-1

8、可以得到：