资源描述：
《数据结构 第6 章树.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第六章树前几章，讨论了线性结构，如线性表、栈、队列以及线性结构的扩充(多维数组和广义表)。但在系统软件和应用软件的设计中，很多情况下需要描述数据的层次关系。本章讨论一种非线性数据结构：树和二叉树(即层次结构)。它能对数据结构随机再组织，故称树为动态结构。本章涉及内容：树和二叉树的定义、操作、性质、存储结构、二叉树的遍历、线索化和树与二叉树之间的转换等问题，最后给出二叉树的一个典型应用——Huffman（哈夫曼）编码及译码。7/25/2021116.1树的基本概念例6-１IBMPCDOS中文件结构是一棵树，如图6
2、.1：MFD(根节点)子目录A子目录B子目录A1子目录A2文件文件文件文件文件文件有向弧等为关系叶节点分支节点7/25/202121树的基本概念例6-2编译系统中将表达式组织成一棵树，如a+b*(c-d)-e/f的树结构：6.1.1树的定义及基本操作1．定义：树(Tree)是n（n≥0）个节点满足层次关系的有限集，当n=0时，称为空树,记为Φ；当n＞0时，称为非空树。对非空树T满足下列条件：（1）T有且仅有一个称为根（root）的节点；（2）T的其余节点可分为m(m≥0)个互不相交的有限集：T1，
3、T2..，Tm,Ti(1≤i≤m)为根的子树(subtree)。显然,这是一个递归定义,即当子树Ti非空时,又要满足定义中的(1)和(2)。—abcdef/*—+3树的定义树T可形式化描述，即：T＝（D，R）其中D，R分别为元素集和关系集，若D=φ，则树T为空树，否则有：D＝{root}∪DF,root∈datatype,为根元素,DF=根下各子树Ti的元素集：(m≥0)，且Di∩Dj=φ(不相交)，1≤i，j≤m，i≠j。ri是root的子树Ti之根,Ti=(Di,R)——递归；R=Di={
4、ri}UDFi,1≤i≤m，m＞0；фm=04树的定义例设树T：这里：D={A}∪DF，DF=D1∪D2，D1={B}∪DF1，DF1=D11∪D12，D11={E}，D12={F}，D2={C},故D＝{A,B,C,E,F},而R={,,,}。ACBEF有向弧的箭头可省去5树的定义及特点从树T的定义可以看出其特点：根无上层节点（或称为父节点、直接前驱），叶节点无下层节点（或称孩子节点、直接后继），其它节点（分支节点）有唯一的一个直接前驱节点和若干个直接后继节点。2．树的
5、逻辑结构表示法1）层次表示法前面关于树的一些例子，都属于层次表示法，它比较直观地表示了树中各节点的层次关系。下面对树的讨论，都采用这种表示法。2）嵌套表示法：如：3）广义表表示法：如例6-5中的树，可表示为：(A，B(E,F)，C)。ACBEFACBEF63.树的基本术语（1）节点：由数据元素(data)及若干连接子树的分支（指针）组成一个节点，即节点=data+pointers，其逻辑形式和存储形式如图6.7所示。逻辑形式：存储形式：（2）节点的出度（OD）：节点拥有的非空子树数目。（3）节点的入度(ID)：
6、指向节点的分支（或有向弧、指针）的数目。（4）树的度（TD）：树中节点出度的最大值。如树T：datap1p2…pn（连接子树的根）(指向各子树的根节点）图6.7ACBEF此树中OD(A)=3，OD(B)=1。显然，叶节点的出度为0。根据树的特点，根的入度为0，其它各节点的入度=1。此树的度为3，它决定了分配给节点的指针数目。度=K的树称为K叉树。data7树的基本术语（5）节点之间的关系节点的孩子（或子女）：节点的子树之根为该节点的孩子。如图6.8中，A的孩子分别为B，C，D，反之,B，C，D的双亲（父节点）为
7、A。节点的兄弟：同一双亲下的孩子为兄弟。如图6.8中，B、C、D为兄弟,且B是C的左兄弟，D是C的右兄弟。而E和F之间为堂兄关系。（6）节点的层次：对非空树，根为第一层，根下的孩子节点为第二层，依次类推。层次数的最大值为该树的深度。（7）有序树和无序树：若树中任一节点的各子树从左到右有序，则该树为有序树（强调子树的次序），否则为无序树。设T1、T2：ADBECFACBABC若T1，T2为有序树，它们是两棵不同的树；若T1，T2为无序树，它们是两棵相同的树。图6.88树的基本术语（8）森林（或树林）：m(m≥0)
8、棵互不相交的有序树的有序集合。例6-6设树T1、T2、T3如图6.8所示：则F={T1,T2,T3}构成一个森林。4．树的抽象数据类型根据上面的定义，我们可以定义如下的抽象数据类型：ADTTree{数据元素集：D（前面已介绍）；数据关系集：R；基本操作集：P；ACBDFEGH9树的抽象数据类型TreeInit(&T)操作结果：构造空树T。TreeDestroy(&T)初始条件：树T存在
