您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 数据结构A第5章(南邮)
第5章树引言树形结构是元素之间具有分层关系的结构,它类似于自然界中的树,应用广泛,是一类很重要的非线性数据结构。在计算机应用中,常出现嵌套的数据,树结构提供了对该类数据的自然表示;利用树结构,可以有效地解决一些算法问题。由于结构特征,树形结构常采用递归方式定义。被称为递归数据结构。有关树的许多算法是递归的。内容提要1、树的基本概念;给出树的定义,关于树中的一些术语;2、二叉树的定义、性质及其规范;3、二叉树的遍历等算法的实现;4、树和森林的表示、存储和遍历;5、二叉树的应用实例——哈夫曼树和哈夫曼编码。•层次结构的数据在现实自然界中大量存在。–国家、省、市、县和区。–书的章节、回目。–上级和下级。–整体和部分。–祖先和后裔。5.1树的基本概念5.1.1树的定义课堂提要第5章树5.1树的基本概念5.2二叉树5.3二叉树的遍历5.5树和森林5.7哈夫曼树和哈夫曼编码图5-1西欧语言谱系图原始印欧语古意大利语日耳曼语西日耳曼语拉丁语西班牙语法语意大利语希腊语北日耳曼语冰岛语瑞典语挪威语英语荷兰语德语古希腊语树形结构操作系统的目录结构1.树的定义定义5.1有根数或树的定义树是包括n(n1)个元素的有限非空集合D,R是D中元素的序偶的集合,R满足以下特性:(1)有且仅有一个结点r∈D,不存在任何结点v∈D,v≠r,使得v,r∈R,称r为树的根。(2)除根r以外的所有结点u∈D,都有且仅有一个结点v∈D,v≠u,使得v,u∈R。这样定义的树也称有根树,简称树。树不为空集合,树中至少有一个根结点,根结点没有前驱,其余结点都有唯一的前驱结点。因此树形成层次结构。2.树的递归定义•定义5.2树是包括n个结点的有限非空集合T,其中一个特定的结点r称为根,其余结点(T-{r})划分成m(m≥0)个互不相交的子集T1,T2,...Tm,其中,每个子集都是树,被称为树根r的子树。•定义5.2是递归的,用子树来定义树,也就是说,在树的定义中引用了树概念本身,所以,树被称为递归数据结构。EAFGBCDLJMN结点(node):树中的元素。E、A、F、B、G、C、D、L、J、M、N均为结点。5.1.2基本术语EAFGBCDLJMN路径(path):从某个结点沿树中的边可到达另一个结点,则称这两个结点之间存在一条路径。E和N之间存在一条路径。根结点和它的子树根(如果存在)之间形成一条边。路径(path):从某个结点沿树中的边可到达另一个结点,则称这两个结点之间存在一条路径。E和N之间存在一条路径。EAFGBCDLJMN路径(path):从某个结点沿树中的边可到达另一个结点,则称这两个结点之间存在一条路径。E和N之间存在一条路径。双亲(parent):若一个结点有子树,那么该结点称为子树根的双亲。A、F、B的双亲是E。C、D的双亲是F。孩子(child):某结点子树的根是该结点的孩子。E有三个孩子:A、F、B。D有一个孩子:J。兄弟(sibling):有相同双亲的结点互为兄弟。A、F、B互为兄弟,C和D互为兄弟。结点G和C互为兄弟否?EAFGBCDLJMN后裔(decendent):一个结点的所有子树上的任何结点都是该结点的后裔。结点C的后裔为:L、M、N。EAFGBCDLJMN祖先(ancestor):从根结点到某个结点的路径上的所有结点都是该结点的祖先。结点L的祖先为:E、F、C。结点的度(degree):结点拥有的子树数。结点E的度为3,结点F的度为2,结点A的度为1,结点G的度为0。叶子(leaf):度为零的结点。B、G、J、M、N均为叶子结点。EAFGBCDLJMN分支结点(branch):度不为零的结点。E、A、F、C等为分支结点。树的度:树中结点的最大的度。该树的度为3。结点的层次:根结点的层次为1,其余结点的层次等于其双亲结点的层次加1。结点E的层次为1。结点M的层次为5。树的高度:树中结点的最大层次。∵树中结点的最大层次为5。∴树的高度为5。12345EAFGBCDLJMNAG无序树:如果树中结点的各子树之间的次序是不重要的,可以交换位置。下列是同一棵无序树:将左边树中所有结点的子树互换次序就是右边的树。EAFGBCDLJMNEFBCDLJNM有序树:如果树中结点的各棵子树看成是从左到右有次序的,则称该树为有序树。有序树的各子树从左到右为第一棵子树、第二棵,…如果下列是有序树,则二者是二棵不同的树AGEAFGBCDLJMNEFBCDLJNM森林:是树的集合。0个或多个不相交的树组成森林。果园或有序森林:有序树的有序集合。森林与树只有很小的差别,若将树中的根去掉,则得到根的子树组成的森林。BEAGFCDLJMNE若增加一个结点,将森林中各树的根作为新增结点的孩子,则森林即成为树。递归1.递归的定义函数直接(间接)调用自已,称为函数的递归调用。2.简单实例以下是一个最简单的递归函数。voidfunc(){func();}修改为:voidfunc(intn){if(n=0)return;func(n--);}3.递推关系可以把要解决的问题转化为一个新问题,而这个新的问题的解决方法仍与原来的解决方法相同,只是所处理对象的规模有规律地递增或递减,即要找到对象之间的递推关系。方法相同,规模变化4.递归的结束条件要有一个明确的结束递归的条件,一定要能够在适当的地方结束递归调用,不然可能导致系统崩溃intfunc(intn){if(n==1)return1;returnfunc(n-1)*n;}例如:采用递归计算N!正整数N!=N*(N-1)*(N-2)*…*2*1,阶乘序列可转换为N!=N*(N-1)!,而(N-1)!以可转换为(N-1)!=(N-1)*(N-2)!(N-2)!=(N-2)*(N-3)!,……2!=2*1!1!=1递推关系:N!=N*(N-1)!结束条件:N等于1intfunc(intn){if(n==1)return1;returnfunc(n-1)*n;}n=3{if(n==1)…….func(n-1)*n}n=2{if(n==1)…….func(n-1)*n}n=1{if(n==1)return1}1func(n-1)func(n-1)n=2n=12执行过程:设计递归算法,求有n个元素的整数数组A中的最大值。a0a1…ai…an-2an-101…i…n-2n-1a(n-1)Max(n)Max(n-1)a0a1…ai…an-3an-2an-101…i…n-2n-1a(n-2)Max(n-1)Max(n-2)设计递归算法,求整数数组A[n]中的最大值。a0a1…ai…an-3an-2an-101…i…n-2n-1a(1)Max(2)Max(1)递推关系:max(n)等于max(n-1)与a[n-1]之间的大者结束条件:n等于1时,Max(1)的值即为a0,所以不再向下递推intMax(inta[],intn){inttemp;if(n==1)returna[0];else{temp=Max(a,n-1);if(tempa[n-1])returna[n-1];elsereturntemp;}}递推关系:max(n)等于max(n-1)与a[n-1]之间的大者结束条件:n等于1时,Max(1)的值即为a0,所以不再向下递推intMax(inta[],intn){inttemp;if(n==1)returna[0];else{temp=Max(a,n-1);if(tempa[n-1])returna[n-1];elsereturntemp;}}8910012n=3{if(n==1)…….Max(a,2)a[2]}n=2{if(n==1)…….Max(a,1)a[1]}n=1{if(n==1)returna[0]}89•二叉树是非常重要的树形数据结构。•很多从实际问题中抽象出来的数据是二叉树形的;以后我们将看到任意树或森林可方便地转换成二叉树,从而为一般树和森林的存储和处理提供了有效方法。5.2二叉树课堂提要第5章树5.1树的基本概念5.2二叉树5.3二叉树的遍历5.5树和森林5.7哈夫曼树和哈夫曼编码方法二:改进结构,组织成树形结构。比较次数不会超过树高,提高了效率。先看一个二叉树应用例子。设有序表为(21,25,28,33,36,45),现在要在表中查找元素33。282136253345方法一:顺序搜索。效率低,平均比较一半的元素。(21,25,28,33,36,45)比较了4次!比较了3次!3333定义5.3二叉树(binarytree)是结点的有限集合,该集合或者为空集,或者是由一个根和两个互不相交的、称为该根的左子树和右子树的二叉树组成。上述定义表明二叉树可以为空集,因此,二叉树有5种基本形态。5.2.1二叉树的定义(a)(b)(c)(d)(e)图5-4二叉树的五种基本形态树与二叉树的区别:⑴树不能是空树,即至少有一个根结点。而二叉树可以是空树。⑵一般树的子树之间是无序的。而二叉树中结点的子树要区分左、右子树,即使只有一棵子树。⑶树中每个节点可有0棵或若干子树。而二叉树的每个节点最多只能有2棵子树。EFEF性质5.1二叉树的第i(i1)层上至多有2i-1个结点。可用归纳法证明之。当i=1时,二叉树至多只有一个结点,结论成立。设当i=k时结论成立,即二叉树上至多有2k-1个结点,当i=k+1时,∵每个结点最多只有两个孩子,∴第k+1层上至多有2*2k–1=2k个结点,性质成立。5.2.2二叉树的性质性质1、2的图形解释性质5.1二叉树的第i(i1)层上至多有2i-1个结点。性质5.2高度为h的二叉树上至多有2h–1个结点。当h=0时,二叉树为空二叉树。当h0时,利用性质1,高度为h的二叉树中结点的总数最多为:1012112(222...2)21hihhi12311...1nnaaaaaa补充:等比数列的求和公式是1(1)21iii性质二叉树的第层上至多有个结点。性质1、2的图形解释性质5.3包含n个元素的二叉树的高度至少为log2(n+1)根据性质2,高度为h的二叉树最多有2h–1个结点(性质2),因而n2h–1,则有hlog2(n+1)。由于h是整数,所以hlog2(n+1)。性质5.4任意一棵二叉树中,若叶结点的个数为n0,度为2的结点的个数为n2,则必有n0=n2+1。设二叉树的度为1的结点数为n1,树中结点总数为n,则n=n0+n1+n2……①(∵二叉树中只有度为0、1、2三种类型的结点)设分支数为B,n个结点的二叉树,除了根结点外,每个结点都有一个分支进入,则B=n-1;分支是由度为1或者度为2的射出的,又有B=2n2+n1;则有:n-1=2n2+n1n=2n2+n1+1……②由①②可得到:n0+n1+n2=2n2+n1+1n0+n2=2n2+1即n2=n0-1。定义5.4高度为h的二叉树恰好有2h–1个结点时称为满二叉树。01234567891011121314(a)满二叉树图5.6几种特殊的二叉树性质5.2高度为h的二叉树上至多有2h–1个结点。0123456789(b)完全二叉树图5.6几种特殊的二叉树9定义5.5一棵二叉树中,只有最下面两层结点的度可以小于2,并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。定义5.6扩充二叉树也称2-树,其中除叶子结点外,其余结点都必须有两个孩子。532330111213173589完全二叉树的性质性质5.5具有n个结点的完全二叉树的高度为log2(n+1)。证明:根据性质2高度为h-1的完全二叉树结点个数最多为2h-1-1高度为h的完全二叉树结点个数最多为2h-1高度为h的完全二叉树结点个数取值范围[2h-1,2h)2h-1-1<n≤2h–1log2(n+1)≤h<log2(n+1)+1h=log2(n+1)结论:⑴n个结点的二叉树中完全二叉树最矮,高度为log2(n+1)。⑵n个结点的完全二叉树和二叉判定树的高度是一样的2log1n2h
本文标题:数据结构A第5章(南邮)
链接地址:https://www.777doc.com/doc-3171969 .html