搜索
南昌大学第1/209页第十章树与二叉树南昌大学第2/209页树形结构是一种重要的非线性。树结构在客观世界中广泛存在，如行政组织机构和人类社会的家谱及图书馆的藏书、工厂产品的结构以及操作系统中文件目录等。本章重点讨论二叉树的存储结构及其基本的运算，并简单介绍树形结构的应用。南昌大学第3/209页一、树的定义树是n（n0)个节点的集合，它满足下列两个条件：1)仅有一个特定的根节点。2)其余节点可分为m(m:0)个互不相交的子集T1、T2…、Tn，每个子集都是一棵树，称为根的子树。树的定义中用到了树的概念，是一个递归定义，显示了树的固有特性，即一棵树由若干棵子树构成，而子树又由下层的若干棵子树构成。第一节树南昌大学第4/209页二、树常见的表示形式如图10-1所示，本章主要采用的是自然表示法。第一节树南昌大学第5/209页三、树的有关名词(1)节点的度:节点的孩子数称为节点的度。(2)树的度（树的叉）：树中最大的节点度为该树的度。(3)叶子节点（终端节点）：度为0的节点（1个孩子都没有）称为叶子节点。(4)双亲节点：节点的父亲节点。(5)树的高度（深度）：树的层数（根为第1层）为树的高度。第一节树ABECFDGHJI南昌大学第6/209页一、定义二叉树是一种重要的树形结构，它的特点是：二叉树可以为空（节点个数为0），任何一个节点的度都小于或等于2，并且，子树有左、右之分，其次序不能任意颠倒。二叉树有5种基本形态，如图10-2所示。第二节二叉树南昌大学第7/209页第二节二叉树从树的角度来看它们是同一棵树，从二叉树角度来看它们是不同的两个二叉树。南昌大学第8/209页例10-1试写出具有3个节点的所有不同形态的树和二叉树。第二节二叉树南昌大学第9/209页三、二叉树的性质二叉树具有以下重要的性质。性质1：二叉树第i(i=1)层上最多有2i-1个节点。性质2：深度为k的二叉树最多有2k-1个节点。性质3：任意一棵二叉树中，若叶子节点个数为n0，度为2的节点个数为n2，则n0＝n2＋1。第二节二叉树南昌大学第10/209页下面介绍两种特殊的二叉树。(1)满二叉树指深度为k，且有2k-1个节点的二叉树。或者说除叶子节点外，其它节点的度都为2的二叉树。(2)完全二叉树一个满二叉树的最下层从右向左连续缺少n(n=0)个节点的二叉树。图10-3为满二叉树和完全二叉树示例。第二节二叉树南昌大学第11/209页可以看出：1)满二叉树一定是完全二叉树．它是完全二叉树的特例。2）完全二叉树不一定是满二叉树。3）满二叉树中n1=0;完全二叉树中n1=0或1。性质4：具有n个节点的完全二叉树的深度为└log2n┘＋1（符号└x┘表示取x的整数部分）第二节二叉树南昌大学第12/209页四、二叉树的存储结构二叉树的存储结构有顺序存储和链式存储两种。1、顺序存储结构（1）方法1)先将二叉树变成完全二叉树。（给有关节点补够两个孩子，所补节点为虚拟节点，仅占个空间）。2)将这个完全二叉树中各节点从上到下，逐层从左向右依次存放到计算机连续空间中去。第二节二叉树南昌大学第13/209页例10-2写出图10-4a所示二叉树的顺序存储结构，并说明最少需要多少个存储空间。第二节二叉树南昌大学第14/209页说明：①上述完全二叉树，按编号依次存储在一维数组s[0..n]中，其中s[l..n]用来存放各节点。为符合人们的计数习惯，s[0]可以不用，或者用来存放二叉树节点个数。②计算二叉树节点顺序存储最少需要多少个空间，不含s[0]，本题最少需13个存储空间。③图10-4b中的口代表空节点（虚拟节点），仅占个位置。第二节二叉树南昌大学第15/209页例10-3一个深度为K且只有K个节点的二叉树顺序存储最多需要多少个存储空间，最少需要多少个。解：为解题方便，假设K=4。1)最坏情况的树形为右单支树，可看出要变成一个完全二叉树必须为满二叉树，如图10-5所示。最多需2k一1个存储空间。2)最好情况的树形为左单支树变成完全二叉树，如图10-6所示。其节点个数为深度为K一1的满二叉树节点个数加1，所以，最少需2k-1个存储空间。第二节二叉树南昌大学第16/209页由以上分析可以看出，完全二叉树和满二叉树顺序存储是不浪费空间的。第二节二叉树南昌大学第17/209页(2)完全二叉树节点顺序编号的意义1)编号方法如图10-7所示。2)编号的意义：在顺序存储下根据一个节点的位置可以很方便地求出它的双亲及孩子的地址。假设节点编号为i，则有：①第i号节点的地址=第一个节点地址+(i-1)*d(d为节点所占字节数）。②i=1时为根节点，无双亲节点。③i＞1时，该节点的双亲节点编号为└i/2┘。如编号为8和9的节点，其双亲编号为4。④若2i=n，则第i号节点的左孩子编号为2i;否则无左孩子。第二节二叉树南昌大学第18/209页⑤若2i+1=n，则第i号节点的右孩子编号为2i＋1;否则无右孩子。第二节二叉树南昌大学第19/209页例10-4一个完全二叉树节点个数为1000，则n0、n1、n2和高度h各为多少？解：1）第1000号节点的双亲编号为[1000/2]=500，即说明：1000是500的左孩子。2)完全二叉树的n1只有0和1两个值，根据完全二叉树节点顺序编号的意义可知：n1=1（500号节点只有1个孩子）。3)500号节点前面的所有节点都有两个孩子，所以n2=499。4）500号节点后面的节点都没有孩子，所以n0＝500。5)假设该完全二叉树为满二叉树，则有2h-1=1000，得h=10。注意：1）29=512、210=1024是计算机中特殊的数，应记住。2）凡是完全二叉树的有些问题，应联想到能否用完全二叉树节点顺序编号来解决。第二节二叉树南昌大学第20/209页2.链式存储结构1)二叉树链式存储中每个节点含3个成员（域）。第二节二叉树其中：Lchild存放节点左孩子的地址(左链)；rchild存放节点右孩子的地址(右链)；data节点的数据域。2)二叉树链式存储类型的定义：structnode{datatypedata；structnode*Lchild,*rchild：}；南昌大学第21/209页例10-5写出图10-8a所示二叉树的链式存储结构。其链式结构如图10-8b所示。可以看出：具有n个节点的二叉树链式存储共有2n个链，其中只有n-1个用来存放该节点的左、右孩子，其余的n+1个指针域为空。第二节二叉树南昌大学第22/209页二叉树的遍历就是访问二叉树各个节点的过程。对二叉树的各种运算，首先要找到各个节点，这是二叉树运算的基础。本节只讨论二叉树的3种基本遍历方法：先序遍历、后序遍历和中序遍历。二叉树的3种遍历方法很有规律性，下面以二叉树的中序遍历为例讨论二叉树的3种遍历方法。第三节二叉树的遍历南昌大学第23/209页一、二叉树的中序（中根）遍历1．定义若二叉树非空，则：1)先：中序遍历左子树。2)再：访问根节点。3）最后：中序遍历右子树。注意：1)二叉树的遍历是一个递归过程。2)左、右子树为遍历，根节点为访问。3)中序遍历的过程是不断执行左、根、右的过程。二叉树中每一个节点都可以看作根，左、右子树是相对于根节点而言。4）遍历是按图10-9所示二叉树的基本组成结构进行的。第三节二叉树的遍历南昌大学第24/209页2.举例写出图10-10a所示二叉树中序遍历结果。第三节二叉树的遍历可以看出，图10-10a所示二叉树的中序遍历结果序列为：DBGEHACIF。南昌大学第25/209页3.二叉树中序遍历的算法(1)递归算法voidt11（structnode＊p）{if(p!=NULL){t11(p-Lchild)；／＊中序遍历左子树＊／printf(“%c”,p-data)；／＊访问根节点＊／t11(p-rchild)：／＊中序遍历右子树＊／}}第三节二叉树的遍历南昌大学第26/209页例10-6已知一个二叉树的中序遍历结果为abc，写出二叉树。解：共有5种二叉树，如图10-13所示。第三节二叉树的遍历南昌大学第27/209页二、二叉树的先序（先根）遍历二叉树先序遍历的定义是：1)先：访问根节点。2)再：先序遍历左子树。3)最后：先序遍历右子树。图10-10a所示先序遍历结果序列为：ABDEGHCFI。第三节二叉树的遍历南昌大学第28/209页三、二叉树的后序（后根）遍历二叉树后序遍历的定义是：1)先：后序遍历左子树。2）再；后序遍历右子树。3）最后：访问根节点。图10-10a所示二叉树的后序遍历结果序列为：DGHEBIFCA。第三节二叉树的遍历南昌大学第29/209页通过上面3种遍历的讨论，可以看出3种遍历的路线完全相同，就是根节点访问的顺序不同。总结1：已知一个二叉树的先序和中序或后序和中序遍历结果可以唯一地确定一裸二叉树。具体方法如下：1)根据先序或后序结果确定二叉树各层的根（先序根在前面，后序根在后面）。2)根据中序确定各层根的左、右子树（位置是：左、根、右）。反复作1）、2）即可。第三节二叉树的遍历南昌大学第30/209页例10一已知一个二叉树的后序遍历结果和中序遍历结果分别为：DGHEBIFCA和DBGEHACIF，试确定这个二叉树。解：第一步：由后序遍历结果确定整个二叉树根为A，由中序结果确定A的左、右子树。后序遍历结果：第三节二叉树的遍历中序遍历结果：南昌大学第31/209页第二步：确定A的左子树。1)后序遍历结果：第三节二叉树的遍历中序遍历结果：2）确定B的右子树：①后序遍历结果：南昌大学第32/209页②中序遍历结果：第三节二叉树的遍历第三步：确定A的右子树。1)后序遍历结果：中序遍历结果：南昌大学第33/209页2)确定C的右子树：①后序遍历结果：第三节树的遍历②中序遍历结果：南昌大学第34/209页本节主要研究树的存储结构以及树、森林和二叉树的关系。一、树的存储结构前面介绍了二叉树的两种存储结构，能否用二叉树存储方法来存储树呢？结论是：浪费空间，不可行。为适应各种实际问题的需要，下面介绍树的3种存储结构。1．双亲静态链表存储法给定一个树，如图10-16a所示，它的静态链表存储结构如图10-16b所示。第四节树、森林与二叉树的关系南昌大学第35/209页第四节树、森林与二叉树的关系可以看出，树的双亲表示法是用一个一维数组来存储的，每个节点有两个成员（两个域）：数据域（data)和双亲域(parent)，节点结构如图10-16c所示。A节点无双亲，用-1表示，B、C、D的双亲就是一维数组中第0号节点即A，E、F的双亲就是一维数组中第2号节点即C。南昌大学第36/209页2.孩子链表存储法孩子链表存储结构由n个单链表组成，每个单链表包括两部分内容：表头节点和各表头节点的孩子节点。如图10-16a所示树的孩子链式存储结构可用图10-17描述。这种存储的特点是：沿着链可以很快找到各个节点的孩子。第四节树、森林与二叉树的关系南昌大学第37/209页3.孩子兄弟链式存储法这种存储方法的特点是：既可以通过链找到各节点的孩子，也可以找到孩子间的兄弟。步骤如下：1)先写出树的孩子兄弟表示法。具体是：用横线连接亲兄弟，竖线连接左孩子，断开和其他孩子的链线。（即，将一般树转化成二叉树）2)用链连接各节点。每个节点3个域，如下表示：第四节树、森林与二叉树的关系南昌大学第38/209页二、树与二叉树的关系1．树变二叉树（1）方法1)写出树的孩子兄弟表示。2）把横线变成右子树，竖线变成左子树（或者以树根为轴心，把孩子兄弟表示顺时针旋转45“）。图10-18d是图10-18a所示树变的二叉树。不难看出，树所变的二叉树的根节点没有右子树。(2)树的遍历树的遍历的基本方法有：先序、后序和按层3种。其先序和后序遍历方法和二叉树类似。第四节树、森林与二叉树的关系南昌大学第39/209页第四节树、森林与二叉树的关系南昌大学第40/209页注意：1)树的先序遍历结果和对应二叉树的先序遍历结果一样。图10-18中，结果均为ABCEFD。2)树的后序遍历结果和对应二叉树的中序遍历结果一样