《数据结构与数据库应用教程》是为“数据结构与数据库”课程编写的教材,也可作为学习数据结构与数据库技术的参考教材。本书的前半部分为数据结构,包括线性表、栈、队列、串、数组、树和图等,以及查找和排序等操作;后半部分为数据库技术,包括数据库系统概论、关系模型与关系代数,关系数据库标准语言SQL、数据库设计与优化、数据库**与完整、事务管理与恢复等,*后以一个综合实例介绍了数据库应用系统的开发过程。本书概念清楚、**突出、内容丰富、结构合理、思路清晰、示例翔实,每章后均附有习题。本书主要面向数据结构与数据库初学者,可作为信息管理与信息系统、计算机及相关专业的本科教学,也可供自学计算机基础知识的读者参考。

第5章树与二叉树
本章学习目标 掌握树的定义及相关术语。
 理解二叉树的定义及性质。
 了解二叉树的存储结构。
 掌握二叉树遍历的基本方法。

本章介绍的树状结构是一类重要的非线性结构,也是一种分层结构,其中以二叉树*为常用。因为在实际应用中,对于给定的问题,许多是能够抽取层级模型的,而树和二叉树是处理层次模型的典型结构。因此,我们研究树和二叉树的存储与应用是非常有实际意义的。
5.1树〖*4/5〗5.1.1树的定义树是一种简单的非线性结构。在树这种数据结构中,所有数据元素之间的关系具有明显的层次特性。图5.1一般的树
图5.1表示了一棵一般的树。由图5.1可以看出,在用图形表示树这种数据结构时,很像自然界中的树,只不过是一棵倒长的树,因此,这种数据结构就用“树”来命名。
在树的图形表示中,总是认为在用直线连起来的两端结点中,上端结点是前驱,下端结点是后继。这样表示前后继关系的箭头就可以省略。
树(Tree)是n(n≥0)个有限数据元素的集合。当n=0时,称这棵树是空树。在一棵非空树T中:
(1) 有一个特殊的数据元素称为树的根结点,根结点没有前驱结点。
(2) 当n>1时,除根结点���外的其余数据元素被分为m(m>0)个互不相交的集合T1,T2,…,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1,T2,…,Tm称为这个根结点的子树。
从树的定义可以看出,树具有下面两个特点。
(1) 树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。
(2) 树中所有结点可以有零个或多个后继结点。
在现实世界中,能用树这种数据结构表示的例子有很多。例如,图5.2中的树表示了学校行政关系结构。图5.2学校行政层次结构树由于树具有明显的层次关系,因此,树与二叉树都可以用树这种数据结构来描述。在所有的层次关系中,人们*熟悉的是血缘关系,按血缘关系可以很直观地理解树结构中各数据元素结点之间的关系,因此,在描述树结构时,也经常使用血缘关系中的一些术语。
抽象数据类型树的定义如下。ADT Tree {
数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:若D为空集,则称为空树。否则:
(1)在D中存在**的称为根的数据元素root;
(2)当n>1时,其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm,其中每一个子集本身又是一棵符合本定义的树,称为根root的子树。
基本操作:P={初始化树,销毁树,插入树,删除树,… }
} ADT Tree树的基本操作有以下几种。
(1) 初始化操作: InitTree (&T)。
初始条件: 树T不存在。
操作结果: 构造空树T。
(2) 销毁操作: DestroyTree (&T)。
初始条件: 树T存在。
操作结果: 销毁树T。
(3) 插入树操作: InsertChild(&T, &p, i, c)。
初始条件: 树T存在。
操作结果: 将以c为根的树插入为结点p的第i棵子树。
(4) 删除树操作: DeleteChild(&T, &p, i)。
初始条件: 树T存在。
操作结果: 删除结点p的第i棵子树。
5.1.2相关术语
下面介绍树这种数据结构中的一些基本术语。
(1) 根结点: 在树结构中,每一个结点只有一个前驱,称为父结点,没有前驱的结点只有一个,称为树的根结点,简称为树的根。例如,在图5.1中,结点A是树的根结点。
(2) 叶子结点: 在树结构中,每一个结点可以有多个后继,它们都称为该结点的子结点。没有后继的结点称为叶子结点。例如,在图5.1中,结点C、E、G、H、I、J均为叶子结点。
(3) 度: 在树结构中,一个结点所拥有的后继个数称为该结点的度。例如,在图5.1中,根结点A的度为3;结点B的度为2;叶子结点的度为0。在树中,所有结点中的*大的度称为树的度。例如,图5.1所示的树的度为3。前面已经说过,树结构具有明显的层次关系,即树是一种层次结构。在树结构中,一般按如下原则分层: 根结点在第1层,同一层上所有结点的所有子结点都在下一层。例如,在图5.1中,根结点A在第1层;结点B、C、D在第2层;结点E、F、G、H在第3层;结点I、J在第4层。树的*大层次称为树的深度。例如,如图5.1所示的树的深度为4。
(4) 孩子、双亲、兄弟: 在树中,以某结点的一个子结点为根构成的树称为该结点的一棵子树。树中某个结点的子树之根称为该结点的孩子,相应地,该结点称为孩子的双亲或父亲。例如,在图5.1中,结点B、C、D是A的孩子;A是B结点的双亲。同一个双亲的孩子称为兄弟,E、F是兄弟,B、C、D是兄弟。
(5) 有序树和无序树: 如果一棵树中结点的各子树之间存在确定的次序关系,称这棵树为有序树;反之,则称为无序树。
5.2二叉树
二叉树是树状结构的另一个重要类型,许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换成二叉树。二叉树的结构规律性强,其存储结构及其算法都较为简单,因此,二叉树特别重要。
5.2.1二叉树的定义
二叉树(Binary Tree)是一种很有用的非线性结构,它是n(n≥0)个结点的有限集合,它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。
二叉树具有以下两个特点。
(1) 非空二叉树只有一个根结点;
(2) 每一个结点*多有两棵子树,且分别称为该结点的左子树与右子树。
图5.3二叉树
由以上特点可以看出,在二叉树中,每一个结点的度*大为2,即所有子树(左子树或右子树)也均为二叉树,而树结构中的每一个结点的度可以是任意的。另外,二叉树中的每一个结点的子树被明显地分为左子树与右子树。在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时,该结点即是叶子结点。如图5.3所示是一棵深度为4的二叉树。
5.2.2二叉树的性质
二叉树具有下列重要特性。
性质1 在二叉树的第k层上,*多有2k-1个结点。
根据二叉树的特点,这个性质是显然的。
性质2深度为k的二叉树*多有2k-1个结点。
深度为k的二叉树是指二叉树共有k层。根据性质1,只要将第1层到第k层上的*大的结点数相加,就可以得到整个二叉树中结点数的*大值,即1 21 22 … 2k-1=2k-1一棵深度为k且有2k-1个结点的二叉树称为满二叉树。完全二叉树是由满二叉树而引出来的。对于深度为k,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称为完全二叉树。即除第k层外,其他各层 (1~k-1) 的结点数都达到*大个数,第k层所有的结点都连续集中在*左边,这就是完全二叉树。
性质3在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个,即n0=n2 1对于这个性质说明如下: 假设二叉树中有n0个叶子结点,n1个度为1的结点,n2个度为2的结点,则二叉树中总的结点数为n=n0 n1 n2(51)在二叉树中除了根结点外,其余每一个结点都有**的一个分支进入。设二叉树中所有进入分支的总数为m,则二叉树中总的结点数为n,除了根结点,其余结点都有一个分支进入,即n=m 1。
又由于二叉树中这m个进入分支是分别由非叶子结点射出的,其中度为1的每个结点射出一个分支,度为2 的每个结点射出两个分支,因此,二叉树中所有度为1与度为2的结点射出的分支总数为n1 2n2。而在二叉树中,总的射出分支数应与总的进入分支数相等,即m=n1 2n2,于是得n=n1 2n2 1(52)*后比较式(51)和式(52),有n0 n1 n2=n1 2n2 1化简后得n0=n2 1。
即,在二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。
性质4具有n个结点的完全二叉树的深度为log2n 1。
证明: 设完全二叉树的深度为k,则根据性质2得2k-1≤n<2k,即k-1≤log2n性质5若对含n个结点的完全二叉树从上到下且从左至右进行1~n的编号,则对完全二叉树中任意一个编号为i的结点,有:
(1) 若i=1,则该结点是二叉树的根,**亲;否则,其双亲结点编号为i/2,其左孩子结点编号为2i,右孩子结点编号为2i 1。
(2) 若2i>n,则该结点无左孩子。
(3) 若2i 1>n,则该结点无右孩子。
5.2.3二叉树的存储结构
二叉树也可以采用两种存储方式: 顺序存储结构和链式存储结构。
二叉树的顺序存储表示可描述为: #define MAX_TREE_SIZE 100//二叉树的*大结点数
typede TElemTypeSqBiTree\[MAX_TREE_SIZE\];//0号单元通常不用
SqBiTree bt;这种存储结构适用于完全二叉树。其存储形式用一组连续的存储单元按照完全二叉树的每个结点“自上而下、从左至右”编号的顺序存放结点内容。一棵完全二叉树(满二叉树)如图5.4所示。
将这棵二叉树存到数组中,相应的下标对应其同样的位置,如图5.5所示。
图5.4完全二叉树示意图
图5.5完全二叉树的顺序存储示意图



