第5章树和二叉树 树与二叉树都属于树(形)结构。树结构是一种比线性结构复杂的非 线性数据结构,比较适合描述具有层次关系的数据,例如记载“祖先—后 代”的族谱、表述“上级—下级”的组织机构、表示“整体—部分”的事物构 成等。树 结构在计算机领域中有着广泛的应用,特别是二叉树。例如,操作 系统中用树表示文件目录的组织结构;编译系统中用语法树表示源程序的 语法结构;数据挖掘中用决策树进行数据分类。 本章讨论树与二叉树的存储设计及遍历操作;二叉树的二叉链表实 现;树或森林与二叉树之间的相互转换;二叉树的典型应用———哈夫曼树 与哈夫曼编码。 本章主要知识点 ● 树的逻辑特性和存储设计。 ● 树与森林的遍历方法。 ● 二叉树的性质、存储设计。 ● 二叉树的创建、遍历、销毁等算法。 ● 树或森林与二叉树之间的相互转换。 ● 哈夫曼树及哈夫曼编码。 本章教学目标 ● 掌握树结构的逻辑特性并用于问题建模。 ● 掌握树、二叉树的存储方法并在具体应用中选择或设计合适的存储 结构。 ● 掌握二叉树的遍历原理与方法并能用于解决问题。 ● 掌握哈夫曼树与哈夫曼编码的构建并能够用于解决应用问题。 4 　数据结构原理与应用 5.树 1 树是一种非线性结构,其存储与操作与线性结构完全不同,树的定义是递归的,所以, 树的许多操作可用递归程序实现。 5.1 树的定义与表示 1. 树(是n(个数据元素的有限集合。当n=0时,称为空树;任意一棵非空 树满足下列条件。 tre) n≥0) ①有且仅有一个没有前驱的特殊元素,即根(root)结点①。 ②当n>1时,除根结点之外的其余数据元素被分成 m ( m >0)个互不相交的集合 T1,T2,…,Tm ,其中每个集合又是一棵树,称为根的子树(subtre);即数据元素 D = {t}∪T1∪T2∪…∪Tm ,且Ti∩Tj =. 。 roo ③对于每棵子树,同样可看成由子树的根与子树根的子树组成。 由上可知,树的定义是递归的,例如图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 章　树和二叉树　51 图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.各类结 点 叶子(ef)结点:度为0的结点称为叶子结点,也称为终端结点 。 la 分支(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 16 　数据结构原理与应用 子孙。 3.路径和路径长度 路径(path):如果树的结点序列n1,n2,…,nk 满足结点ni 是结点ni+1的双亲(1≤ i|ai ,aj ∈D ,1≤i ,j ≤n ,有且仅有一个结点没有前驱结点,其余结点有唯 一前驱结点,任一个结点有零个、一个或多个后继结点} 基本操作: 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 左边的第1 个孩子,返回true;否则,返回false。 RightSibling(T, e, &rs_e) //访问兄弟 操作功能: 查询值为e 的元素的右边的第一个兄弟。 操作输出: 如果存在rs_e 为e 右边的第1 个兄弟,返回true;否则,返回false。 TreeEmpty(T) //测树空 操作功能: 判断树T 是否为空树。 操作输出: 如果T 是空树,返回true;否则,返回false。 TreeDepth(T) //测树深 操作功能: 查询树深。 操作输出: 返回树的深度。 InsertChild(&T, p, i, c) //插入结点 1 18 　数据结构原理与应用 操作功能: p 指向树T 的某个结点,插入结点c 为p 的第i 棵子树。 操作输出: 插入成功,返回true;否则,返回false。 DeleteChild(&T,p,i) //删除结点 操作功能: p 指向树T 的某个结点,删除p 的第i 棵子树。 操作输出: 删除成功,返回true;否则,返回false。 } ADT Tree 5.1.4 树的存储设计 树的存储方法有多种,例如顺序存储、链式存储、顺序和链式相结合的存储方法。本 节介绍双亲表示法、孩子表示法、孩子兄弟表示法等。 1.双亲表示 树的双亲表示是用一个数组来存储树,即采用顺序存储方式。数组元素包括两个成 员,即数据域和指针(游标)域,结构如图5-3所示。数据域用于存储数据元素,指针域用 图5-3 树的双亲表示中数 组元素结构示意图 于存储双亲在数组中的位置。存储描述如下。 template #define MAXNODE //树的结点个数 struct PNode //数组元素类型 { DT data; //数据域 int parent; //指针域,双亲在数组中的下标 }; 图5-4(a)所示“树2”的双亲存储示意图如图5-4(b)所示。 图5-4 树的双亲表示 这种存储结构利用了树中每个结点(除根以外)有唯一双亲的性质。该方法获取双亲 很方便,但求结点的孩子需要遍历整个表。 2.孩子链表表示 树的孩子链表表示(childlistexpress)是顺序存储和链式存储相结合的一种方式,数 据元素信息采用顺序存储,每个双亲的所有孩子形成一个链表,双亲结点的指针指向该链 表。“树2”的孩子链表存储示意图如图5-5所示。 第5 章　树和二叉树　1 19 图5-5 “树2”的孩子链表存储示意图 存储中涉及两种结点(表头结点和孩子结点),它们的结构如图5-6所示。表头结点 包含两个域:数据域data存储数据元素信息;指针域firstchild存储第一个孩子结点的位 置信息。孩子结点也包含两个域:孩子位置child存储孩子结点信息在表头结点中的位 置;指针域nextchild存储下一个孩子结点的位置信息。具体定义如下。 图5-6 结点结构示意图 template struct PNode //双亲结点 { DT data; //数据域 CTNode *firstchild; //指针域,指向孩子链的头 }; struct CTNode //孩子结点 { int child; //孩子位置 CTNode *nextchild; //指针域,指向下一个孩子结点 }; 在孩子链表存储表示法中,结点的孩子信息很容易得到,但双亲信息需要遍历表才可 获得。如果一个问题域中需要同时频繁地获取孩子信息和双亲信息,可以把双亲表示法 和孩子表示法结合起来,形成双亲孩子表示法。 3.双亲孩子表示 树的双亲孩子表示是在孩子表示法的表头信息中加入双亲信息形成的,这样既能直 接获取双亲信息,又能直接获取孩子信息。“树2”的双亲孩子表示如图5-7所示。 图5-7 带双亲信息的孩子链表存储示意图 4.孩子兄弟表示 树的孩子兄弟表示是一种链式存储。每个结点含有一个数据域和两个指针域,结点 1 20 　数据结构原理与应用 结构如图5-8所示。数据域存储数据元素信息;一个指针域指向结点的第一个孩子;另一 个指针域指向结点右边的第一个兄弟。结点定义如下。 图5-8 孩子兄弟存储的 结点结构 template struct TNode { DT data; //数据域 TNode *firstchild; //指向第一个孩子 TNode *rightsib; //指向第一个右兄弟 }; “树2”的孩子兄弟表示法如图5-9所示。 图5-9 “树2”的孩子兄弟存储示意图 树的孩子兄弟表示中因为每个结点有两个指针域,所以也称为树的二叉链表表示。 以上介绍了4种树的存储设计,但其实还有其他设计形式。具体应用中需要切合问 题抽象与问题求解的需要,选择或设计合适的存储方式。 5.1.5 树和森林的遍历 遍历是树或森林最基本操作。树或森林为非线性结构,遍历是结点查找的有效途径。 1.树的遍历 树的遍历(traverse)是指从根结点出发,按照某种次序访问树的所有结点,使得每个 结点被访问一次且仅被访问一次。由树的定义可知一棵树由根结点和m 棵子树构成,根 据先遍历根还是后遍历根,将树的遍历方法分为先根(序)遍历和后根(序)遍历。树具有 层次结构,按层次对树的遍历称为层序遍历。关于树的遍历共有上述3种方法。 遍历时可以从左往右,也可以从右往左,本书仅考虑从左往右的情况。各种遍历方法 如下。 (1)先根(序)遍历(preordertraversal) ● 先访问根结点; ● 然后从左往右,依次先根遍历每棵子树。 例如,“树2”的先根遍历序列为ABDEIFCGH。 (2)后根(序)遍历(postordertraversal) ● 先从左往右,依次后根遍历每棵子树。 ● 然后访问根结点。 第 5 章　树和二叉树　11 例如,“树2”的后根遍历序列为DIEFBGHCA 。 (3)层序遍历(eervra lvltaesl) 层序遍历方法为:从上往下、从左往右,依次遍历各结点 。 例如,“树2”的层序遍历方法为ABCDEFGHI 。 2.森林的遍历 森林由一棵以上的树组成。森林遍历的方法有两种:先序遍历和中序遍历。 (1)先序遍 历 先序遍历的方法是按树的先根遍历方法依次遍历各棵子树 。 图5-10所示“森林1”由3棵树组成。 第 1棵树的先根遍历序列为BDEIMN;第2棵 树的先根遍历序列为P;第3棵树的先根遍历 序列为CFGKJHL 。3个序列连起来,得到森 林先序遍历序列为BDEIMNPCFGKJHL 。 (2)中序遍历 图5-10 森林 1 中序遍历(l)方法是按 树 inordertraversa 的后根遍历方法依次遍历森林的各棵子树。 即:首先后序遍历第1棵树的根的各棵子树,接着访问第2棵树的根,然后后序遍历其 他树。 例如“森林1”的中序遍历:第1棵树的后根遍历序列为DMNIEB;第2棵树的后根 遍历序列为P;第3棵树的后根遍历序列为FKJGLHC 。三者连起来,得到“森林1”的中 序遍历序列为DMNIEBPFKJGLHC 。 森林可以分为3部分:第1棵树的根Ⅰ、第1棵树根的子树Ⅱ、其他树Ⅲ。在中序遍 历中,第1棵树的根处于遍历的中间位置,因此称为森林的中序遍历。 二叉树的定义与特性 二叉树与树一样,是一种树形结构,但它是一棵度不超过2的有序树。树形结构的术 语同样适用于二叉树。 5.1 二叉树的定义 2. 二叉树( e)是n(个有限结点的集合,0时为空二叉树。非空二叉 树 T 满足下列条件。 binarytrn≥0) n= ①有且仅有一个没有前驱的数据元素,即根结点。 ②当n>1时,除根结点之外的其余结点被分成2个互不相交的集合T1 和T2,分别 称为 T 的左子树和右子树,且T1 和T2 本身又均为二叉树;即数据元素 D ={root}∪T1 ∪T2,且T1∩T2=. 。 二叉树的定义是递归的。对于每棵子树,同样可看成由子树根与子树根的左、右子树 组成。 2. 5 122　数据结构原理与应用 二叉树可以有5种基本形态,如图5-11 所示。 图5-11 二叉树的5种基本形态 【思考】 ①一棵有3个结点的二叉树有几种形态? ②一棵二叉树交换左、右子树后还是同一棵二叉树吗? ③一棵有3个结点的树有几种形态? 5.2 特殊二叉树 2. 满二叉树、完全二叉树、斜树均为特殊形态的二叉树,如图5-12 所示。 图5-12 几种特殊二叉树