数据结构与数据库应用教程（高等院校信息技术规划教材）

作者简介

内容简介

第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＜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.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所示,二叉链表具有不浪费空间,插入、删除方便等特点。 其中,lchld和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二叉树的示例 本书主要包括两大部分，第一部分为数据结构，包括线性表、栈、队列、串、数组、树和图等，以及查找和排序等操作；第二部分为数据库技术，包括数据库系统概论、关系模型与关系代数，关系数据库标准语言SQL、数据库设计与优化、数据库安全与完整、事务管理与恢复等。