第六章树和二叉树ppt课件.ppt

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

1、第6章树数据结构（C描述）6.6哈夫曼树6.5树和森林6.4线索二叉树6.3遍历二叉树6.2二叉树6.1树的基本概念目录6.1树的基本概念6.1.1树的定义1．树的定义树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则：（1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；（2）除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可

2、以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。树的结构参见图6-1。AABCDIHGFEJKLM（a）空树（b）仅含有根结点的树（c）含有多个结点的树图6-1树的示意图ø在图6-1(c)中，树的根结点为A该树还可以分为三个互不相交子集T0，T1，T2，其中T0={B，E，F，J，K，L}，T1={C，G}，T2={D，H，I，M}，其中的T0，T1，T2都是树，称为图6-1（C）中树的子树，而T0，T1，T2又可以分解成若干棵不相交子树。图6-2图6-1(C)的树的三个子

3、树CGBEFJKLDHIM(a)T0子树图2-6图6-1(C)的树的三个子树(b)T1子树(c)T2子树2．树的逻辑结构描述一棵树的逻辑结构可以用二元组描述为：tree=(k,R)k={ki∣1≤i≤n;n≥0,kielemtype}R={r}其中，n为树中结点个数，若n=0，则为一棵空树，n>0时称为一棵非空树，而关系r应满足下列条件：（1）有且仅有一个结点没有前驱,称该结点为树根;（2）除根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。例如，对图6-1的树结构,

4、可以二元组表示为：ABCDIHGFEJKLM图6-1树的示意图K={A，B，C，D，E，F，G，H，I，J，K，L，M}R={r}r={(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)}数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系:(1)在D中存在唯一的称为根的数据元素root；它在H下无前驱(2)若D-{root}≠Ø，则存在D-

5、{root}的一个划分D1,D2,…,Dm（m>0)，对任意j≠k，有Dj∩Dk=Ø,且对任意的i，唯一存在数据元素xi∈Di,有∈H;(3)对应于D-{root}的划分，H-{，…}有惟一的一个划分H1,…Hm(m>0)，对任意j≠k，有Hj∩Hk=Ø,且对任意的i，Hi是Di上的关系，（Di,{Hi})是一棵符合本定义的树，称为根root的子树。数据关系R：ADTTree{3．树的抽象数据类型描述基本操作：查找类插入类删除类Root(T)//求树的根结点查找

6、类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,valu

7、e)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树1．树形结构表示法树的表示方法有多种。下图中的树形表示法是其中的一种，也是最常用的一种。在这种表示方法中，结点之间的关系是通过连线表示的，虽然每条线上都不带有箭头（即方向)，但它并不是无向的，而是有向的，其方向隐含从上到下，即连线的上方结点是下方结点的前

8、驱，下方结点是上方结点的后继。4．树的表示形式ABCDIHGFEJKLM图6-2树的树形表示法2.凹入法表示法每棵树的根对应着一个条形，子树的根对应着较短的条形，且树根在上，子树的根在下。具体参见图6-3。A图6-3树的凹入法表示ABEJKLFCGDHMIABCDIHGFEJKLM图6-2树的树形表示法3.嵌套集合表示法（集合图表示法）每棵树对应一个圆形，园