根据二叉树的性质5,完全二叉树和满二叉树采取顺序存储方式,树中结点的序号可以**地反映出结点之间的逻辑关系,即可以做到**复原二叉树。对于一般二叉树,只有将各层空缺处统统补上“虚结点”,其内容为空,才能将其改造成一棵完全二叉树。若空缺结点较多,势必造成空间利用率的下降,使树的插入、删除不便。在这种情况下,就应该考虑使用链式存储结构。
二叉树的链式存储结构中*常用的是二叉链表和三叉链表。二叉链表的每个结点有一个数据域和两个指针域,一个指针指向左孩子,另一个指针指向右孩子。常见的二叉树结点结构及存储结构描述如图5.6所示,二叉链表具有不浪费空间,插入、删除方便等特点。
其中,lchild和rchild是分别指向该结点左孩子和右孩子的指针,data是数据元素的内容。二叉树的链式存储表示可描述为: typedef struct BiTNode {//结点结构
TElemType data;
struct BiTNodelchild, rchild; //左右孩子指针
} BiTNode, BiTree;图5.6二叉链表的存储结构
这种存储结构的特点是寻找孩子结点容易,寻找双亲结点比较困难。因此,若需要频繁地寻找双亲结点,可以给每个结点添加一个指向双亲结点的指针域,便可以采用三叉链表的形式,其结点结构及存储结构描述如图5.7所示。
图5.7三叉链表的存储结构
其中,data是数据域,parent、lchild和rchild都是指针域,分别存放指向双亲、左孩子和右孩子的指针。
5.3二叉树的遍历
遍历指按某条搜索路线遍访每个结点且不重复(又称周游)。它是树结构插入、删除、修改、查找和排序运算的前提,是二叉树一切运算的基础和核心。二叉树是一种非线性的数据结构,在对它进行操作时,总是需要逐一对每个数据元素实施操作,这样就存在一个操作顺序问题。由二叉树的递归定义可知,二叉树是由三个基本单元组成: 根结点、左子树和右子树。由此提出了三种二叉树遍历的搜索路径: 先(根)序遍历,中(根)序遍历,后(根)序遍历。
1. 先序遍历算法的递归描述
先序遍历的递归过程为: 若二叉树为空树,则遍历结束;否则,
(1) 访问根结点;
(2) 先序遍历根结点的左子树;
(3) 先序遍历根结点的右子树。
二叉树先序遍历算法的递归描述为: void Preorder (BiTree T, void( visit)(TElemType& e))
{ if (T) {
visit(T->data); //访问结点
Preorder(T->lchild, visit);//遍历左子树
Preorder(T->rchild, visit);//遍历右子树
}
}2. 中序遍历算法的递归描述
中序遍历的递归过程为: 若二叉树为空树,则遍历结束;否则,
(1) 中序遍历根结点的左子树;
(2) 访问根结点;
(3) 中序遍历根结点的右子树。
二叉树中序遍历算法的递归描述为: void Inorder (BiTree T)
{
if (T) {
Inorder(T->lchild);//遍历左子树
printf(T->data); //访问结点
Inorder(T->rchild);//遍历右子树
}
}3. 后序遍历算法的递归描述
后序遍历的递归过程为: 若二叉树为空树,则遍历结束;否则,
(1) 后序遍历根结点的左子树;
(2) 后序遍历根结点的右子树;
(3) 访问根结点。
二叉树后序遍历算法的递归描述为: void Postorder (BiTree T)
{
if (T) {
Postorder(T->lchild);//遍历左子树
Postorder(T->rchild);//遍历右子树
printf(T->data);//访问结点
}
}可见,遍历二叉树的算法中的基本操作是访问结点,不论按哪一种次序进行遍历,对含n个结点的二叉树,其时间复杂度均为O(n)。
小结
本章主要介绍树、二叉树的概念及遍历方法等。
(1) 树是一种非线性的数据结构,是若干结点的集合,由**的根结点和若干棵互不相交的子树构成。其中每一棵子树又是一棵树,也是由**的根结点和若干棵互不相交的子树组成的,由此可知: 树的定义是递归的。树的结点数目可以为0,为0的时候是一棵空树。
(2) 树是一种层次数据结构,**层只有一个结点,称为树根结点,其后每一层都是上一层相应结点的后继结点。每个结点可以有任意多个后继结点,但除树根结点外,每个结点有并且只能有一个前驱结点。树中结点的前驱结点称为该结点的父亲或双亲,后继结点称为该结点的孩子。
(3) 二叉树是一种特殊的树状结构,它的特点是每个结点*多只有两棵子树,并且二叉树的子树有左右之分,其次序不能任意颠倒。
(4) 二叉树的存储结构分为顺序存储结构和链式存储结构两种。顺序存储*适合于完全二叉树,使用顺序存储结构要从数组下标为1开始。
(5) 二叉树的遍历是指按一定的规则和次序访问树中的每个结点,且每个结点只能被访问一次。它包括先序、中序、后序三种不同的遍历次序。
习题
5.1写出如图5.8所示的树的叶子结点、非叶子结点、各结点的度和树深。
5.2已知一棵二叉树如图5.9所示,给出树的先序遍历序列、中序遍历序列和后序遍历序列。
图5.8一般树的示例
图5.9二叉树的示例

