第5 章 树和二叉树 读史可以明鉴,知古可以鉴今。中国古代大量鸿篇巨制为中华文明和人类文明做出 了重大贡献。坚定文化自信首先要对民族文化有更准确的理解。以二十四史为代表的纪 传体正史与中华民族数千年文明相依相伴,是世界上唯一载录绵延数千年的信史,成为一 代又一代中国人可以源源不断汲取的智慧源泉。 作为二十四史之首的《史记》,是司马迁以“究天人之际,通古今之变,成一家之言”的 史识,专注十四年创作的中国第一部纪传体通史,被鲁迅誉为“史家之绝唱,无韵之离骚”, 对后世具有非常大的影响。《史记》记载了上至皇帝时代,下至武帝太初四年间共3000年 的历史。我们可以通过图5-1来了解这一部亘古通今的千年巨著。 图5-1 《史记》结构图 这种最简单的思维导图把所有的信息都组织在一个树状的结构图上,可以加强对信 息的记忆与理解。树结构不仅可以被用于构建思维导图,还可以用于组织机构管理。 本章将介绍这种树状结构,包括其逻辑结构、存储结构以及基本操作,并将给出实际 175 第 5 章　树和二叉树 应用问题的案例实现。 5.问题的提出 1 问题1:某大学设有若干个职能处室和院系,每个职能处室又根据业务需要设置若干 个科室和研究所,而每个院系按专业和学科方向设置不同的教研室、研究所和实验室。要 求对机构的设置进行动态管理,并提供创建、删除、增加、查询和显示等功能。 这些部门之间的关系如图5-2所示。 图5- 2 某大学机构设置示意图 问题2:在表达式求值中,如何存储表达式才能更便于计算表达式的值? 在第3章介绍了两种表达式求值的方法。无论是原表达式还是后缀表达式都是以字 符串形式存储,这需要事先确定存储空间的大小。如果可以根据算术表达式动态分配存 储空间,并且可方便地进行表达式求值,则可以有效解决一些应用系统中的表达式计算 问题。 图5-3是表达式a+(b*c-d/e)对应的二叉树存储结构,其后序遍历序列“abc*de/ -+”是原表达式的后缀表达式。 问题1中各个部门的名称是数据元素,问 题2中的操作对象和运算符是数据元素,数据 元素之间的关系不再是线性关系,而是层次关 系。相邻两层中,上一层的一个数据元素可以 与下一层的多个数据元素有关系,下一层的一 个数据元素只能与上一层的一个数据元素有 关系。这种关系称为一对多的层次关系,即 图5-3表达式的二叉树存储示意图 176 新编数据结构及算法教程（第 2 版） 1∶n 。我们把具有这种层次关系的结构称为树状结构。 5.树的定义和基本术语 2 5.2.1 树的递归定义 树是由根结点和子树组成,具有以下特征。 (1)有一个特定的称为该树之根的结点,即根结点。 (2)结点数n=0时,表示树是空树。 (3)结点数n>0 时,有m(m≥0)个互不 相交的有限结点集,每个结点集对应一棵 子树。 树的定义说明了树是一种递归的数据结 构,即树中包含树。如图5-4所示的是一棵空 树和一棵一般的树。在图5-4中,A是根结 点,有三棵子树,B是子树的根结点,有两棵子 树。树的结点之间有明确的层次关系。图5- 4 空树和一般的树 通常,企事业单位的行政机构、书的目录 结构、人类的家族血缘关系、操作系统的资源管理器以及结构化程序模块之间的关系等都 是树状结构。 5.2.2 树的基本术语 下面根据树的特征,分类给出树的基本术语描述。 1. 树的结点 包含一个数据元素及若干指向其子树的分支。 2. 树的规模 ( 树的规模包括结点的度、树的度、结点的层次、树的高度(深度)和树的宽度。 1)结点的度:结点拥有的子树数。如图5-4中结点A的度为3,结点B的度为2,结 点C的度为1,结点E的度为0。 (2)树的度:树中各结点度的最大值。如图5-4中的树,度为3。 (3)结点的层次:根为第一层,根的孩子为第二层,以此类推。 (4)树的深度(高度):树中结点的最大层次。如图5-4中非空树的深度是4。 (5)树的宽度:树中各层的结点数的最大值。如图5-4中非空树的宽度是4。 3. 结点 结点分为叶子(终端结点)、根和内部结点(非终端结点、分支结点)。 (1)根结点:无前驱。如图5-4中的结点A。 (2)叶子(终端结点):度为零的结点,无后继。如图5-4中的结点E、F、I、J和H。 第 5 章　树和二叉树 177 (3)分支结点(非终端结点):度不为零的结点。除根结点外,分支结点也称内部结 点(1个前驱,多个后继)。如图5-4中的结点B、C、D和G。 4.结点间的关系 根据结点所在层次与其上层、下层以及同层的关系,结点之间存在以下关系: (1)孩子:结点的子树的根称为该结点的孩子。相应地,该结点称为孩子的双亲。 如图5-4中结点B、C、D是结点A的孩子;结点A是结点B、C、D的双亲。 (2)兄弟:同一双亲的孩子之间互为兄弟。如图5-4中的结点B、C、D互为兄弟,它 们共同的双亲是A。 (3)祖先:结点的祖先是从根到该结点所经分支上的所有结点。如图5-4中的结点I 的祖先是A、C、G。 (4)子孙:以某结点为根的子树中的任一结点都称为该结点的子孙。如图5-4中的 结点C的子孙是G、I、J。 5.兄弟间的关系 根据兄弟间的关系,一棵树的子树分为无序树和有序树。 如图5-5所示的两棵树根结点相同,构成子树的结点相同,但子树的顺序不同,它们 是两棵不同的有序树。 森林指m(m≥0)棵互不相交的树的集合,任何一棵非空树是一个二元组,即Tre= (root,F1),其中root称为根结点,F1称为子树森林,如图5-6所示。 图5- 5 两棵不同的树图5- 6 子树森林、森林与树 5.2.3 树的表示 1.结点连线表示 连线意指上方结点是下方结点的前驱(双亲),下方结点是上方结点的后继(孩子)。 如图5-7所示,结点A与结点B的连线表示结点A是结点B的双亲,结点B是结点A的 孩子。 178 新编数据结构及算法教程（第 2 版） 图5- 7 一棵树的结点连线示例 2. 二元组表示 如图5-7所示的树可表示为:T=(D,R), 其中,D={A,C,E,G,H,J},R= B,D,F,I, {,,,,, }。 C>,,,1,则其双亲结点是.i/2.。 (2)如果2i>n,则结点i为叶子,否则其左孩子是结点2i。 (3)如果2i+1>n,则结点i无右孩子,否则其右孩子是结点2i+1。 【证明】 首先证明(2)和(3),再导出(1)。 对于任意一棵完全二叉树,对编号为i的结点,假设它所在的层为k。 (1)如果k是第1层,k=1,i是根结点的编号,i=1。如果结点i有左孩子,则左孩子 编号是2i=2;如果有右孩子,则右孩子的编号是2i+1=3。 (2)如果k是最后一层,结点i为叶子结点,结点i既无左孩子,又无右孩子。 (3)如果k不是最后一层,假设i是第k层上所有非叶子结点的最后一个结点的编 号,根据性质2,第k层上的结点i满足:2k-1≤i≤2k-1,那么在第k层上结点i之前的 (i-2k-1)个结点都是度为2的结点,编号为i的结点度为2或1。所以对于第k层上的非 叶子结点i,一定存在左孩子,左孩子编号为第k+1层的第一个结点的编号2k 与第k层 上结点i之前度为2的结点个数(i-2k-1)的2倍之和,即2k+2(i-2k-1)=2i。如果存在 右孩子,右孩子编号为2i+1,如表5-1所示。 表5-1 完全二叉树第k层上的非叶子结点的孩子编号一览表 第k层结点编号2k-1(度为2) 2k-1+1(度为2) … i(度为2或1) … 2k-1 左孩子: 2k=2×2k-1 右孩子: 2k+1=2×2k-1+1 左孩子: 2k+2=2(2k-1+1) 右孩子: 2k+3=2(2k-1+1)+1 如果i的度为2 左孩子:2i 右孩子:2i+1 如果i的度为1 左孩子:2i 当2i>n时,编号为2i的结点不存在,说明双亲结点i既没有左孩子也没有右孩子, 所以编号为i的结点一定是叶子结点。当2i≤n时,说明编号为2i的结点存在,是编号为 i的结点的左孩子。 当2i+1>n时,编号为2i+1的结点不存在,说明双亲结点i没有右孩子;当2i+1≤ n时,说明编号为2i+1的结点存在,是编号为i的结点的右孩子。 由上述结果不难推出,对任何一个结点i,如果i是根结点,那么i无双亲,否则.i/2. 是i的双亲。 5.3.3 二叉树的抽象数据类型 二叉树的抽象数据类型描述如下。