数据结构是计算机及相关专业的核心课程,也是计算机及相关专业硕士研究生入学考试的必考科目,而且是理工专业的热门公选课程。本书介绍了数据结构、算法以及抽象数据类型的概念,讲述了线性表、栈和队列、字符串和多维数组、树和二叉树、图等常用数据结构,讨论了查找和排序技术。本书通过合理规划教学内容,梳理了知识单元及其拓扑结构,并兼顾概念层和实现层,既强调数据结构的基本概念和原理及方法,又注重数据结构的程序实现和实际运用,在提炼基础知识的同时,进行了适当的扩展和提高。 本书内容丰富,层次清晰,深入浅出且结合了实例,可作为计算机及相关专业数据结构课程的教材,也可供从事计算机软件开发和应用的工程技术人员参考和阅读。

第5章树和二叉树本章概述前面讨论的数据结构都属于线性结构,线性结构主要描述具有单一的前驱和后继关系的数据。树结构是一种比线性结构更复杂的数据结构,适合描述具有层次关系的数据,如祖先后代、上级下属、整体部分以及其他类似的关系。树结构在计算机领域有着广泛的应用,例如在编译程序中用语法树来表示源程序的语法结构、在数据挖掘中用决策树来进行数据分类等。
本章内容分为树和二叉树两部分,由实际问题引出树结构,介绍树的定义和基本术语,给出树的抽象数据类型定义,讨论树的存储结构;给出二叉树的定义和基本性质,讨论二叉树的存储结构,实现二叉链表存储的二叉树的遍历操作,*后讨论二叉树的经典应用——哈夫曼树。教学**二叉树的性质;二叉树和树的存储表示;二叉树的遍历及算法实现;树与二叉树的转换关系;哈夫曼树教学难点二叉树的层序遍历算法;二叉树的建立算法;哈夫曼算法教学内容
和
教学目标知识点树的定义和基本术语树和二叉树的抽象数据类型定义树和二叉树的遍历树的存储结构二叉树的定义二叉树的基本性质二叉树的顺序存储结构二叉链表三叉链表二叉树遍历的递归算法二叉树遍历的非递归算法二叉树的层序遍历算法二叉树的建立算法树、森林和二叉树之间的转换哈夫曼树及哈夫曼编码教 学 要 求了解理解掌握熟练掌握√√√√√√√√√√√√√√√数据结构——从概念到Java实现第5章树和二叉树5.1引言
树结构是一种比线性结构更复杂的数据结构,比较适合描述具有层次关系的数据,如祖先后代、上级下属、整体部分以及其他类似的关系。很多实际问题抽象出的数据模型是树结构,请看下面两个例子。
【例51】文件系统问题。Windows操作系统的文件目录结构如图51(a)所示,其中“/”表示文件夹,括号内的数字表示文件的大小(单位KB)。假设文件夹本身的大小是1KB,统计每个文件和文件夹的大小。
图51文件系统目录及其数据模型
【想法——数据模型】文件目录结构具有层次特点,每个文件夹均可包含多个子文件夹和文件。将每个文件或文件夹抽象为一个结点,文件夹与文件之间的关系抽象为结点之间的边,从而将文件目录结构抽象为一个树结构,如图51(b)所示。可以对树进行某种遍历,即对树中所有结点进行没有重复、没有遗漏的访问,在遍历过程中统计每个文件和文件夹的大小。那么,应该如何存储文件目录结构并在遍历过程中统计大小呢?
【例52】二叉表示树。编译系统在处理算术表达式时,通常将表达式转换为一棵二叉表示树,通过二叉表示树可以判断算术表达式是否存在语法错误,并将算术表达式转换为后缀形式,也称逆波兰式。请将给定的算术表达式转换为二叉表示树。
【想法——数据模型】二叉表示树是对应一个算术表达式的二叉树,并具有以下特点: ①叶子结点一定是操作数; ②分支结点一定是运算符。将一个算术表达式转换为二叉表示树时基于如下规则:
(1) 根据运算符的优先顺序,将表达式结合成(左操作数 运算符 右操作数)的形式。
(2) 由外层括号开始,运算符作为二叉表示树的根结点,左操作数作为根结点的左子树,右操作数作为根结点的右子树;
(3) 如果某子树对应的操作数为一个表达式,则重复第(2)步的转换,直到该子树对应的操作数不能再分解。
例如,将表达式(A B)(C DE)结合成((A B)(C (DE))),则二叉表示树的根结点是运算符,左操作数即左子树是(A B),右操作数即右子树是(C (DE))。对于左子树(A B),其根结点是运算符 ,左子树是A,右子树是B。对于右子树(C (DE)),其根结点是运算符 ,左子树是C,右子树是(DE)。依此类推,构造过程如图52所示。
图52二叉表示树的构造过程
5.2树的逻辑结构〖*4/5〗5.2.1树的定义和基本术语〖*2〗1. 树的定义在树中通常将数据元素称为结点(node)。
树(tree)是n(n≥0)个结点的有限集合这里定义的树在数学上属于有根树(rooted tree)。从数学角度讲,树结构是图的特例,无回路的连通图就是树,称为自由树(free tree)。本章讨论的是有根有序树,所谓有序树是指根结点的子树从左到右是有顺序的。。当n=0时,称为空树;任意一棵非空树满足以下条件:
(1) 有且仅有一个特定的称为根(root)的结点。
(2) 当n>1时,除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1、T2、…、Tm,其中每个集合又是一棵树显然,树的定义是递归的。由于树结构本身具有递归特性,因此对树的操作通常采用递归方法。,并称为这个根结点的子树(subtree)。
图53(a)是一棵具有9个结点的树: T={A,B,C,D,E,F,G,H,I},结点A为树T的根结点。除根结点A之外的其余结点分为两个不相交的集合: T1={B,D,E,F,I}和T2={C,G,H},T1和T2构成了根结点A的两棵子树;子树T1的根结点为B,其余结点又分为三个不相交的集合: T11={D},T12={E,I}和T13={F},T11、T12和T13构成了根结点B的三棵子树;依此类推,直到每棵子树只有一个根结点为止。
需要强调的是,树中根结点的子树之间是互不相交的。例如,图53(b)由于根结点A的两个子树之间存在交集,结点E既属于集合T1又属于集合T2,所以不是树;图53(c)中根结点A的两个子树之间也存在交集,边(B,C)依附的两个结点属于根结点A的两个子集T1和T2,所以也不是树。
图53树结构和非树结构的示意图
2. 树的基本术语
(1) 结点的度、树的度。某结点所拥有的子树的个数称为该结点的度(degree);树中各结点度的*大值称为该树的度。在如图53(a)所示的树中,结点A的度为2,结点B的度为3,该树的度为3。
(2) 叶子结点、分支结点。度为0的结点称为叶子结点(leaf node),也称为终端结点;度不为0的结点称为分支结点(branch node),也称为非终端结点。在如图53(a)所示的树中,结点D、I、F、G、H是叶子结点,其余结点都是分支结点。
(3) 孩子结点、双亲结点、兄弟结点。某结点的子树的根结点称为该结点的孩子结点(children node);反之,该结点称为其孩子结点的双亲结点(parent node);具有同一个双亲的孩子结点互称为兄弟结点(brother node)。在如图53(a)所示的树中,结点B是结点A的孩子,结点A是结点B的双亲,结点B和C互为兄弟,结点I没有兄弟。
(4) 路径、路径长度。如果树的结点序列n1n2…nk满足如下关系: 结点ni是结点ni 1的双亲(1≤i(5) 祖先、子孙。如果从结点x到结点y有一条路径,那么x就称为y的祖先(ancestor),y称为x的子孙(descendant)。显然,以某结点为根的子树中的任一结点都是该结点的子孙。在如图53(a)所示的树中,结点A、B、E均为结点I的祖先,结点B的子孙有D、E、F、I。
(6) 结点的层数、树的深度(高度)、树的宽度。我们规定根结点的层数(level)为1,对其余任何结点,若某结点在第k层,则其孩子结点在第k 1层;树中所有结点的*大层数称为树的深度(depth),也称为树的高度。树中每一层结点个数的*大值称为树的宽度(breadth)。在如图53(a)所示的树中,结点D的层数为3,树的深度为4,树的宽度为5。
5.2.2树的抽象数据类型
树在不同的实际应用中,其基本操作也不尽相同。下面给出基本操作只包含树的遍历的抽象数据类型(ADT)定义。针对具体应用,可在其基础上重新定义基本操作。ADT Tree
DataModel
树由一个根结点和若干棵子树构成,树中结点具有层次关系
Operation
initTree
输入: 无
功能: 初始化一棵树
输出: 一棵树
preOrder
输入: 无
功能: 前序遍历树
输出: 树的前序遍历序列
postOrder
输入: 无
功能: 后序遍历树
输出: 树的后序遍历序列
leverOrder
输入: 无
功能: 层序遍历树
输出: 树的层序遍历序列
endADT
5.2.3树的遍历操作定义
树的遍历(traverse)是指从根结点出发,按照某种次序访问树中所有结点,使得每个结点被访问一次且仅被访问一次。访问是一种抽象操作,在实际应用中可以对结点进行各种处理,如输出结点的信息、修改结点的某些数据等。对应到算法上,访问可以是一条简单语句,可以是一个复合语句,也可以是一个模块。为了不失一般性,在此将访问定义为输出结点的数据信息。树的遍历次序通常有前序(根)遍历和后序(根)遍历两种方式。此外,如果按树的层序依次访问各结点,则可得到另一种遍历次序: 层序遍历。
树的前序遍历操作定义为: 若树为空,则空操作返回;否则执行以下操作。
(1) 访问根结点。
(2) 按照从左到右的顺序前序遍历根结点的每一棵子树。
树的后序遍历操作定义为: 若树为空,则空操作返回;否则执行以下操作。
(1) 按照从左到右的顺序后序遍历根结点的每一棵子树。
(2) 访问根结点。
树的层序遍历也称树的广度遍历,其操作定义为: 从树的根结点开始,自上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。
例如,图53(a)所示树的前序遍历序列为: A B D E I F C G H,后序遍历序列为: D I E F B G H C A,层序遍历序列为: A B C D E F G H I。
5.3树的存储结构
在大量的实际应用中,人们使用多种存储方法来表示树。无论采用何种存储方法,都要求存储结构不仅能存储树中各结点的数据信息,还要表示结点之间的逻辑关系——父子关系。下面介绍几种基本的存储方法。
5.3.1双亲表示法
每个结点都记述自己的双亲。由树的定义可知,除根结点外,树中每个结点都有且仅有一个双亲结点。根据这一特性,用一维数组来存储树的各个结点(一般按层序存储),数组元素包括结点的数据信息、该结点的双亲在数组中的下标。树的这种存储方法称为双亲表示法(parent express),数组元素的结点结构如图54所示。其中,data存储树中结点的数据信息;parent存储该结点的双亲在数组中的下标。数组元素的结点结构可定义为类ParentNode,定义如下:public class ParentNode<T>{
private T data;//定义结点泛型数据域
private int parent;//定义结点双亲下标
public T getData() { return data; }
public void setData(T element) { data=element; }
public int getParent () { return next; }
public void seParent (int parent) { this.parent=parent; }
}
例如,图53(a)所示树的双亲表示法存储如图55所示,图中parent域的值为-1,表示该结点**亲,即该结点是根结点。
图54双亲表示法的结点结构图55双亲表示法的存储示意图



操作性能分析: 查找任意结点的父结点,仅需要常数时间,时间性能为O(1)。查找任意结点的孩子结点,需要遍历所有结点,时间性能为O(n)。
5.3.2孩子表示法
每个结点记述自己的所有孩子。树的孩子表示法(child express)是一种基于链表的存储方法,即把每个结点的孩子排列起来,看成一个线性表,且以单链表存储,称为该结点的孩子链表,所以n个结点共有n个孩子链表(叶子结点的孩子链表为空表)。n个孩子链表共有n个头引用,这n个头引用又构成了一个线性表,为了便于进图56孩子表示法的结点结构
行查找操作,可采用顺序存储。*后,将存放n个头引用的数组和存放n个结点数据信息的数组结合起来,构成孩子链表的表头数组。在孩子表示法中存在两类结点: 孩子结点和表头结点,其结点结构如图56所示。孩子结点由类ChildNode实现,头结点由类TreeNode实现,定义如下:public class ChildNode {
private int child;//结点对应头结点下标
private ChildNode next;//引用下一个孩子
public int getChild() { return child;}
public void setChild(int child) { this.child=child;}
public ChildNode getNext() { return next;}
public void setNext(ChildNode next) {this.next=next;}
}
public class TreeNode<T>{
private T data; //定义结点泛型数据域
private ChildNode firstChild; //孩子链表头引用
public T getData() { return data;}
public void setData(T data) { this.data=data;}
public ChildNode getFirstChild() { return firstChild;}
public void setFirstChild(ChildNode firstChild) {
this.firstChild=firstChild;}
}
例如,图57是图53(a)所示树采用孩子表示法的存储示意图。孩子表示法不仅表示了孩子结点的信息,而且联在同一个孩子链表中的结点具有兄弟关系。
图57孩子表示法的存储示意图
操作性能分析: 查找任意结点的父结点,需要遍历边表结点,时间性能为O(n)。查找任意结点的孩子结点,若该结点孩子个数为m,则时间性能为O(m)。
图58孩子兄弟表示法的结点结构
5.3.3孩子兄弟表示法
每个结点记述自己的长子和右兄弟。树的孩子兄弟表示法(children brother express)又称为二叉链表表示法,其方法是链表中的每个结点除数据域外,设置两个引用域分别引用该结点的**个孩子和右兄弟,链表的结点结构如图58所示。其中,data存储结点数据信息;firstChild存储**个孩子引用;rightSib存储右兄弟引用。孩子兄弟结点由类CSNode实现,定义如下:public class CSNode<T>{
private T data;//定义结点泛型数据域
private ChildNode firstChild;//引用长子
private ChildNode rightSib;//引用右兄弟
public T getData() { return data; }
public void setData(T data) { this.data=data; }
public ChildNode getFirstChild() { return firstChild;}
public void setFirstChild(ChildNode firstChild) { this.firstChild=
firstChild; }
public ChildNode getRightSib() { return rightSib; }
public void setRightSib(ChildNode rightSib) { this.rightSib=rightSib;}
}
例如,图59是图53(a)所示树采用孩子兄弟表示法的存储示意图。
图59树的孩子兄弟表示法的存储示意图
操作性能分析: 此存储方式便于实现树的各种操作。例如,若要访问某结点x的第 i个孩子,只需要从该结点的**个孩子引用找到第1个孩子后,沿着孩子结点的右兄弟域连续走i-1步,便可找到结点x的第i个孩子。
5.4二叉树的逻辑结构
树结构有很多变种,二叉树是一种*简单的树结构,而且任何树都可以简单地转换为对应的二叉树。所以,二叉树是本章的**。
5.4.1二叉树的定义
二叉树(binary tree)是n(n≥0) 个结点的有限集合,该集合或者为空集(称为空二叉树),或图510一棵二叉树
者由一个根结点和两棵互不相交的、分别称为根结点的左子树(left subtree)和右子树(right subtree)的二叉树组成。二叉树如图510所示,其具有如下特点。
(1) 每个结点*多有两棵子树,即二叉树不存在度大于2的结点。
(2) 二叉树的左右子树不能任意颠倒,如果某结点只有一棵子树,则必须指明它是左子树还是右子树。
需要强调的是,二叉树和树是两种不同的树结构。首先,二叉树不是度为2的树。例如,图511(a)所示是一棵二叉树,但这棵二叉树的度是1;假设图511(b)是一棵度为2的树,则结点B是结点A的**个孩子,结点C是结点A的第二个孩子,并且可以为结点A再增加孩子。其次,树的孩子有序的关系,即第1个孩子,第2个孩���,…,第i个孩子,但二叉树的孩子却有左右之分,即使二叉树中某结点只有一个孩子,也要区分它是左孩子还是右孩子。例如,假设图511(c)所示是二叉树,则它们是两棵不同的二叉树,假设图511(d)所示是树,则它们是同一棵树。
图511二叉树和树是两种树结构
在实际应用中,经常用到如下几种特殊的二叉树。
1. 斜树
所有结点都只有左子树的二叉树称为左斜树(left oblique tree);所有结点都只有右子树的二叉树称为右斜树(right oblique tree);左斜树和右斜树统称为斜树(oblique tree),如图512所示。斜树的特点是: ①每一层只有一个结点; ②斜树的结点个数与其深度相同。
图512斜树示例2. 满二叉树
在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,则这样的二叉树称为满二叉树(full binary tree)。图513(a)是一棵满二叉树,图513(b)不是满二叉树,因为虽然所有分支结点都存在左右子树,但叶子不在同一层上。满二叉树的特点是: ①叶子只能出现在*下一层; ②只有度为0和度为2的结点。
图513满二叉树和非满二叉树示例
3. 完全二叉树
对一棵具有n个结点的二叉树按层序编号,如果编号为i(1≤i≤n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树(complete binary tree)。显然,一棵满二叉树必定是一棵完全二叉树。完全二叉树的特点是: ① 深度为k的完全二叉树在k-1层是满二叉树; ② 叶子结点只能出现在*下两层,且*下层的叶子结点都集中在左侧连续的位置;③ 如果有度为1的结点,则只可能有一个,且该结点只有左孩子。图514给出了完全二叉树和非完全二叉树示例。
图514完全二叉树和非完全二叉树示例
5.4.2二叉树的基本性质
【性质51】在一棵二叉树中,如果叶子结点个数为n0,度为2的结点个数为n2,则n0=n2+1。

目录第1章绪论1 1.1问题求解与程序设计2 1.1.1程序设计的一般过程2 1.1.2数据结构在程序设计中的作用5 1.1.3算法在程序设计中的作用6 1.1.4本书讨论的主要内容7 1.2数据结构的基本概念8 1.2.1数据结构8 1.2.2抽象数据类型11 1.3算法的基本概念13 1.3.1算法及算法的特性13 1.3.2算法的描述方法14 1.4算法分析16 1.4.1算法的时间复杂度16 1.4.2算法的空间复杂度18 1.4.3算法分析举例18 1.5扩展与提高21 1.5.1从数据到大数据21 1.5.2算法分析的其他渐进符号22 思想火花——概率算法23 习题24 第2章线性表27 2.1引言28 2.2线性表的逻辑结构29 2.2.1线性表的定义29数据结构——从概念到Java实现目录2.2.2线性表的抽象数据类型29 2.2.3线性表的Java接口定义31 2.3线性表的顺序存储结构及实现31 2.3.1顺序表的存储结构31 2.3.2顺序表的实现32 2.3.3顺序表的使用37 2.4线性表的链接存储结构及实现38 2.4.1单链表的存储结构39 2.4.2单链表的实现41 2.4.3单链表的使用47 2.4.4双链表48 2.4.5循环链表50 2.5顺序表和链表的比较51 2.6扩展与提高52 2.6.1线性表的静态链表存储52 2.6.2顺序表的动态分配方式54 2.7应用实例55 2.7.1约瑟夫环问题55 2.7.2一元多项式求和57 思想火花——好算法是反复努力和重新修正的结果61 习题62 实验题65 第3章栈和队列67 3.1引言68 3.2栈69 3.2.1栈的逻辑结构69 3.2.2栈的顺序存储结构及实现70 3.2.3栈的链接存储结构及实现73 3.2.4顺序栈和链栈的比较76 3.3队列76 3.3.1队列的逻辑结构76 3.3.2队列的顺序存储结构及实现77 3.3.3队列的链接存储结构及实现82 3.3.4循环队列与链队列的比较85 3.4扩展与提高85 3.4.1两栈共享空间85 3.4.2双端队列87 3.5应用举例88 3.5.1括号匹配问题88 3.5.2表达式求值89 思想火花——好程序要能识别和处理各种输入92 习题93 实验题95 第4章字符串和多维数组97 4.1引言98 4.2字符串99 4.2.1字符串的逻辑结构99 4.2.2字符串的存储结构101 4.2.3模式匹配101 4.3多维数组105 4.3.1数组的逻辑结构105 4.3.2数组的存储结构与寻址106 4.4矩阵的压缩存储107 4.4.1特殊矩阵的压缩存储107 4.4.2稀疏矩阵的压缩存储110 4.5扩展与提高112 4.5.1稀疏矩阵的转置运算112 4.5.2广义表114 4.6应用实例118 4.6.1发纸牌118 4.6.2八皇后问题119 思想火花——用常识性的思维去思考问题121 习题121 实验题123 第5章树和二叉树125 5.1引言126 5.2树的逻辑结构127 5.2.1树的定义和基本术语127 5.2.2树的抽象数据类型128 5.2.3树的遍历操作定义129 5.3树的存储结构130 5.3.1双亲表示法130 5.3.2孩子表示法131 5.3.3孩子兄弟表示法131 5.4二叉树的逻辑结构133 5.4.1二叉树的定义133 5.4.2二叉树的基本性质134 5.4.3二叉树的抽象数据类型定义136 5.4.4二叉树的遍历操作定义137 5.4.5二叉树的Java接口定义139 5.5二叉树的存储结构及实现139 5.5.1顺序存储结构139 5.5.2二叉链表140 5.5.3三叉链表145 5.6森林146 5.6.1森林的逻辑结构146 5.6.2树、森林与二叉树的转换147 5.7*优二叉树149 5.7.1哈夫曼算法149 5.7.2哈夫曼编码152 5.8扩展与提高154 5.8.1二叉树遍历的非递归算法154 5.8.2线索二叉树157 5.9应用实例161 5.9.1堆与优先队列161 5.9.2并查集165 思想火花——调试程序与魔术表演167 习题168 实验题169 第6章图171 6.1引言172 6.2图的逻辑结构173 6.2.1图的定义和基本术语173 6.2.2图的抽象数据类型定义176 6.2.3图的遍历操作176 6.2.4图的Java接口定义178 6.3图的存储结构及实现179 6.3.1邻接矩阵179 6.3.2邻接表183 6.3.3邻接矩阵和邻接表的比较188 6.4*小生成树188 6.4.1Prim算法189 6.4.2Kruskal算法192 6.5*短路径196 6.5.1Dijkstra算法196 6.5.2Floyd算法199 6.6有向无环图及其应用201 6.6.1AOV网与拓扑排序201 6.6.2AOE网与关键路径204 6.7扩展与提高206 6.7.1图的其他存储方法206 6.7.2图的连通性208 6.8应用实例210 6.8.1七巧板涂色问题210 6.8.2医院选址问题211 思想火花——直觉可能是错误的213 习题214 实验题217 第7章查找技术219 7.1引言220 7.1.1查找的基本概念220 7.1.2查找算法的性能221 7.2线性表的查找技术221 7.2.1线性表查找结构的定义221 7.2.2顺序查找222 7.2.3折半查找222 7.3树表的查找技术225 7.3.1二叉排序树225 7.3.2平衡二叉树231 7.3.3B树235 7.4散列表的查找技术239 7.4.1散列查找的基本思想239 7.4.2散列函数的设计240 7.4.3处理冲突的方法242 7.4.4散列查找的性能分析245 7.4.5开散列表与闭散列表的比较246 7.5各种查找方法的比较247 7.6扩展与提高247 7.6.1顺序查找的改进——分块查找247 7.6.2折半查找的改进——插值查找248 7.6.3B树的改进——B 树249 思想火花——把注意力集中于主要因素,不要纠缠于噪声250 习题251 实验题253 第8章排序技术255 8.1引言256 8.1.1排序的基本概念256 8.1.2排序算法的性能257 8.1.3排序类的定义257 8.2插入排序258 8.2.1直接插入排序258 8.2.2希尔排序260 8.3交换排序261 8.3.1起泡排序261 8.3.2快速排序263 8.4选择排序266 8.4.1简单选择排序266 8.4.2堆排序268 8.5归并排序273 8.5.1二路归并排序的递归实现273 8.5.2二路归并排序的非递归实现275 8.6各种排序技术的使用277 8.7各种排序方法的比较277 8.8扩展与提高279 8.8.1排序问题的时间下界279 8.8.2基数排序280 思想火花——学会“盒子以外的思考”283 习题284 实验题286 附录A预备知识289 A.1数学术语289 A.2级数求和289 A.3集合290 A.4关系291 附录BJava语言基本语法293 B.1程序文件结构293 B.2数据类型294 B.3Java编程规范295 B.4控制语句295 B.5函数296 B.6类与对象297 B.7接口298 B.8异常处理299 附录C中英文词汇对照表301 参考文献305