《树与二叉树整》ppt课件

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

1、第6章树与二叉树树(tree)结构是一种多分支多层次的数据结构，由一组结点组成。由于它呈现与自然界树类似的结构形式，所以称之为树。在许多算法中，常用树型结构描述问题的求解过程或表示求解的对策等。树的逻辑结构6.1树2树的存储结构树是由n(n≥0)个结点组成的有限集。在任意一棵非空树T中：①有且仅有一个特定的称为根(root)结点；②当n>1时，其余结点分成m(m>0)个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又都是一棵树，并且称为根的子树。36.1.1树的逻辑结构1.树的定义42.树的基本操作InitTree(tree);操作结果：构造空树Tree。

2、InsertChild(Tree,p,child);初始条件：树Tree存在，p指向Tree中某个结点，1≤i≤p所指结点的度+1，非空树child与Tree不相交。操作结果：插入child为T中p所指结点的子树。树结构中经常会用到一些基本术语。例如：结点结点的度叶结点分支结点树的度双亲及孩子兄弟堂兄弟祖先子孙层次树的深度有序树无序树森林53.树的基本概念66.1.2树的存储结构假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在连续空间中的位置。typedefstruct{//双亲表示结构定义TNodetree[MAX];//结点数组in

3、tnodenum;//结点数}ParentTree;//双亲表示结构类型名#defineMax100typedefstructTNode{//结点结构定义DataTypedata;//数据域intparent;//双亲位置域}TNode;1.双亲表示法7RABCDEFGHK树R-1A0B0C0D1E1F3G6H6K6数组下标0123456789双亲存储结构树的双亲表示存储结构利用了每个结点（根结点除外）只有惟一双亲的性质。在树的双亲存储结构中，求双亲Parent(T,x)操作非常方便。求树根结点Root(x)操作也很简单：反复调用Parent操作，直到遇见无双亲的结点

4、时，即T.parent=-1时，便找到了惟一的无双亲的根结点。在树的双亲存储结构中，求某结点的孩子结点时需遍历整个结构。例如求树中结点F的孩子，就需要在整个结构中从头到尾扫描一遍T.parent域，T.parent=6的结点G、H、K就是结点F的孩子。由于树中每个结点可能有多棵子树，则可以用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时，链表中的结点可以有如下3种结构格式：8同构结点格式不同构结点格式单链表存储结构2.孩子表示法(1)同构结点格式。即多重链表中的结点是同构的。datachild1child2……childd其中d为树的度。由于

5、树中很多结点的度都小于d，所以链表中有很多空链域，空间比较浪费。9设树的度为k，结点数为n。若采用同构结点格式，每个结点具有k个固定链域，那么共有nk个链域。由于n个结点要有(n-1)个枝相连，而每枝需要1个链域。因此，这棵树的空链域的个树为：n(k–1)+1。由此可知，树的度越大，空链域越多。如果采用同构结点格式将造成空间的极大浪费。(2)不同构结点格式。即多重链表中的结点是不同构的。degreechild1child2……childddata其中种存储结构避免了孩子表示法存储结构中出现的空链域，节约存储空间。但是由于每个结点的孩子链域数不同，所以在这种结构上进行的

6、各种操作不易实现。为结点的度，degree域的值和d相同。这10d(3)单链表存储结构。即把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表（叶子结点的孩子链表为空表）。而n个头指针又组成一个线性表，为了便于查找，可以采用顺序存储结构。11RABCDEFGHk树ABCDREFGHK35∧6∧012∧789∧0123456789根位置∧∧∧∧∧∧12与树的双亲表示法相反，树的孩子单链表表示法便于查找树中任一结点的孩子：由链表中某结点的指针域next即可以得到该结点的孩子结点。在树的孩子单链表结构中，查找某结点的双亲需要按照该

7、结点在头结点顺序表中的位置序号在每个孩子链表中扫描，当在孩子域child中找到相同的序号时，则单链表表头的结点就是要找的双亲。例如，要寻找树中G结点的双亲结点。G结点在头结点顺序表中的位置序号为7，则在孩子链表中查询child=7的孩子结点，当找到的时候，该单链表的表头结点F就是G的双亲结点。树的孩子兄弟表示法又称二叉树表示法，或二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点的结构相同，都有3个域：数据域data存放树中结点的信息；孩子域firstchild存放该结点的第一个孩子结点（从左算起）的地址；兄弟域nextsibling存放该