内蒙古大学《算法与数据结构》讲义08二叉树和其他树
28页1、下载第8章二叉树和其他树在一片丛林中有各种各样的树、植物和动物。在数据结构的世界中也有许多“树” ,不过本书不可能全部介绍。在本章中将学习两种基本的树:一般树 (简单树)和二叉树。第9、1 0和11章中对其他树有更详细的介绍。在本章的应用部分给出了树的两个应用。第一个应用是关于在一个树形分布的网络中设置信号调节器。第二个应用是3 . 8 . 3节中所介绍的在线等价类问题。在线等价类问题在本章中又被称为合并/搜索问题。利用树来解决等价类问题要比3 . 8 . 3节中的链表解决方案高效得多。另外,本章中还覆盖了以下内容: 树和二叉树的术语,如高度、深度、层、根、叶子、子节点、父节点和兄弟节点。 二叉树的公式化描述和链表描述。 4种常用的二叉树遍历方法:前序遍历,中序遍历,后序遍历和按层遍历。8.1 树到目前为止,我们已经介绍了线性数据结构和表数据结构。这些数据结构一般不适合于描述具有层次结构的数据。在层次化的数据之间可能有祖先 -后代、上级-下属、整体-部分以及其他类似的关系。例8-1 Joe的后代 图8 - 1给出了J o e的后代,并按层次方式组织,其中 J o e在最顶层。 J o
2、e的孩子( A n n,M a r y和J o h n)列在下一层,在父母和孩子间有一条边。在层次表示中,非常容易地找到A n n的兄弟姐妹, J o e的后代,C h r i s的祖先等。例8-2 合作机构 作为层次数据的一个例子,考虑图8 - 2的合作管理机构。在层次中地位最高的人(此处为总裁)在图中位置最高。在层次中地位次之的(即副总裁)在图中位于总裁之下等等。副总裁为总裁的下属,总裁是他们的上级。每个副总裁都有他自己的下属,而其下属又图8-1 Joe的后代图8-2 合作管理结构总裁财务副总裁市场副总裁销售副总裁开发副总裁有他们自己的下属。在图中,在每个人与其直接下属或上级之间都有一条边互连。例8-3 政府机构 图8 - 3是联邦政府各分支机构的层次图。在最顶层是整个联邦政府。层次结构的下一级,是其主要的隶属单位 (例如不同的部)。每个部可进一步细分。这些分支在层次结构的下一级画出。例如,国防部分成陆军、海军、空军和海军陆战队。在每个机构及其分支机构间都有一条边。图8 - 3的数据即为整体-部分关系的例子。图8-3 联邦政府模型例8-4 软件工程 考察另一种层次数据软件工程中的模
3、块化技术。通过模块化,可以把大的复杂的任务分成一组小的不太复杂的任务。模块化的目标是把软件系统分成许多功能不相关的部分或模块以便于进行相对独立的开发。由于解决几个小问题比解决大问题更容易一些,因此模块化方法可以缩短整个软件的开发时间。另外,不同的程序员可以同时开发不同的模块。如果有必要,每个模块可以再细分,从而得到如图 8 - 4所示的用树形表示的模块层次结构。该树给出了某文字处理器的一种可行的模块分解图。图8-4 文字处理器的模块层次结构文字处理器的最顶层模块被划分为下一层的几个模块,在图 8 - 4中只给出4个。文件模块完成与文本文件有关的操作,如打开一个已存在文件( O p e n) ,打开一个新文件(N e w) ,保存文件(S a v e) ,打印文件(P r i n t) ,从文字处理器中退出( Q u i t) 。在层次结构中下一层的每一个模块分别代表一个函数。字体模块处理与字体有关的所有功能。这些功能包括改变字体、大小、颜色等。若把具有这些功能的模块在图中画出的话,那么它们一定出现在字体模块之下。导入模块用于处理图形、表格以及其他格式的文本文件。光标模块处理屏幕上光标的
4、移动。在接口完全设计好后,程序员可以以相对独立的方式分析、设计和开发每个模块。当一个软件系统以模块化方式划分好之后,可以很自然地以模块为单位来开发该系统。在最终完成的软件系统中,所含有的模块数与模块层次结构中节点数一样多。模块化可以促进对第8章二叉树和其他树2 4 9下载联邦政府教育部国防部陆军海军空军海军陆战队税务部文字处理器字体文件导入光标欲解决问题的智能化管理。通过把一个大问题系统地分解成小而相对独立的小问题,可以使大问题的解决更省力。可以将独立的问题分配给不同的人同时解决。而在一个单一模块上进行分工是非常困难的。开发模块化软件的另一好处是,分开测试一些小而独立的模块比测试一个大的模块要容易得多。层次结构清晰地给出了模块间的关系。定义树 树(t r e e)t 是一个非空的有限元素的集合,其中一个元素为根(r o o t) ,余下的元素(如果有的话)组成t 的子树(s u b t r e e) 。现在看一下定义与层次数据例子之间的关系。层次中最高层的元素为根。其下一级的元素是余下元素所构成的子树的根。例8-5 在J o e的后代例子中(例8 - 1 ),数据集合是 J o e,A
5、 n n,M a r y,M a r k,S u e,J o h n,C h r i s ,因此n = 7,树的根为J o e。余下的元素被分成三个不相交的集合 A n n , M a r y,M a r k,S u e 和 John,Chris 。 A n n 是只有一个元素的树,其根为A n n。 Mary,M a r k,Sue 的根为M a r y,而 John,Chris 的根为J o h n。集合 Mary,M a r k,S u e 余下的元素分成不相交的集合 Mark 和 Sue ,二者均为单元素的子树,集合 John,Chris 余下的元素也为单元素子树。在画一棵树时,每个元素都代表一个节点。树根在上面,其子树画在下面。在树根与其子树的根(如果有子树)之间有一条边。同样的,每一棵子树也是根在上,其子树在下。在一棵树中,边连结一个元素及其子节点。在图8 - 1中,A n n,M a r y,J o h n是J o e的孩子(c h i l d r e n) ,J o e是他们的父母(p a r e n t) 。有相同父母的孩子为兄弟( s i b l i n g) 。A
《内蒙古大学《算法与数据结构》讲义08二叉树和其他树》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义08二叉树和其他树》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页