第5章树和二叉树 树与二叉树都属于树(形)结构。树结构是一种比线性结构复杂的非 线性数据结构,比较适合描述具有层次关系的数据,如记载“祖先—后代” 的族谱、表述“上级—下级”的组织机构、表示“整体—部分”的事物构成等。 树结构在计算机领域中有着广泛的应用,特别是二叉树。例如,操作 系统中用树表示文件目录的组织结构;编译系统中用语法树表示源程序的 语法结构;数据挖掘中用决策树进行数据分类。 本章讨论树与二叉树的存储设计及遍历操作;二叉树的二叉链表实 现;树或森林与二叉树之间的相互转换;二叉树的典型应用———最优二叉 树与哈夫曼编码。 本章主要知识点 ● 树的逻辑特性和存储设计。 ● 树与森林的遍历方法。 ● 二叉树的性质、存储设计。 ● 二叉树的创建、遍历、销毁等算法。 ● 树或森林与二叉树之间的相互转换。 ● 最优二叉树及哈夫曼编码。 本章教学目标 ● 掌握树结构的逻辑特性并用于问题建模。 ● 掌握树、二叉树的存储方法并在具体应用中选择或设计合适的存储 结构。 ● 掌握二叉树的遍历原理与方法并能用于解决问题。 ● 掌握最优二叉树与哈夫曼编码的构建并能够用于解决应用问题。 126 　数据结构原理与应用（第 2 版） 5.树 1 树是一种非线性结构,其存储与操作与线性结构完全不同,树的定义是递归的,因此, 树的许多操作可用递归程序实现。 5.1 树的定义与表示 1. 树(是n(个数据元素的有限集合。当n=0时,称为空树;任意一棵非空 微课视频tre) n≥0) 树满足下列条件。 root) (1)有且仅有一个没有前驱的特殊元素,即根(结点①。 (2)当n>1时,除根结点之外的其余数据元素被分成 m ( m >0)个互不相交的集合 T1,T2,…,Tm ,其中每个集合又是一棵树,称为根的子树(subtre);即数据元素 D = {且Ti∩Tj =. 。 root}∪T1∪T2∪…∪Tm , (3)对于每棵子树,同样可看成由子树的根与子树根的子树组成。 由上可知,树的定义是递归的,例如图5-1是一棵树。其中,①A为树根,T1、T2、T3 是A的子树;B、P、C分别为3棵子树的根。②T11 、T12分别为子树T1 的根B的子树; T31 、T32和T33分别为子树T3 的根C的子树。 图5- 1 树 1 在树结构中,尽管用无箭头的线表示结点之间的关系,但实际上树中双亲与孩子之间 是一种有向关系。 除了上述图形表示法之外,树还有嵌套集合表示、凹入表示和广义表表示等方法。嵌 套集合是指一些集合的集体,其中任何两个集合或者不相交,或者一个包含另一个。树的 嵌套集合表示是指根为一个大集合,根的子树构成这个大集合中若干互不相交的子集,如 此嵌套下去,如图5-2(a)所示。树的凹入表示如图5-2(b)所示,通过不同的缩进表示层 次包含关系,主要用于树的屏幕输出。树的广义表表示是用括号表示层次及其包含关系, 如图5-2(c)所示。 ① 在树中,常常将数据元素称为结点。 第 5 章　树和二叉树　127 图5- 2 树的各种表示法 5.2 树的术语 1. 1.结点的度和树的度 结点的度(degre) 结点所拥有的子树的个数称为该结点的度。例如在图5-1所示 的“树1中,(”) 结点A和C的度为3;结点B、I、G的度为2;结点E和H的度为1;其余结点 的度为0。 树的度树内结点度的最大值称为树的度。图5-1所示的“树1”的度为3。 2.各类结点 叶(leaf)结点度为0的结点称为叶结点,也称为终端结点。 分支(bh)结点度不为0的结点称为分支结点,也称为非终端结点。孩子结点(c(c) (n) (a) (r) hildnode) 树中某结点X的子树的根(即X的后继结点)称为X的孩子 结点。例如“树1”中A的孩子结点为B、P、C;B的孩子结点为D、E;C的孩子结点为F、 G、H。 双亲(parent)结点如果树中某结点Y是另一个结点X的孩子,则结点X(即Y的 前驱)称为Y的双亲结点。树中除根没有双亲结点外,其余的结点均有唯一的双亲结点。 例如“树1”中A是B、P、C的双亲;B是D、E的双亲;C是F、G、H的双亲。 兄弟(brother) 树中具有相同双亲的结点互为兄弟结点。例如,“树1”中B、P、C互 为兄弟;D、E互为兄弟;F、G、H互为兄弟。 堂兄弟树中双亲为兄弟的结点的孩子互为堂兄弟结点。例如,“树1”中D、E与F、 G、H互为堂兄弟。 祖先(ancestor) 从根到某结点X所经分支上的所有结点称为结点X的祖先。例 如,“树1”中M的祖先为A、B、E和I;K的祖先为A、C、G。 子孙(descendant) 以某结点X为根的子树中任一结点都称为结点X的子孙结点。 例如“树1中,(”) 除根结点A之外的所有结点均为A的子孙。F、G、H、K、J和L都是C的 1 28 　数据结构原理与应用（第2 版） 子孙。 3.路径和路径长度 路径(path) 如果树的结点序列n1,n2,…,nk 满足结点ni 是结点ni+1的双亲(1≤ i|ai ,aj ∈D ,1≤i ,j ≤n ,有且仅有一个结点没有前驱结点,其余结点有 唯一前驱结点,任一个结点有零个、一个或多个后继结点} 第5 章　树和二叉树　1 29 基本操作: InitTree(&T) //初始化树 操作功能: 创建一个空树T。 操作输出: 创建成功,返回true;不成功,退出。 DestroyTree(&T) //销毁树 操作功能: 释放树T 所占的存储空间。 操作输出: 无。 CreateTree(&T,definition) //创建树 操作功能: 按树的定义(definition)创建树T。 操作输出: 创建成功,返回true;否则,返回false。 ClearTree(&T) //清空树 操作功能: 把树T 变成一棵空树。 操作输出: 无。 PreTree(T) //先根遍历树 操作功能: 先根遍历树的各结点。 操作输出: 遍历结果。 PostTree(T) //后根遍历树 操作功能: 后根遍历树的各结点。 操作输出: 遍历结果。 LevelTree(T) //层序遍历树 操作功能: 层序遍历树的各结点。 操作输出: 遍历结果。 Root(T,&e) //访问树根 操作功能: 查询树根。 操作输出: 树非空,e 为树根元素,返回true;否则,返回false。 Parent(T,e, &par_e) //访问双亲 操作功能: 查询值为e 元素的双亲。 操作输出: 如果存在par_e 为e 的双亲,返回true;否则,返回false。 LeftFirstChild(T,e, &lc_e) //访问左孩子 操作功能: 查询值为e 的元素的左边的第一个孩子。 操作输出: 如果存在lc_e 为e 左边的第一个孩子,返回true;否则,返回false。 RightSibling(T, e, &rs_e) //访问兄弟 操作功能: 查询值为e 的元素的右边的第一个兄弟。 操作输出: 如果存在rs_e 为e 右边的第一个兄弟,返回true;否则,返回false。 TreeEmpty(T) //测树空 操作功能: 判断树T 是否为空树。 操作输出: 如果T 是空树,返回true;否则,返回false。 TreeDepth(T) //测树深 操作功能: 查询树深。 操作输出: 返回树的深度。 InsertChild(&T, p, i, c) //插入结点 操作功能: p 指向树T 的某个结点,插入结点c 为p 的第i 棵子树。 操作输出: 插入成功,返回true;否则,返回false。 DeleteChild(&T,p,i) //删除结点 操作功能: p 指向树T 的某个结点,删除p 的第i 棵子树。 操作输出: 删除成功,返回true;否则,返回false。 } ADT Tree 5.1.4 树的存储设计 树的存储方法有多种,如顺序存储、链式存储、顺序和链式相结合的存储方法。本节微课视频 1 30 　数据结构原理与应用（第2 版） 介绍双亲表示法、孩子链表表示法、双亲孩子表示法、孩子兄弟表示法。 图5-3 树的双亲表示中数 组元素结构示意图 1.双亲表示 树的双亲表示是用一个数组来存储树,即采用顺序存 储方式。数组元素包括两个成员,即数据域和指针(游标) 域,结构如图5-3所示。数据域用于存储数据元素,指针域 用于存储双亲在数组中的位置。存储描述如下。 template #define MAXNODE //树的结点个数 struct PTNode //数组元素类型 { DT data; //数据域 int parent; //指针域,双亲在数组中的下标 }; PTNode T[MAXNODE]; //树T 图5-4(a)所示“树2”的双亲存储示意图如图5-4(b)所示。 图5-4 树的双亲表示 这种存储结构利用了树中每个结点(除根以外)有唯一双亲的性质。该方法获取双亲 很方便,但求结点的孩子需要遍历整个表。 2.孩子链表表示 树的孩子链表表示是顺序存储和链式存储相结合的一种方式,数据元素信息采用顺 序存储,每个结点的所有孩子形成一个链表,双亲结点的指针指向该链表。“树2”的孩子 链表存储示意图如图5-5所示。 图5-5 “树2”的孩子链表存储示意图 第5 章　树和二叉树　1 31 存储中涉及两种结点(表头结点和孩子结点),它们的结构如图5-6所示。表头结点 包含两个域:数据域(data)存储数据元素信息;指针域(firstchild)存储第一个孩子结点的 位置信息。孩子结点也包含两个域:孩子位置(child)存储孩子结点信息在表头结点中的 位置;指针域(nextchild)存储下一个孩子结点的位置信息。具体定义如下。 图5-6 结点结构示意图 template struct PNode //双亲结点 { DT data; //数据域 CTNode *firstchild; //指针域,指向孩子链的头 }; struct CTNode //孩子结点 { int child; //孩子位置 CTNode *nextchild; //指针域,指向下一个孩子结点 }; 在孩子链表存储表示法中,结点的孩子信息很容易得到,但双亲信息需要遍历表才可 获得。如果一个问题域中需要同时频繁地获取孩子信息和双亲信息,可以把双亲表示法 和孩子表示法结合起来,形成双亲孩子表示法。 3.双亲孩子表示 树的双亲孩子表示是在孩子链表表示法的表头信息中加入双亲信息形成的,这样既 能直接获取双亲信息,又能直接获取孩子信息。带双亲信息的孩子链表存储示意图如 图5-7所示。 图5-7 带双亲信息的孩子链表存储示意图 图5-8 孩子兄弟存储的 结点结构 4.孩子兄弟表示 树的孩子兄弟表示是一种链式存储。每个结点含有一个数据域和两个指针域,结点 结构如图5-8所示。数据域存储数据元素信息;一个指针域指向结点的第一个孩子;另一 个指针域指向结点右边的第一个兄弟。结点定义如下。 template struct TNode { DT data; //数据域 TNode *firstchild; //指向第一个孩子 TNode *rightsib; //指向第一个右兄弟 }; 132 　数据结构原理与应用（第 2 版） “树2”的孩子兄弟存储示意图如图5-9所示。 图5- 9 “树2”的孩子兄弟存储示意图 树的孩子兄弟表示中因为每个结点有两个指针域,所以也称为树的二叉链表表示。 以上介绍了4种树的存储设计,但其实还有其他设计形式。具体应用中需要切合问 题抽象与问题求解的需要,选择或设计合适的存储方式。 1.树和森林的遍历 5.5 微课视频遍历是树和森林最基本的操作。树和森林为非线性结构,遍历是结点查找的有效 途径。 1. 树的遍历 树的遍历(traverse)是指从根结点出发,按照某种次序访问树的所有结点,使得每个 结点被访问一次且仅被访问一次。由树的定义可知,一棵树由根结点和 m 棵子树构成, 根据先遍历根还是后遍历根,将树的遍历方法分为先根(序)遍历和后根(序)遍历。树具 有层次结构,按层次对树的遍历称为层序遍历。关于树的遍历共有上述3种方法。 遍历时可以从左往右,也可以从右往左,本书仅考虑从左往右的情况。各种遍历方法 如下。 (1)先根(序)遍历(preordertraversal)。先访问根结点;然后从左往右,依次先根遍 历每棵子树。例如,“树2”的先根遍历序列为ABDEIFCGH 。 (2)后根(序)遍历(postordertraversal)。先从左往右,依次后根遍历每棵子树;然后 访问根结点。例如,“树2”的后根遍历序列为DIEFBGHCA 。 (3)层序遍历(eervra从左往右, lvltaesl)。层序遍历方法为从上往下、依次遍历各结 点。例如,“树2”的层序遍历序列为ABCDEFGHI 。 2. 森林的遍历 森林由一棵以上的树组成。森林遍历的方法有两种:先序遍历和中序遍历。 (1)先序遍历。先序遍历的方法是按树 的先根遍历方法依次遍历各棵子树。 图5-10 所示“森林1”由3棵树组成。第 1棵树的先根遍历序列为BDEIMN;第2棵 树的先根遍历序列为P;第3棵树的先根遍历 序列为CFGKJHL 。3个序列连起来,得到森 图5-10 森林 1 林先序遍历序列为BDEIMNPCFGKJHL 。 第 5 章　树和二叉树　331 (2)中序遍历。中序遍历(l)方法是按树的后根遍历方法依次遍历森 inordertraversa 林的各棵子树,即首先后序遍历第1棵树的根的各棵子树,接着访问第1棵树的根,然后 后序遍历其他树。 例如“森林1”的中序遍历:第1棵树的后根遍历序列为DMNIEB;第2棵树的后 根 遍历序列为P;第3棵树的后根遍历序列为FKJGLHC 。三者连起来,得到“森林1”的 中 序遍历序列为DMNIEBPFKJGLHC 。 森林可以分为3部分:第1棵树的根Ⅰ、第1棵树根的子树Ⅱ、其他树Ⅲ。在中序遍 历中,第1棵树的根处于遍历的中间位置,因此称为森林的中序遍历。 5.二叉树的定义与特性 2 二叉树与树一样,是一种树形结构,但它是一棵度不超过2的有序树。树形结构的 术 语同样适用于二叉树 。 2.二叉树的定义 5.1 二叉树(是n(个有限结点的集合,0时为空二叉树。非空二叉 binarytre) n≥0) n=微课视频 树 T 满足下列条件。①有且仅有一个没有前驱的数据元素,即根结点。②当n>1时,除 根结点之外的其余结点被分成两个互不相交的集合T1 和T2,分别称为 T 的左子树和右 子树,且T1 和T2 本身又均为二叉树;即数据元素 D ={root}∪T1∪T2,且T1∩ T2=. 。 二叉树的定义是递归的。对于每棵子树,同样可看成由子树根与子树根的左、右子树 组成。 二叉树可以有5种基本形态,如图5-11所示。 图5-11 二叉树的5种基本形态 【思考】 (1)一棵有3个结点的二叉树有几种形态? (2)一棵二叉树交换左、右子树后还是同一棵二叉树吗? (3)一棵有3个结点的树有几种形态? 134　数据结构原理与应用（第2版） 5.2 特殊二叉树 2. 满二叉树、完全二叉树、斜树均为特殊形态的二叉树,如图5-12所示。 图5-12 几种特殊二叉树 1.满二叉树( e ) fulbinarytr 满二叉树如图5-12(a)所示,是同样深度的二叉树中具有最多结点的二叉树。为标识 结点个数,图中按层序并从左往右对结点进行了编号。 满二叉树具有下列特性:①第 i 层有2i-1个结点;②所有叶结点均在最后一层,深度 为 k 的满二叉树有2k-1个叶结点;③深度为 k 的满二叉树的结点总数为2k -1;④没有 度为1的结点;⑤具有 n 个结点的满二叉树高度为ln+1 )。 2.完全二叉树(completebinarytre ) og2( 对一棵具有 n 个结点的二叉树按层序编号,如果编号为i(1≤i≤n)的结点与同样深 度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同,则这棵二叉树称为完全二 叉树。也就是说,在完全二叉树中,当树的结点小于同等深度的满二叉树时,是从满二叉 树的最底层,从右到左,结点依次减少。例如,图5-12(b)所示的二叉树是完全二叉树, 图5-12(c)所示的二叉树不是完全二叉树。 完全二叉树具有下列特性:①叶结点只出现在最下两层,且最下层的叶结点都集中 在二叉树的左部;②深度为 k 的完全二叉树在k-1层上一定是满二叉树;③在结点个数 n 一定的各棵二叉树中,完全二叉树是其中最矮的二叉树;④当结点个数为偶数时,完全 二叉树只有一个度为1的结点;当结点个数为奇数时,没有度为1的结点。 3.斜树(obliquetre ) 树中结点只有左孩子(左斜树)或只有右孩子(右斜树)的二叉树称为斜树,如图5-12(d) 和图5-12(e)所示。