第5章 树和二叉树

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

1、第4章内容回顾单链表的基本操作，包括插入、删除以及查找双向链表和循环链表的区别树和二叉树第五章预习检查什么是二叉树树的遍历有哪几种方式树有那些应用2021/10/84本章目标了解树的定义和基本术语了解二叉树的定义、性质、和存储结构掌握二叉树的遍历本章结构树的逻辑结构和存储结构树和二叉树二叉树遍历二叉树2021/10/865.1.1树型结构实例1．家族树5-1树的逻辑结构和存储结构图5-1家族树2021/10/872．书的目录结构图5-2书的目录5-1书的目录结构2021/10/885.1.2树的定义1．树的定义树(Tree)是n(n≥

2、0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件：(1)有且仅有一个结点没有前驱，称该结点为根结点(Root)；(2)除根结点以外，其余结点可分为m(m≥0)个互不相交的有限集合T0，Tl，…，Tm-1。其中每个集合又构成一棵树，树T0，Tl，…，Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。5-1树的逻辑结构和存储结构2021/1

3、0/89图5-3树的示例图5-3(a)是一棵只有一个根结点的树；图5-3(b)是一棵有12个结点的树，即T={A，B，C，…，K，L}。A是棵根，除根结点A之外，其余的11个结点分为三个互不相交的集合。T1，T2和T3是根A的三棵子树，且本身又都是一棵树。所以树的定义是递归的。2021/10/8102．树的基本术语树的结点包含一个数据元素及若干指向其子树的分支。1.树的结点:包含一个数据元素和指向其子树的所有分支;2.结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值Max(D(I))含义:

4、树中最大分支数为树的度;4.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度5.森林:是m(m>=0)棵互不相的树的集合森林与树概念相近,相互很容易转换.6.有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。2021/10/8117.森林:是m（m≥0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：8.孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。

5、9.子孙:以某结点为根的子树中的所有结点都被称为是该结点的子孙。10.祖先:从根结点到该结点路径上的所有结点。11.兄弟:同一个双亲的孩子之间互为兄弟。12.堂兄弟:双亲在同一层的结点互为堂兄弟。2021/10/8123.树的基本运算树的基本运算主要有：⒈初始化操作INITIATE(T)：创建一棵空树。⒉求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。⒊求双亲函数PARENT(T,x)：在树T中求x的双亲。⒋求第i个孩子函数CHILD(T,x,i)：在树T中求结点x的第i个孩子。⒌建树函数CRT-TREE(x,

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

7、用一组地址连续的存储单元来存放树的结点，每个结点有两个域：data域-----存放结点的信息；parent域-----存放该结点双亲结点的位置特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量。5-1-4树的存储结构2021/10/815存储结构描述为：#defineMaxTreeSize100//定义数组空间的大小typedefcharDataType；//定义数据类型typedefstruct{DataTypedata；//结点数据intparent；//双亲指针，指示结点的双亲在数组中的位置}PTreeNode；typed

8、efstruct{PTreeNodenodes[MaxTreeSize];intn；//结点总数}PTree；PTreeT；//T是双亲链表2021/10/8162．孩子链表表示法这是树的链式存储结构。每个结点的孩子用单