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

《数据结构课件 第六 章树.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第6章树和二叉树本章中主要介绍下列内容：树的逻辑定义和存储结构二叉树的逻辑定义、存储结构二叉树的基本操作算法树和二叉树的转换哈夫曼树及其应用退出5.1树的概念与定义5.2二叉树5.3树与森林5.4哈夫曼树及其应用5.5应用举例5.1树树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来

2、描述其执行过程。为了在实际上是线性的储存载体上(内存、磁盘)储存非线性的树结构….树的应用举例——八枚硬币问题设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，其中有且仅有一枚硬币是假币，并且假币的重量与真币的重量不同，可能轻，也可能重。现要求以天平为工具，用最少的比较次数挑选出假币，并同时确定这枚假币的重量比其它真币是轻还是重。问题的解决是经过一系列的判断，这些判断构成了树结构，可以用判定树来描述这个判定过程。解决这个问题的最自然的想法就是把硬币分成两组，也就是一分为二。但是，如果一分为三的话，会获得更少的比较次数。从八枚硬币中任取六枚a，b，

3、c，d，e，f，在天平两端各放三枚进行比较。假设a，b，c三枚放在天平的一端，d，e，f三枚放在天平的另一端，可能出现三种比较结果：⑴a＋b＋c>d＋e＋f⑵a＋b＋c＝d＋e＋f⑶a＋b＋cd＋e＋f，可以肯定这六枚硬币中必有一枚为假币，同时也说明，g,h为真币。这时可将天平两端各去掉一枚硬币，假设去掉和，同时将天平两端的硬币各换一枚，假设硬币，作了互换，然后进行第二次比较，比较的结果同样可能有三种：①a＋e>d＋b：这种情况表明天平两端去掉硬币c，f且硬币b，e互换后，天平两端的轻重关系保持不变，从而说明了假币必然是a，d

4、中的一个，这时我们只要用一枚真币（例如h）和a进行比较，就能找出假币。若a>h，则a是较重的假币；若a＝h，则d为较轻的假币；不可能出现a②a＋e＝d＋b：此时天平两端由不平衡变为平衡，表明假币一定在去掉的两枚硬币c，f中，同样用一枚真币（例如h）和c进行比较，若c>h，则c是较重的假币；若c＝h，则f为较轻的假币；不可能出现c③a＋e：此时表明由于两枚硬币b，e的对换，引起了两端轻重关系的改变，那么可以肯定b或e中有一枚是假币，同样用一枚真币（例如h）和b进行比较，若b>h，则b是较重的假币；若b＝h，则e为较轻的假币；不可能出现b对于结果⑵和⑶的情

5、况，可按照上述方法作类似的分析。图5-42给出了判定过程，图中大写字母H和L分别表示假币较其它真币重或轻，边线旁边给出的是天平的状态。八枚硬币中，每一枚硬币都可能是或轻或重的假币，因此共有16种结果，反映在树中，则有16个叶子结点，从图中可看出，每种结果都需要经过三次比较才能得到。5.1树5.1.1树的定义和基本运算1.定义树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一

6、棵树。由此可以看出，树的定义是递归。树(Tree)：是包括n(n>=0)个结点的有限集T。当T非空时，满足：（1）有且仅有一个特别标出的称为根的结点；（2）除根结点外，其余结点可分为m（m>=0）个互不相交非空的有限集T1,T2,…,Tm,其中每一个集合本身又是一棵树，称为根的子树(Subtree)。树的递归定义：空树：不包括任何结点的树。树结构的特点：（1）树的根的结点没前驱结点，除了根结点之外的所有结点都有且只有一个前驱结点；（2）树的结点可以有零个或多个后继结点。树结构描述的是层次关系。A只有根结点的树ABCDEFGHIJKLM有子树的树根子树树

7、的表示方法：(c)凹入表（a）树形表示ABCDEFIJGH(A(B(D)(E(I)(J))(F))(C(G)(H)))(d)嵌套括号表示法CDEIJFGHAB(b)文氏图对比树型结构和线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子

8、(leaf)——度为0的结点，又叫终端结点孩子(child)——结点子树的根称为该结点的孩子双