第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 ）。在层次结构中下一层的每一个模块分别代表一个函数。字体模块处理与字体有关的所有功能。这些功能包括改变字体、大小、颜等。若把具有这些功能的模块在图中画出的话，那么它们一定出现在字体模块之下。导入模块用于处理图形、表格以及其他格式的文本文件。光标模块处理屏幕上光标的移动。在接口完全设计好后，程序员可以以相对独立的方式分析、设计和开发每个模块。
当一个软件系统以模块化方式划分好之后，可以很自然地以模块为单位来开发该系统。在最终完成的软件系统中，所含有的模块数与模块层次结构中节点数一样多。模块化可以促进对
联邦政府
教育部国防部陆军海军空军海军陆战队
税务部
文字处理器
字体文件导入光标
欲解决问题的智能化管理。通过把一个大问题系统地分解成小而相对独立的小问题，可以使大问题的解决更省力。可以将独立的问题分配给不同的人同时解决。而在一个单一模块上进行分工是非常困难的。开发模块化软件的另一好处是，分开测试一些小而独立的模块比测试一个大的模块要容易得多。层次结构清晰地给出了模块间的关系。
定义[树] 树（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. 给出本书中主要元素的树形表示(整本书、章、节、小节)。
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的左子树和右子树。
二叉树和树的根本区别是：
• 二叉树可以为空，但树不能为空。
• 二叉树中每个元素都恰好有两棵子树（其中一个或两个可能为空）。而树中每个元素可有若干子树。
• 在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。而树的子树间是无序的。
像树一样，二叉树也是根节点在顶部。二叉树左(右)子树中的元素画在根的左(右)下方。在每个元素和其子节点间有一条边。
a)
b)
二叉树公式c)
图8-5  数学表达式树

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。