数据结构万扣树.ppt

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

1、数据结构:线性结构(线性表,栈,队列等)非线性结构:至少存在一个数据元素有不止一个直接前驱或后继(树,图等)3.1树的定义一.树的定义树是n个数据元素的有限集(记为T)，对任意一棵树T有：⒈存在唯一一个称为根的数据元素；⒉当n＞1时，其它数据元素可分为m(m＞0)个互不相交的有限集T1,T2,…,Tm，其中每个集合Ti(i=1,2,…,m)本身又是一棵树，并称树Ti是根的子树。3.1树的定义二.树的表示形式⑴倒悬树。是最常用的表示形式，如图6-1(b)。⑵嵌套集合。是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。图6-2(a)是图6-1(b)树的嵌套集合形式。⑶广

2、义表形式。图6-2(b)是树的广义表形式。⑷凹入法表示形式。见P120树的表示方法的多样化说明了树结构的重要性。3.1树的定义ABDCEGFHIMJNKL(a)一般的树(b)嵌套集合形式HIJDFBKLECMNGA(c)广义表形式A(B(E(K,L),F),C(G(M,N)),D(H,I,J)）3.1树的定义三.树的基本术语1.树的结点:包含一个DE和指向其子树的所有分支;2.结点的度:一个结点拥有的子树的个数；度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值Max(D(I))含义:树中最大分支数为树的度4.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则

3、其孩子为k+1层；树中结点的最大层次称为树的深度或高度；5.森林:是m(m>=0)棵互不相的树的集合；森林与树概念相近,相互很容易转换；3.1树的定义1层2层4层3层depth=4DACBIJHGFEMLKheight=43.2二叉树一.二叉树的概念二叉树是结点数为0或每个结点最多只有左右两棵子树的树。二叉树是一种特殊的树结构，它的特点是：⑴每个结点最多只有两棵子树，即不存在结点度大于2的结点；⑵子树有左右之分，不能颠倒。问题：二叉树和度为2的树有何不同？3.2二叉树二.二叉树的性质性质1.在二叉树的第i层上至多有2i-1个结点(i≥1)。证明:用归纳法1.当i=1,即第一层只有一个根结点,

4、显然2i-1=20=1成立2.假设对所有的j上述性质成立,即第j层上至多有2j-1个结点3.要证明i=j+1时,命题也成立。由归纳假设：第j层上至多有2j-1个结点，又由于二叉树每个结点的度最大为2，所以第j+1层上结点总数最多为第j层上最大结点数的2倍。即2*2j-1=2(j+1)-13.2二叉树性质2.深度为k的二叉树至多有2k-1个结点(k≥1)。（深度一定，二叉树的最大结点数也确定）证明：深度为k的二叉树的最大结点数是二叉树中每层上结点的最大数之和。即k∑（第i层上结点的最大数）i=1k=∑2i-1=1+2+22+……+2k-1=2k-1(等比级数求和)i=13.2二叉树性质3.二叉

5、树中,终端结点数n0与度为2的结点数n2有如下关系:n0=n2+1证明:设二叉树中度为i的结点数为ni,则结点总数n=n0+n1+n2除根结点外,每个结点都是另一结点的孩子孩子数=n-1；度为i（i=0，1，2）的结点，有i个孩子。孩子数=2n2+n1n-1=2n2+n1即n0+n1+n2-1=2n2+n1故n0=n2+13.2二叉树满二叉树:深度为k，且有2k-1个结点的二叉树。特点：（1）每一层上结点数都达到最大（2）度为1的结点数n1=0结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。1237654k=3n=23-1=7满二叉树3.2二叉树完全二叉

6、树:深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。452131237654k=3n=23-1=7满二叉树完全二叉树3.2二叉树LH2=0RH2=11324653241LH1=3RH1=1LH1-RH1=2非完全二叉树非完全二叉树LH2-RH2=0-1=-13.2二叉树性质4.结点数为n的完全二叉树，其深度为└log2n┘+1证明：设深度为k，则由性质2和完全二叉树定义有：结点数n满足：2k-1-1＜n≤2k-1或写为2k-1≤n＜2k于是有：k-1≤log2n＜k因为k-1和k均为整数显然有└log2n┘=k-1,故k=

7、└log2n┘+13.2二叉树性质5.在按层序编号的n个结点的完全二叉树中，任意一结点i(1≤i≤n)有：⑴i=1时，结点i是树的根；否则(i>1)，结点i的双亲为结点└i/2┘。⑵2i＞n时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。⑶2i+1＞n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。3.2二叉树三、二叉树的存储结构⒈顺序存储结构用一组地址连续的存储单元，以层序顺序存放二叉