目录 **部分数 据 结 构 第1章绪论3 1.1数据结构的概念3 1.1.1数据结构的范畴3 1.1.2相关概念和术语4 1.2算法和算法分析7 1.2.1算法的基本概念7 1.2.2算法复杂度11 小结13 习题14第2章线性表15 2.1线性表的逻辑结构15 2.1.1线性表的定义15 2.1.2线性表的基本操作16 2.2线性表的顺序存储及运算实现17 2.2.1顺序存储的特点17 2.2.2顺序表上的运算实现17 2.3线性表的链式存储及运算实现21 2.3.1链式存储的特点22 2.3.2链表上的运算实现24 小结26 习题27第3章特殊线性表28 3.1栈28 3.1.1栈的定义28 3.1.2栈的存储及运算实现29 3.2队列31 3.2.1队列的定义31 3.2.2队列的存储及运算实现33 3.3串35 3.3.1串的定义35 3.3.2串的存储37 小结37 习题38第4章数组39 4.1数组的定义39 4.2数组的存储及运算实现40 小结42 习题42第5章树与二叉树43 5.1树43 5.1.1树的定义43 5.1.2相关术语44 5.2二叉树45 5.2.1二叉树的定义45 5.2.2二叉树的性质46 5.2.3二叉树的存储结构47 5.3二叉树的遍历48 小结50 习题50第6章图51 6.1图的定义和术语51 6.2图的存储表示53 6.3图的遍历55 小结57 习题58第7章查找59 7.1基本概念59 7.2静态查找表60 7.2.1顺序查找60 7.2.2折半查找61 7.2.3索引查找62 7.3动态查找表63 7.3.1二叉排序树64 7.3.2平衡二叉树66 7.4哈希表的查找66 小结69 习题69第8章排序70 8.1基本概念70 8.2插入排序71 8.2.1直接插入排序71 8.2.2希尔排序73 8.3交换排序74 8.3.1冒泡排序74 8.3.2快速排序76 8.4选择排序78 8.5归并排序79 小结81 习题82 第二部分数据库技术 第9章数据库系统概述85 9.1数据库系统的作用85 9.1.1数据与数据管理85 9.1.2数据库应用88 9.2数据库处理技术的发展过程91 9.2.1人工管理阶段91 9.2.2文件系统阶段92 9.2.3数据库系统阶段93 9.2.4**数据库阶段95 9.3数据模型97 9.3.1概念模型97 9.3.2数据模型101 9.3.3层次模型103 9.3.4网状模型104 9.3.5关系模型106 9.3.6面向对象模型109 9.4数据库系统的结构111 9.4.1数据库系统的三级模式结构111 9.4.2数据库系统的二级映像113 9.4.3数据库体系结构114 9.5数据库管理系统117 9.5.1DBMS的工��模式117 9.5.2DBMS的主要功能118 9.5.3DBMS的组成119 小结120 习题121第10章关系模型与关系代数122 10.1关系模型122 10.2关系代数126 10.2.1集合的三种基本运算——交、并、差126 10.2.2关系的基本运算129 小结133 习题134第11章关系数据库标准语言——SQL135 11.1SQL概述及特点135 11.1.1SQL概述135 11.1.2SQL的特点136 11.1.3SQL的基本概念137 11.2SQL的数据定义138 11.2.1数据库的定义138 11.2.2基本表的定义141 11.2.3索引的定义147 11.3SQL的单表查询149 11.3.1SELECT语句概述149 11.3.2投影运算151 11.3.3选择运算153 11.3.4排序运算157 11.3.5查询表158 11.4SQL的连接查询159 11.4.1等值与非等值连接159 11.4.2自表连接162 11.4.3外连接163 11.5SQL的聚合查询166 11.5.1聚合函数166 11.5.2分组聚合167 11.6SQL的嵌套子查询169 11.6.1使用IN的子查询169 11.6.2使用比较运算符的子查询170 11.6.3使用存在量词EXISTS的子查询172 11.7集合运算173 11.8SQL的数据操纵174 11.8.1插入数据174 11.8.2更新数据176 11.8.3删除数据178 11.9视图179 11.9.1创建视图179 11.9.2查询视图181 11.9.3视图更新182 11.9.4删除视图183 小结184 习题184第12章数据库设计及优化189 12.1数据库设计方法189 12.1.1数据库和信息系统189 12.1.2数据库设计过程190 12.2需求分析192 12.2.1需求分析的任务192 12.2.2需求分析的步骤193 12.2.3需求分析的方法193 12.3概念结构设计195 12.3.1概念模型的基本概念195 12.3.2概念模型的表示方法195 12.3.3概念结构的特点196 12.3.4概念结构设计的方法197 12.3.5概念结构设计的步骤198 12.4规范化200 12.4.1关系模式规范化的必要性200 12.4.2函数依赖201 12.4.3范式与规范化203 12.4.4模式分解原则207 12.4.5规范化的本质分析与总结207 12.5逻辑结构设计208 12.5.1概念模型向关系模型的转换208 12.5.2数据模型的优化211 12.5.3数据库逻辑设计案例212 12.6数据库的物理设计214 12.6.1数据库物理设计的方法214 12.6.2确定数据库的物理结构215 12.6.3对物理结构进行评价216 12.7数据库的实施与维护216 12.7.1数据库的实施216 12.7.2数据库的维护218 小结219 习题219第13章数据库**性与完整性221 13.1数据库**性221 13.1.1数据库**的基本概念221 13.1.2用户管理223 13.1.3角色管理225 13.2数据库完整性226 13.2.1完整性约束的概念和类型227 13.2.2完整性约束的管理228 13.3TransactSQL基础233 13.3.1SQL对象的命名规则和注释233 13.3.2数据类型233 13.3.3变量237 13.3.4函数239 13.3.5批处理和流程控制242 13.4游标246 13.4.1游标的使用247 13.4.2当前游标集的修改250 13.5存储过程252 13.5.1存储过程概述252 13.5.2创建和执行存储过程252 13.5.3修改和删除存储过程254 13.6触发器255 13.6.1触发器概述255 13.6.2创建触发器256 13.6.3删除和修改触发器258 小结259 习题259第14章事务管理与恢复260 14.1事务260 14.1.1并发操作时产生的问题260 14.1.2事务的概念262 14.1.3事务的特性263 14.2并发控制264 14.3恢复与备份266 14.3.1数据库系统的故障266 14.3.2数据库备份267 14.3.3数据库恢复268 小结271 习题271第15章数据库应用开发272 15.1ADO.NET概述272 15.2系统分析276 15.2.1系统需求分析276 15.2.2系统用例分析277 15.2.3系统时序图278 15.3数据库分析和设计279 15.3.1数据库分析279 15.3.2数据库设计279 15.4数据库的连接和访问281 15.4.1数据库的连接281 15.4.2数据库的访问282 15.5系统界面设计及相关代码实现284 15.5.1酒店客房管理系统的首界面设计及其代码实现284 15.5.2客房信息管理界面的设计及其代码实现286 小结287参考文献288