数据结构实用教程(c语言版)第5章树.ppt

《数据结构实用教程(c语言版)第5章树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实用教程（C语言版）中国水利水电出版社第5章树本章中主要介绍下列内容：树的逻辑定义和存储结构二叉树的逻辑定义、存储结构二叉树的基本操作算法树和二叉树的转换哈夫曼树及其应用本章目录5.1树15.2二叉树25.3二叉树的建立和遍历35.4树、森林与二叉树的转换45.5哈夫曼树55.6本章小结6结束5.1树5.1.1树的定义5.1.2树的表示方法5.1.3树的基本术语5.1.4树的存储结构返回到总目录5.1.1树的定义树是n（n≥0）个结点的有限集合。当n=0时称为空树。当n>0时，是非空树，它满足以下两个

2、条件：（1）有且仅有一个称为根的结点；（2）其余结点分为m（m≥0）个互不相交的非空集合T1，T2，…，Tm，其中每个集合本身又是一棵树，称为根的子树。返回到本节目录树的二元组表示法树可用二元组来表示。其中，D为结点集合，R为边的集合。一棵树T如图5-1所示，则它的二元组表示方法为：T=（D,R）D={A,B,C,D,E,F,G,H}R={,,,,,,,}图5-1树的逻辑结构图返回到本节目录5.1.2树的表示方法树的逻辑结构表示有

3、树形表示法，文氏图表示法，凹入表示法和广义表表示法等。1．树形表示法这是树的最基本的表示，使用一棵倒置的树表示树结构。图5-1就是采用这种方法。2．文氏表示法使用集合以及集合的包含关系描述树结构。图5-2（a）就是图5-1的树的文氏图表示法。3．凹入表示法使用线段的伸缩关系描述树的结构。图5-2（b）就是图5-1的树的凹入表示法。4．广义表表示法将树的根结点写在括号的左边，除根结点外的其余结点写在括号内并用逗号间隔来描述树的结构。图5-2（c）就是图5-1的树的广义表表示法。返回到本节目录树的三种表示方法(a

4、)文氏图表示法(b)凹入图表示法(c)广义表表示法图5-2树的其它表示方法返回到本节目录5.1.3树的基本术语1．结点树的结点包含一个数据元素及若干指向其子树的分支。2．结点的度结点所拥有的分支数目或后继结点个数称为该结点的度（Degree）。例如图5-1所示的树中结点A的度为3，结点C的度为2，结点E的度为0。3．树的度树中各结点度的最大值称为该树的度。例如图5-1所示的树的度为3。4．叶子（终端结点）度为零的结点称为叶子结点。例如图5-1所示的树中结点E、G、H、I为叶子结点。返回到本节目录5.1.3树的

5、基本术语5．分支结点度不为零的结点称为分支结点。例如图5-1所示的树中的A、B、C、D、F都是分支结点。6．孩子结点一个结点的后继称为该结点的孩子结点。例如图5-1所示的树中A的孩子结点为B、C、D。7．双亲结点一个结点称其为其后继结点的双亲结点。例如图5-1所示的树中A是B、C、D的双亲结点，C是F、G的双亲。8．兄弟结点同一双亲结点下的孩子结点互称为兄弟结点。例如图5-1所示的树中B、C、D互为兄弟结点，F、G互为兄弟结点，但不同双亲的两个同层结点不互为兄弟结点，如G和H不互为兄弟结点。返回到本节目录5.

6、1.3树的基本术语9．堂兄弟双亲互为兄弟的两个结点互称为堂兄弟。例如图5-1所示的树中G和H就互为堂兄弟。10．子孙结点一个结点的所有子树中的结点称之为该结点的子孙结点。例如图5-1所示的树中A的子孙为B、C、D、E、F、G、H、I。11．祖先结点从树根结点到达一个结点的路径上的所有结点称为该结点的祖先结点。例如图5-1所示的树中E的祖先结点为A和B（包括其双亲结点B）。返回到本节目录5.1.3树的基本术语12．层数树的根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。例如图5-1所示的树中A的层数为

7、1，B、C、D的层数为2，E、F、G、H的层数为3，I的层数为4。13．树的深度树中结点的最大层数称为树的深度（或高度）。例如图5-1所示的树中的深度为4。14．有序树和无序树如果一棵树中的结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成了不同的树，称这样的树为有序树，反之，则为无序树。15．森林m（m≥0）棵互不相交树的集合称为森林。返回到本节目录5.1.4树的存储结构1.双亲表示法用一个一维数组存储树中的各个结点，数组元素是一个结构体型数据，包含两个域：data域和parent域，

8、分别表示结点的数据值和其双亲结点在数组中的下标。其类型定义如下：typedefstruct{ElemTypedata;/*结点的数据域，ElemType可以是任意类型*/intparent;/*结点存储其双亲的数组下标值*/}ParType[MaxSize];返回到本节目录1.双亲表示法示例图5-1中给出的树，可以用图5-3来存储表示。其中，规定数组下标为0的位置存储的是根结点，设根结点的paren