内蒙古大学《算法与数据结构》讲义08二叉树和其他树

下载第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 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 软件工程 考察另一种层次数据软件工程中的模块化技术。通过模块化，可以把大的复杂的任务分成一组小的不太复杂的任务。模块化的目标是把软件系统分成许多功能不相关的部分或模块以便于进行相对独立的开发。由于解决几个小问题比解决大问题更容易一些，因此模块化方法可以缩短整个软件的开发时间。另外，不同的程序员可以同时开发不同的模块。如果有必要，每个模块可以再细分，从而得到如图 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） 。在层次结构中下一层的每一个模块分别代表一个函数。字体模块处理与字体有关的所有功能。这些功能包括改变字体、大小、颜色等。若把具有这些功能的模块在图中画出的话，那么它们一定出现在字体模块之下。导入模块用于处理图形、表格以及其他格式的文本文件。光标模块处理屏幕上光标的移动。在接口完全设计好后，程序员可以以相对独立的方式分析、设计和开发每个模块。当一个软件系统以模块化方式划分好之后，可以很自然地以模块为单位来开发该系统。在最终完成的软件系统中，所含有的模块数与模块层次结构中节点数一样多。模块化可以促进对第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 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 n n，M a r y，J o h n在图8 - 1的树中为兄弟，而M a r k和C h r i s则不是。此外还有其他术语：孙子（ g r a n d c h i l d） ，祖父（g r a n d p a r e n t） ，祖先（a n c e s t o r） ，后代（d e s c e n d e n t）等。树中没有孩子的元素称为叶子（l e a f） 。因此在图8 - 1中，A n n，M a r k，Sue 和Chris 是树的叶子。树根是树中唯一一个没有父节点的元素。例8-6 在合作机构的例子中（例8 - 2） ，公司雇员是树中的元素。总裁是树的根，余下的分成不相交的集合，代表公司的不同分支，每个分支有一个副总裁，为该分支子树的根。分支中余下的元素分成不相交的集合，代表不同的部。部长是子树的根。余下元素同样可分成不同的科等。副总裁是总裁的子节点，部长是副总裁的子节点。总裁是副总裁的父节点，每个副总裁是其分支中元素的父节点。在图8 - 3中，根为联邦政府。其子树的根为国防部，教育部，税务部等。联邦政府是其子节点的父节点。国防部的子节点为陆军、海军、空军、海军陆战队。国防部的子节点之间为兄弟关系，同时它们也是叶节点。树的另一常用术语为级（ l e v e l） 。指定树根的级为1，其孩子（如果有）的级为 2，孩子的孩子为3，等等。在图8 - 3中，联邦政府在第1级，国防部、教育部、税务部在第2级，陆军、海军、空军和海军陆战队在第3级。元素的度（degree of an element）是指其孩子的个数。叶节点的度为 0，在图8 - 4中文件模块的度为5。树的度（degree of a tree）是其元素度的最大值。练习1. 给出本书中主要元素的树形表示(整本书、章、节、小节)。2 5 0第二部分数 据 结 构下载1) 树中共有多少个元素?2) 标出叶节点。3) 标出第3级元素。4) 给出每个元素的度。2. 访问h t t p : / / w w w. c i s e . u f l . e d u，即佛罗里达大学计算机、信息科学和工程系主页。通过连接到更下一级的网页，绘出网页间的层次结构。用节点表示网页，用线连接网页。1) 此结构一定是一棵树吗? 为什么？2) 若此结构是一棵树，指出其根和叶子。8.2 二叉树定义二叉树 二叉树（binary tree）t 是有限个元素的集合（可以为空） 。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成 2个二叉树，分别称为t的左子树和右子树。二叉树和树的根本区别是： 二叉树可以为空，但树不能为空。 二叉树中每个元素都恰好有两棵子树（其中一个或两个可能为空） 。而树中每个元素可有若干子树。 在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。而树的子树间是无序的。像树一样，二叉树也是根节点在顶部。二叉树左 (右)子树中的元素画在根的左 (右)下方。在每个元素和其子节点间有一条边。图8-5 数学表达式树第8章二叉树和其他树2 5 1下载a)b)c)图8 - 5给出了表示数学表达式的二叉树。每个操作符（十，一， *，/）可以有一个或两个操作数。左操作数是操作符的左子树，右操作数是操作符的右子树。树中的叶节点为常量或变量。注意在数学表达式树中没有括号。数学表达式二叉树的一个应用是产生一个表达式的优化代码。我们并不研究怎样从数学表达式树中产生最优代码的算法，只是用它来说明许多操作可以用二叉树来解决。练习3. 1) 标出图8 - 5中二叉树的叶子。2) 标出图8-5b 中第3级的所有节点。3) 在图8-5c 中第4级有多少个节点?4. 给出如下各表达式的二叉树：1) ( a + b)/ (c - d * e ) + e + g * h /a。2) -x-y * z + ( a + b + c / d * e)。3) ( a + b) ( c-e ) ) | | a f & (x z)。8.3 二叉树的特性特性1 包含n (n 0 )个元素的二叉树边数为n-1。证明二叉树中每个元素 (除了根节点) 有且只有一个父节点。在子节点与父节点间有且只有一条边，因此边数为n-1。二叉树的高度（h e i g h t）或深度（d e p t h）是指该二叉树的层数。图8-5a 中二叉树的高度为3，而图8-5b 和c 的高度为4。特性2 若二叉树的高度为h，h0，则该二叉树最少有h个元素，最多有2h- 1个元素。证明因为每一层最少要有1个元素，因此元素数最少为h。每元素最多有2个子节点，则第i 层节点元素最多为2i - 1个，i 0。h= 0时，元素的总数为0，也就是20 - 1。当h 0时，元素的总数不会超过hi=12i- 1= 2h -1。特性3 包含n 个元素的二叉树的高度最大为n，最小为l o g2(n+ 1 )。证明因为每层至少有一个元素，因此高度不会超过n。由特性2，可以得知高度为h 的二叉树最多有2h-1个元素。因为n2h -1，因此hl o g2(n+ 1 )。由于h 是整数，所以hl o g2(n+ 1 )。图8-6 高度为4的满二叉树2 5 2第二部分数 据 结 构下载当高度为h 的二叉树恰好有2h- 1个元素时，称其为满二叉树（full binary tree） 。图8-5a 是一个高度为3的满二叉树。图8-5b 和c 的二叉树不是满二叉树。图8 - 6给出高度为4的满二叉树。假设对高度为h 的满二叉树中的元素按从第上到下，从左到右的顺序从 1到2h- 1进行编号（如图8 - 6所示） 。假设从满二叉树中删除k个元素，其编号为2h-i, 1ik，所得到的二叉树被称为完全二叉树（complete binary tree） 。图8 - 7给出三棵完全二叉树。注意满二叉树是完全二叉树的一个特例，并且，注意有n个元素的完全二叉树的深度为l o g2(n+ 1 )。图8-7 完全二叉树在完全二叉树中，一个元素与其孩子的编号有非常