数据结构第6章树和二叉树

《数据结构第6章树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树本章主题：树、二叉树教学目的：掌握树和二叉树的类型定义、运算及存储结构教学重点：树的各种表示、各种存储方式和运算，二叉树的概念及其运算和应用教学难点：二叉树的非递归运算及应用主要内容：树二叉树树、森林与二叉树的转换树的应用本章学习导读本章主要介绍树的基本概念，树的存储结构，树和二叉树的遍历等一些常用算法。通过本章学习，读者应该：1)熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。2)理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。3)熟练掌握二叉树和树的各种存储结构及建立的算

2、法。4)学会编写实现树的各种操作的算法。5)了解最优二叉树的特性，掌握建立最优二叉树和哈夫曼编码的方法。数据结构:线性结构和非线性结构线性结构(线性表,栈,队列等)非线性结构:至少存在一个数据元素有不止一个直接前驱或后继(树,图等)树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为

3、时，可用树来描述其执行过程。等等。6.1.1树型结构实例1．家族树6.1树的逻辑结构和存储结构图6-1家族树2．书的目录结构图6-2书的目录66.1.2树的定义1．树的定义树(Tree)是n(n≥0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件：(1)有且仅有一个结点没有前驱，称该结点为根结点(Root)；(2)除根结点以外，其余结点可分为m(m≥0)个互不相交的有限集合T0，Tl，…，Tm-1。其中每个集合又构成一棵树，树T0，Tl，…，Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个直接前

4、驱，但可以有0个或多个后继。树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。6.1树的逻辑结构和存储结构7图6-3树的示例图6-3(a)是一棵只有一个根结点的树；图6-3(b)是一棵有12个结点的树，即T={A，B，C，…，K，L}。A是棵根，除根结点A之外，其余的11个结点分为三个互不相交的集合。T1，T2和T3是根A的三棵子树，且本身又都是一棵树。所以树的定义是递归的。返回2．树的基本术语树的结点包含一个数据元素及若干指向其子树的分支。1.树的结点:包含一个D

5、E和指向其子树的所有分支;2.结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值Max(D(I))含义:树中最大分支数为树的度;4.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度5.森林:是m(m>=0)棵互不相的树的集合森林与树概念相近,相互很容易转换.6.有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。7.森林:是m（m≥0）棵互不相交的树的集合。在树结构中，结

6、点之间的关系又可以用家族关系描述，定义如下：8.孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。9.子孙:以某结点为根的子树中的所有结点都被称为是该结点的子孙。10.祖先:从根结点到该结点路径上的所有结点。11.兄弟:同一个双亲的孩子之间互为兄弟。12.堂兄弟:双亲在同一层的结点互为堂兄弟。3.树的基本运算树的基本运算主要有：⒈初始化操作INITIATE(T)：创建一棵空树。⒉求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。⒊求双亲函数PARENT(T,x)：在树T中求x的双亲。⒋求第i个

7、孩子函数CHILD(T,x,i)：在树T中求结点x的第i个孩子。⒌建树函数CRT-TREE(x,F)：建立以结点x为根，森林F为子树的树。6.遍历树操作TRAVERSE(T)：按顺序访问树T中各个结点。6.1.3树的表示树的逻辑表示方法有多种，常见的有：1．树形图表示法2．嵌套集合表示法（文氏图表示法）3．凹入表示法4．广义表表示法2021/7/19126.1.3树的存储结构和线性表一样，树可以用顺序和链式两种存储结构。树的顺序存储结构适合树中结点比较“满”的情况。根据树的非线性结构特点，常用链式存储方式来表示树。树常用的存储方法有：双亲

8、存储表示法、孩子链表表示法和孩子兄弟链表表示法。1．双亲存储表示法一般采用顺序存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域：data域-----存放结点的信息；par