数据结构树和叉树ppt

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

1、树的概念树的遍历及存储二叉树二叉树的遍历线索二叉树哈夫曼树及其应用第七章树和二叉树树的递归定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树。树的概念ACGBDEFKLHMIJ树的逻辑结构•除了根结点外，每个结点有且仅有一个直接前驱。•所有结点可以有多个直接后继。1--多树的表示(1)树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和

2、形象。下图就是采用这种表示法。(2)文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。(3)凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。(4)括号表示法。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。ADTTree{数据对象:D={ai

3、1in,n0,ai属Elemtype类型数据关系:R1={

4、ai,ajD,1in,1jn,每个元素只有一个前驱可以有多个后继}基本运算:InitTree(t);ClearTree(t);Parent(t,e);

5、Sons(t,e);Traver(t);}抽象数据类型数的定义1层2层4层3层height=4树的基本常用术语ACGBDEFKLHMIJ层次根为第1层最大层数为树的深度（高度）双亲(直接前驱）孩子（直接后继）兄弟堂兄弟子孙祖先森林----m(m>=0)棵互不相交的树的集合。d=3d=0度一个结点的子树的个数称为该结点的度。度为零的结点称为叶子结点。度不为零的结点称为分支结点。树中所有结点的度的最大值为树的度。dmax=3d=2KLFGMIJABCDEH树和森林的遍历深度优先遍历先根次序遍历后根次序遍历广度优先遍历按层次序遍历先根次序遍历当树非空*访问根结点*依次先根遍历根的各子

6、树DT1T2T3ABEFCGDHIJ先根次序遍历森林依次先根遍历各子树T1T2T3ABCDEFGHIKJACGBDEFHIJACGBDEFHIJK树和森林的遍历后根次序遍历当树非空*依次后根遍历根的各子树*访问根结点T1T2T3DAEFBGCHIJD后根次序遍历森林依次后根遍历各子树T1T2T3BCEDAGFKIJHACGBDEFHIJACGBDEFHIJK树和森林的遍历按层次序遍历当树非空*自上向下依次遍历每一层*每层从左向右访问结点层次：123ABCDEFGHIJ按层次序遍历森林依次遍历森林中各层结点层次：123AFHBCDGIJEKACGBDEFHIJACGBDEFHIJ

7、Kdataparent0123456双亲表示树的存储结构ABCDEFG-1000113指向其双亲的位置dataparent特点：很快确定双亲结点ACGBDEF孩子表示法每个结点拥有孩子的个数不同，所以采用单链表链接孩子结点。孩子结点结构：childnext孩子结点的序号指向下一个孩子结点树结点结构：dataheadptr指向第一个孩子结点0123456dataheadptrABCDEFG123456typedefstructcnode{intchild;structcnode*next;}link;typedefstruct{datatypedata;link

8、*headptr;}ctree;ctreeT[maxnode];特点：很快确定孩子结点但确定双亲效率低dataparentheadprt-1000113孩子双亲表示法ACGBDEFAdatafirstChildnextSiblingBCDGFE孩子兄弟表示指向第一个孩子结点指向右兄弟结点TACGBDEF定义：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树(BinaryTree)二叉树的五种不同形态LRLR度2有序树？二叉树与度为2的树的区别度2=2序有序无序ABDEFGABC

9、DFE分别有0个1个2个3个4个结点的不同二叉树如下n0=1n1=1n2=2n3=5n4=140个1个2个3个4个性质2深度为k的二叉树至多有2k-1个结点。(k1)二叉树的性质性质1在二叉树的第i层最多有2i-1个结点。(i1)[证]（数学归纳法）i=1,2i-1=20=1。设i=j成立，即第j层至多2j-1个结点。则j+1层，最多有2*2j-1=2(j+1)-1（由于每个最多有两个后继）[证]20+21+…+2k-1=2k-1性质3对任何一棵二叉树,若其叶结点个数为n0,度为2的结点