数据结构第章树与二叉树ppt课件.ppt

数据结构第章树与二叉树ppt课件.ppt

ID:58915122

大小:1.61 MB

页数:66页

时间:2020-09-29

数据结构第章树与二叉树ppt课件.ppt_第1页
数据结构第章树与二叉树ppt课件.ppt_第2页
数据结构第章树与二叉树ppt课件.ppt_第3页
数据结构第章树与二叉树ppt课件.ppt_第4页
数据结构第章树与二叉树ppt课件.ppt_第5页
资源描述:

《数据结构第章树与二叉树ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第5章树和二叉树(Tree&BinaryTree)特点:非线性结构,一个直接前驱,但可能有多个直接后继。(一对多或1:n)5.1树的概述5.2二叉树定义和性质5.3遍历二叉树5.4线索二叉树5.5树和森林5.6哈夫曼及其应用15.1树的基本概念1.树的定义2.若干术语3.逻辑结构4.存储结构5.树的运算21.树的定义注1:树的定义具有递归性,即“树中还有树”。由一个或多个(n≥0)结点组成的有限集合T,有且仅有一个结点称为根(root),当n>1时,其余的结点分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是棵树,被称作这个根的子树。3树的

2、表示法主要有5种:图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子-右兄弟表示法4图形表示法:教师学生其他人员2002级2003级2004级2005级……华科大武昌分校电信系计算机系自控系……叶子根子树5嵌套集合表示法6广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J))根作为由子树森林组成的表的名字写在表的左边datalink1link2...linkn麻烦问题:应当开设多少个链域?7凹入表示法(又称目录表示法)8左孩子-右兄弟表示法ABCDEFGHIJKLM数据左孩子右兄弟92.若干术语——即树的数据元素——结点挂接的子树数结点结点

3、的度结点的层次终端结点分支结点树的度树的深度(或高度)——从根到该结点的层数(根结点算第一层)——即度为0的结点,即叶子——即度不为0的结点(也称为非终端结点)——所有结点度中的最大值(Max{各结点的度})——指所有结点中最大的层数(Max{各结点的层次})问:右上图中的结点数=;树的度=;树的深度=1334(有几个直接后继就是几度,亦称“次数”)ABCGEIDHFJFLK103.树的逻辑结构一对多(1:n),有多个直接后继(如家谱树、目录树等等),但只有一个根结点,且子树之间互不相交。4.树的存储结构讨论1:树是非线性结构,该怎样存储?特点:——仍然有顺序存储

4、、链式存储等方式。115.2二叉树为何要重点研究每结点最多只有两个“叉”的树?二叉树的结构最简单,规律性最强;可以证明,所有树都能转为唯一对应的二叉树,不失一般性。1.二叉树的定义2.二叉树的性质3.二叉树的存储结构(二叉树的运算见5.3节)121.二叉树的定义定义:是n(n≥0)个结点的有限集合,由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构:一对二(1:2)基本特征:①每个结点最多只有两棵子树(不存在度大于2的结点);②左子树和右子树次序不能颠倒。问:具有3个结点的二叉树可能有几种不同形态?有5种基本形态:一般的树有几种?132.

5、二叉树的性质(3+2)讨论1:第i层的结点数最多是多少?(利用二进制性质可轻松求出)性质1:在二叉树的第i层上至多有2i-1个结点(i>0)。性质2:深度为k的二叉树至多有2k-1个结点(k>0)。再提问:第i层上至少有个结点?1讨论2:深度为k的二叉树,最多有多少个结点?(利用二进制性质可轻松求出)2i-1个2k-1个14讨论3:二叉树的叶子数和度为2的结点数之间有关系吗?性质3:对于任何一棵二叉树,若2度的结点数有n2个,则叶子数(n0)必定为n2+1(即n0=n2+1)证明:∵二叉树中全部结点数n=n0+n1+n2(叶子数+1度结点数+2度结点数)又∵二叉树

6、中全部结点数n=B+1(总分支数+根结点)(除根结点外,每个结点必有一个直接前趋,即一个分支)而总分支数B=n1+2n2(1度结点必有1个直接后继,2度结点必有2个)三式联立可得:n0+n1+n2=n1+2n2+1,即n0=n2+1物理意义:叶子数=2度结点数+1152.深度为K的二叉树的结点总数,最多为个。A)2k-1B)log2kC)2k-1D)2k1.树T中各结点的度的最大值称为树T的。A)高度B)层次C)深度D)度DCC3.深度为9的二叉树中至少有个结点。A)29B)28C)9D)29-1课堂练习:16满二叉树:一棵深度为k且有2k-1个结点的二叉树。(特

7、点:每层都“充满”了结点)完全二叉树:深度为k的、有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。AOBCGEKDJFIHNML深度为4的满二叉树完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式?完全二叉树的特点是只有最后一层叶子不满,且全部集中在左边。但这其实是顺序二叉树的含义。而图论中的“完全二叉树”是指n1=0的情况。因为它们在顺序存储方式下可以复原!17对于两种特殊形式的二叉树(满二叉树和完全二叉树),还特别具备以下2个性质:性质4:具有n个结点的完全二叉树的深度必为log2n+1性质5:对完全二叉树,

8、若从上至下

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。