正版新书]数据结构与数据库应用教程(高等院校信息技术规划教材)

部 数据结构
章 绪论
1.1 数据结构的概念
1.1.1 数据结构的范畴
1.1.2 相关概念和术语
1.2 算法和算法分析
1.2.1 算法的基本概念
1.2.2 算法复杂度
小结
习题
第2章 线表
2.1 线表的逻辑结构
2.1.1 线表的定义
2.1.2 线表的基本作 2.2 线表的顺序存储及运算实现
2.2.1 顺序存储的特点
2.2.2 顺序表上的运算实现
. 线表的链式存储及运算实现
..1 链式存储的特点
..2 链表上的运算实现
小结
习题
第3章 特殊线表
3.1 栈
3.1.1 栈的定义
3.1.2 栈的存储及运算实现
3.2 队列
3.2.1 队列的定义
3.2.2 队列的存储及运算实现
3.3 串
3.3.1 串的定义
3.3.2 串的存储
小结
习题
第4章 数组
4.1 数组的定义
4.2 数组的存储及运算实现
小结
习题
第5章 树与二树 5.1 树
5.1.1 树的定义
5.1.2 相关术语
5.2 二树 5.2.1 二叉树的定义
5.2.2 二叉树的质
5.. 二叉树的存储结构
5.3 二叉树的遍历
小结
习题

第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学校行政层次结构树由于树具有明显的层次关系,因此,树与二叉树都可以用树这种数据结构来描述。在所有的层次关系中,人们熟悉的是血缘关系,按血缘关系可以很直观地理解树结构中各数据元素结点之间的关系,因此,在描述树结构时,也经常使用血缘关系中的一些术语。
抽象数据类型树的定义如下。ADTTree数据对象D:D是具有相同特的数据元素的集合。
数据关系R:若D为空集,则称为空树。否则:(1)在D中存在的称为根的数据元素root;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树,称为根root的子树。 基本操作:P=初始化树,销毁树,插入树,删除树,…ADTTree树的基本操作有以下几种。
(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。前面已经说过,树结构具有明显的层次关系,即树是一种层次结构。在树结构中,一般按如下原则分层:根结点在层,同一层上所有结点的所有子结点都在下一层。例如,在图5.1中,根结点A在层;结点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二叉树的定义二叉树(BinaryTree)是一种很有用的非线结构,它是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,只要将层到第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＜k,因为k只能是整数,因此,k=log2n+1。
质5若对含n个结点的完全二叉树从上到下且从左至右进行1～n的编号,则对完全二叉树中任意一个编号为i的结点,有:(1)若i=1,则该结点是二叉树的根,无双亲;否则,其双亲结点编号为i/2,其左孩子结点编号为2i,右孩子结点编号为2i+1。
(2)若2i＞n,则该结点无左孩子。
(3)若2i+1＞n,则该结点无右孩子。
5..二叉树的存储结构二叉树也可以采用两种存储方式:顺序存储结构和链式存储结构。
二叉树的顺序存储表示可描述为:#defineMAX_TREE_SIZE100//二叉树的结点数typedeTElemTypeSqBiTree\\[MAX_TREE_SIZE\\];//0号单元通常不用SqBiTreebt;这种存储结构适用于完全二叉树。其存储形式用一组连续的存储单元按照完全二叉树的每个结点“自上而下、从左至右”编号的顺序存放结点内容。一棵完全二叉树(满二叉树)如图5.4所示。
将这棵二叉树存到数组中,相应的下标对应其同样的位置,如图5.5所示。
图5.4完全二叉树示意图图5.5完全二叉树的顺序存储示意图根据二叉树的质5,完全二叉树和满二叉树采取顺序存储方式,树中结点的序号可以地反映出结点之间的逻辑关系,即可以做到复原二叉树。对于一般二叉树,只有将各层空缺处统统补上“虚结点”,其内容为空,才能将其改造成一棵完全二叉树。若空缺结点较多,势必造成空间利用率的下降,使树的插入、删除不便。在这种情况下,就应该考虑使用链式存储结构。
二叉树的链式存储结构中常用的是二叉链表和三叉链表。二叉链表的每个结点有一个数据域和两个指针域,一个指针指向左孩子,另一个指针指向右孩子。常见的二叉树结点结构及存储结构描述如图5.6所示,二叉链表具有不浪费空间,插入、删除方便等特点。
其中,lchld和rchild是分别指向该结点左孩子和右孩子的指针,data是数据元素的内容。二叉树的链式存储表示可描述为:typedefstructBiTNode//结点结构TElemTypedata;structBiTNodelchild,rchild;//左右孩子指针BiTNode,BiTree;图5.6二叉链表的存储结构这种存储结构的特点是寻找孩子结点容易,寻找双亲结点比较困难。因此,若需要频繁地寻找双亲结点,可以给每个结点添加一个指向双亲结点的指针域,便可以采用三叉链表的形式,其结点结构及存储结构描述如图5.7所示。 图5.7三叉链表的存储结构其中,data是数据域,parent、lchild和rchild都是指针域,分别存放指向双亲、左孩子和右孩子的指针。
5.3二叉树的遍历遍历指按某条搜索路线遍访每个结点且不重复(又称周游)。它是树结构插入、删除、修改、查找和排序运算的前提,是二叉树一切运算的基础和核心。二叉树是一种非线的数据结构,在对它进行操作时,总是需要逐一对每个数据元素实施操作,这样就存在一个操作顺序问题。由二叉树的递归定义可知,二叉树是由三个基本单元组成:根结点、左子树和右子树。由此提出了三种二叉树遍历的搜索路径:先(根)序遍历,中(根)序遍历,后(根)序遍历。
1.先序遍历算法的递归描述先序遍历的递归过程为:若二叉树为空树,则遍历结束;否则,(1)访问根结点;(2)先序遍历根结点的左子树;(3)先序遍历根结点的右子树。
二叉树先序遍历算法的递归描述为:voidPreorder(BiTreeT,void(visit)(TElemType&e))if(T)visit(T->data);//访问结点Preorder(T->lchild,visit);//遍历左子树Preorder(T->rchild,visit);//遍历右子树2.中序遍历算法的递归描述中序遍历的递归过程为:若二叉树为空树,则遍历结束;否则,(1)中序遍历根结点的左子树;(2)访问根结点;(3)中序遍历根结点的右子树。
二叉树中序遍历算法的递归描述为:voidInorder(BiTreeT)if(T)Inorder(T->lchild);//遍历左子树printf(T->data);//访问结点Inorder(T->rchild);//遍历右子树3.后序遍历算法的递归描述后序遍历的递归过程为:若二叉树为空树,则遍历结束;否则,(1)后序遍历根结点的左子树;(2)后序遍历根结点的右子树;(3)访问根结点。
二叉树后序遍历算法的递归描述为:voidPostorder(BiTreeT)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二叉树的示例