数据结构第六章树和二叉树课件.ppt

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

1、第六章树和二叉树★树形结构是一类重要的非线性数据结构第一节树的定义和基本术语一、树的定义★Atreeisafinitesetofoneormorenodessuchthat:◆树是n个结点（n≥1）的有限集树的定义1、Thereisaspeciallydesignatednodescalledroot.★有且只有一个特定的结点称为根◆designate=appoint，指定speciallydesignate特别指定、特定树的定义2、Theremainingnodesarepartitionedintom≥0disjoints

2、etsT1，T2，…，Tm，★其余的结点可以分为m个（m≥0）互不相交的有限集T1，T2，…，Tm树的定义3、whereeachofthesesetisatree，WecallT1，T2，…，Tmthesubtreesoftheroot.★其中每一个集合本身又是一颗树，我们将T1，T2，…，Tm称为根的子树树的定义★典例分析（P118图6.1）◆图a：只有一个根结点的树◆图b：有着13个结点的树ABCDEFGHIJKLM树的定义★上图是有13个结点的树◆其中A是根，其余结点分成3个互不相交的子集◆T1={B，E，F，K，L}，

3、T2={C，G}，T3={D，H，I，J，M}，T1，T2和T3都是根A的子树，且本身也是一颗树二、树的抽象数据类型★上述树的结构定义加上树的一组基本操作就构成了抽象数据类型树的定义ADTTree{数据对象D：D是具有相同特性的数据元素的集合数据关系R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集；否则R={H}，H是如下的二元关系⑴在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；⑵若D-{root}≠Φ，则存在D-{root}的一个划分，D1，D2，…，Dm（m≥0），对任意的j≠k（1≤j，k≤m

4、）有Dj∩Dk＝Φ，且对任意的i（1≤i≤m），唯一存在数据元素xi∈Di，有∈H基本操作P：InitTree（&T）；操作结果：构造空树TDestroyTree（&T）；初始条件：树T存在操作结果：销毁树TCreateTree（&T，definition）；初始条件：definition给出树的定义操作结果：按definition构造树TClearTree（&T）；初始条件：树T存在操作结果：将树T清为空树TreeEmpty（T）；初始条件：树T存在操作结果：若T为空树，则返回TRUE，否则返回FALSET

5、reeDepth（T）；初始条件：树T存在操作结果：返回树T的深度Root（T）；初始条件：树T存在操作结果：返回T的根Value（T，cur_e）；初始条件：树T存在，cur_e是T中某个结点操作结果：返回cur_e的值三、树的一些基本术语★Therearemanytermsthatweusewhenreferringtotrees.◆在对树进行分析的时候，我们会使用到一些术语树的一些基本术语★node（结点）◆Anodestandsfortheitemofinformationandthebrachedtoothernod

6、es.◆树的结点包含一个数据元素及若干指向其子树的分支树的一些基本术语★Thedegreeofanode（结点的度）◆Thedegreeofanodeisthenumberofsubtreesofthenode.◆结点拥有的子树称为结点的度（典例分析）树的一些基本术语★Thedegreeofatree（树的度）◆Thedegreeofatreeisthemaximumdegreeofthenodesinthetree.◆树内各结点的度的最大值树的一些基本术语★Leaforterminalnode（叶结点、终端结点）◆Anode

7、withdegreezeroisaleaforterminalnode.◆度为0的结点称为叶结点或终端结点树的一些基本术语★ChildandParent（孩子和双亲）◆Anodethathassubtreesistheparentoftherootsofthesubtrees，andtherootsofthesubtreesarethechildrenofthenode.◆结点的子树的根称为该结点的孩子，而相应地，该结点称为孩子的双亲树的一些基本术语★Sibling（兄弟）◆Childrenofthesameparentare

8、siblings.◆同一个双亲的孩子之间互称兄弟树的一些基本术语★Ancestor（祖先）◆Theancestorsofanodeareallthenodesalongthepathfromtheroottothenode.◆结点的祖先是从根到该结点所经分支上的所有结点树的一