自考数据结构导论 02142 第4章课件.ppt

自考数据结构导论 02142 第4章课件.ppt

ID:57174982

大小:918.50 KB

页数:68页

时间:2020-08-02

自考数据结构导论  02142 第4章课件.ppt_第1页
自考数据结构导论  02142 第4章课件.ppt_第2页
自考数据结构导论  02142 第4章课件.ppt_第3页
自考数据结构导论  02142 第4章课件.ppt_第4页
自考数据结构导论  02142 第4章课件.ppt_第5页
资源描述:

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

1、第44.1树的基本概念4.2二叉树4.3二叉树的存储结构4.4二叉树的遍历4.5树和森林4.6哈夫曼树1树型结构是一类重要的非线性结构。树型结构是结点之间有分支,并且具有层次关系的结构,它非常类似于自然界中的树。树结构在客观世界中是大量存在的,例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程等等。4.1树的定义和基本术语树——是n(n>=0)个结点的有限集T,满足:(1)有且仅有一个特定的称为根的结点;(2)

2、其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm,其中每个子集Ti又是一棵树,并称其为子树。一、树的定义递归是树的固有特性2二、树的逻辑表示▲一般表示法(直观表示法):FCEGBDAb、嵌套括号法:(根(子树,子树…子树))(A(B(E,F),C,D(G))根ABFCDGEc、凹入法表示:▲另三种表示法a、文氏图法:BACDEFG——第一层第二层第三层3三、树的基本术语●度——结点的度:该结点的子树数(即分支数)。树的度:树中结点的度最大值。●结点—由一个数据元素及若干指向其它结点的分支所组成。●叶子(终端结点)——度为零的结点。●孩子

3、(子结点)——结点的子树的根称为该结点的孩子。●双亲(父结点)——一个结点称为该结点所有子树根的双亲。●非终端结点——度不为零的结点。●祖先——结点祖先指根到此结点的一条路径上的所有结点。●子孙——从某结点到叶结点的分支上的所有结点称为该结点的子孙。●兄弟——同一双亲的孩子之间互称兄弟。4●结点的层次——从根算起,根为第一层,其孩子在第二层,….,L层上任何结点的孩子都在L+1层上。●堂兄弟——其双亲在同一层的结点。●树的深度——树中结点的最大层次。●森林——是m(≥0)棵树的集合。●有序树——若树中各结点的子树从左到右是有次序的,不能互换,称为有序树。●

4、无序树——若树中各结点的子树是无次序的,可以互换,则成为无序树。5求根Root(T):求树T的根结点;求双亲Parent(T,X):求结点X在树T上的双亲;若X是树T的根或X不在T上,则结果为一特殊标志;求孩子Child(T,X,i):求树T上结点X的第i个孩子结点;若X不在T上或X没有第i个孩子,则结果为一特殊标志;建树Create(X,T1,…,Tk),k>1:建立一棵以X为根,以T1,…,Tk为第1,…,k棵子树的树;剪枝Delete(T,X,i):删除树T上结点X的第i棵子树;若T无第i棵子树,则为空操作;遍历TraverseTree(T):遍历树

5、,即访问树中每个结点,且每个结点仅被访问一次。四、树的基本操作6二叉树在树结构的应用中起着非常重要的作用,因为二叉树有许多良好的性质和简单的物理表示,而任何树都可以与二叉树相互转换,这样就解决了树的存储结构及其运算中存在的复杂性。4.2二叉树1、定义:二叉树是n(n>=0)个结点的有限集合,它或为空(n=0),或是由一个根结点及两棵互不相交的左、右子树组成,且每棵子树都是二叉树。4.2.1二叉树的基本概念这是一个递归定义。二叉树可以是空集合,根可以有空的左子树或空的右子树。ABDCFGHE72、特点:①二叉树可以是空的,称空二叉树;②每个结点最多只能有两个

6、孩子;③子树有左、右之分且次序不能颠倒。3、二叉树与树的比较:结点子树结点顺序树n≥0不定(有限)无二叉树n≥0≤2有(左、右)8二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也要进行区分,说明它是左子树,还是右子树。这是二叉树与树的最主要的差别。下图列出二叉树的5种基本形态,图(C)和(d)是不同的两棵二叉树。(a)空二叉树A(b)根和空的左右子树A(c)根和左子树A(d)根和右子树A(e)根和左右子树二叉树的5种形式4.2.1二叉树的定义9初始化Initiate(BT):建立一棵空二叉树,BT=∅。求双亲Parent(BT,X):求出二叉树BT

7、上结点X的双亲结点,若X是BT的根或X根本不是BT上的结点,运算结果为NULL。求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X):分别求出二叉树BT上结点X的左、右孩子;若X为BT的叶子或X补在BT上,运算结果为NULL。建二叉树Create(BT):建立一棵二叉树BT。先序遍历PreOrder(BT):按先序对二叉树BT进行遍历,每个结点被访问一次且仅被访问一次,若BT为空,则运算为空操作。4、二叉树的基本操作(见P77)10中序遍历InOrder(BT):按中序对二叉树BT进行遍历,每个结点被访问一次且仅被访问一次,若BT为空,则运算

8、为空操作。后序遍历PreOrder(BT):按后序对二叉树BT进行

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

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

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