数据结构课件第8章.ppt

第8章树与二叉树,8.1树的基本概念8.2二叉树8.3线索二叉树8.4排序二叉树8.5树与森林8.6哈夫曼树8.7实习八：二叉树遍历演示程序,8.1树的基本概念,8.1.1树的定义及应用树型结构的例子广泛存在于现实生活中。例如，图8.1(a)表示了一家的父子关系。其中，圆圈代表了家族中的某个人，圆圈之间的连线则反映了对应的人之间存在父子关系：李富贵有两个儿子李元盛和李元清，其中，李元盛又有三个儿子李明秀、李明英和李明杰。这种表示看上去就像一棵倒立的树，层次分明地反映了家族成员间的关系。同样，一个机构中的行政关系也可表示成树型结构，如图8.1(b)所示。其中，圆圈代表了机构中的各个部门，连线则反映了各部门间的领导与被领导关系。图8.1(b)表示的是某学校的行政建制。,图8.1树的例子,在这种树型的表示方法中，代表着某个实体的圆圈通常被称作结点，而在所有的结点中，会有一个处于最高层次的结点。在图8.1(a)中，代表李富贵的结点是处于最高层次的结点，因为李富贵是其他所有人的祖先；在图8.1(b)中，代表长沙大学的结点是处于最高层次的结点，因为它领导着所有其他结点所代表的机构。这个处于最高层次的结点通常被称为根结点，它就如同树的根一般，其他的所有结点均是以这个“根”为基础得到的，全部结点在一起就构成了一棵“树”。,例如，一个算术表达式也可以用树型结构来表示。运算符作为根结点，参与运算的两个运算对象分别作为根结点的左、右两棵子树。图8.1(c)所示的树表示的算术表达式可理解为ab+(c-d/e)f。作为一种数据结构，树的定义如下：树(tree)是n0个结点的有限集合。n0的树称为空树。在任何一棵非空树T中，有一个特定的结点tT，称为T的根结点；其余的结点T-t被分割成m0个不相交的有穷子集T1-Tm，其中每个这样的子集Ti(im)本身又是一棵树，称为根结点的子树。由此可见，树的定义是一个递归定义。,图8.2树的示意图,图8.2所示是一棵具有14个结点的树T=A，B，N。其中，A为T的根结点；其余结点T-A被分割成三个不相交的子集T1=B,E,F,K,L，T2=C,G,H,I,M，N，T3=D，J。T1、T2、T3都是T的子树。其中，T1的根结点为B，其余结点T-B又分为两个不相交的子集T11=E，T12=F,K,L，它们都是T1的子树。T12的根结点为F，并且包含两棵结点数为1的子树，T11的根结点为E，没有子树。,在一棵树中，一个结点被定义为其子树的根结点的父结点，而其子树的根结点就是它的子女结点。如在图8.2中，A为B、C、D的父结点，B、C、D则为A的子女结点；而B又为E和F的父结点。从定义可以看出，树结构具有以下特点：有且仅有根结点没有父结点；除根结点外，其余所有结点有且仅有一个父结点；包括根结点在内，每个结点可以有多个子女结点。总而言之，树的数据元素之间存在着一对多的关系。,8.1.2树的逻辑表示,1.树形表示法如图8.2所示，树形结构被形象地表示为一棵倒置的、树根在上、树叶在下的树。树的每个结点都用一个圆圈表示，圆圈内的符号代表该结中的数据，结点之间的关系通过连线表示。连线上方的结点为连线下方的结点的父结点，而连线下方的结点则为连线上方结点的子女结点。这种表示方法形象、直观，大多数书中都采用这种方法。,2.文氏图表示法文氏图表示法也称集合图表示法，其中每一个圆形对应着一棵树，圆内包含根结点和子树。图8.2所示的以B为根结点的子树为例，其文氏图表示法如图8.3(a)所示。,图8.3树的逻辑表示方法(a)文氏图表示法；(b)凹入表示法；(c)嵌套括号表示法,3.凹入表示法凹入表示法中的每个条形对应着一个树根，子树的树根对应的条形较短，并在其直接前驱对应的条形之下，图8.3(a)所示的子树若采用凹入表示法，则如图8.3(b)所示。4.嵌套括号表示法嵌套括号表示法也称为广义表表示法，每棵树的根可作为由子树构成的表的名字，放在表的左边，如图8.3(c)所示。,8.1.3基本术语1.结点的度和树的度每个结点具有的子树数或者说后继结点数被定义为该结点的度(degree)。所有结点的度的最大值被定义为该树的度。如在图8.2的树T中，B、F、H结点的度为2，A、C结点的度均为3，D结点的度为1，其余结点的度均为0。因结点中度最大的为3，所以树T的度为3。,2.分支结点和叶结点度大于0的结点称作分支结点或非终端结点；度等于0的结点称作叶结点或终端结点。在分支结点中，又把度为1的结点叫做单分支结点，度为2的结点叫做双分支结点，以此类推。如在图8.2的树T中，A、B、C、D、F、H都是分支结点，E、K、L、G、M、N、I、J都是叶结点。在分支结点中，D为单分支结点，B、F、H分别为双分支结点，A、C为三分支结点。,3.儿子结点、双亲结点和兄弟结点每个结点的子树的根，或者说每个结点的后继，被习惯地称作该结点的儿子或孩子(child)，相应地，该结点被称作儿子结点的双亲。具有同一双亲的孩子互称兄弟(sibiling)。每个结点的所有子树中的结点被称作该结点的子孙。每个结点的祖先被定义为从树根结点到达该结点的路径上经过的所有结点。如在图8.2的树T中，B结点的孩子为E、F结点，双亲为A结点；E、F互为兄弟；B结点的子孙为E、F、K、L结点。I结点的祖先为A、C结点。对于树T中的其他结点亦可进行同样的分析。由孩子结点和双亲结点的定义及树结构的特点可知：在一棵树中，根结点没有双亲结点，叶结点没有儿子结点。如在图8.2的树T中，A结点没有双亲结点，E、K、L等结点没有儿子结点。,4.结点的层数和树的高度树既是一种递归结构，也是一种层次结构。树中的每个结点都处在一定的层次上。结点的层数(level)从树根开始定义，根结点为第一层，它的孩子结点为第二层，以此类推。树中结点的最大层数称为树的深度(depth)或高度(height)。如在图8.2的树T中，A结点处于第一层，B、C、D结点处于第二层，E、F、G、H、I、J结点处于第三层，K、L、M、N结点处于第四层。K、L、M、N结点所处的第四层为树T中结点的最大层数，所以树T的高度为4。,5.有序树和无序树若树中各结点的子树是按照一定的次序从左向右安排的，则称之为有序树，否则称之为无序树。如图8.4中的两棵树，若看作无序树，则是相同的；但若看作有序树，则不同。因为根结点A的两棵子树的次序不同。又如，对于一棵反映父子关系的家族树，若兄弟结点之间是按照排行大小有序的，则它是一棵有序树。,图8.4两棵不同的有序树,6.森林森林是m(m0)棵互不相交的树的集合。例如，对于树中每个分支结点来说，其子树的集合就是森林。如图8.2的树T中，由A结点的子树所构成的森林为T1,T2,T3，由B结点的子树所构成的森林为T11,T12。,8.1.4树的基本操作设T为一棵树，则T的基本操作主要有以下几种：(1)initiate()：初始化操作，置T为空树。(2)parent(x)：求树T中结点x的双亲结点。(3)child(x,i)：求树T中结点x的第i个孩子结点。(4)right-sibling(x)：求树T中结点x右边的兄弟结点。(5)insert-child(y,i,x)：在T中插入以结点x为根的树作为结点y的第i个子树。(6)del-child(x,i)：在T中删除结点x的第i棵子树。(7)traverse()：遍历操作。按某个次序依次访问树T中各结点。,8.2二叉树,8.2.1定义二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树。二叉树的特点是每个结点最多只有两个子女。即，在二叉树中，不存在度大于2的结点。二叉树的子树有左右之分，左右子树的顺序不能颠倒。因此，根据该定义，二叉树有如图8.5所示的五种基本形态。其中，（a）为空二叉树，（b）为只有一个根结点的二叉树，（c）为只有左子树的二叉树，（d）为只有右子树的二叉树，（e）为左、右子树均为非空的二叉树。,图8.5二叉树的基本形态,8.2.2基本性质二叉树有一些特殊的性质，简单归纳如下：(1)任意非空二叉树中，若叶结点的数目为n0，度为2的结点数目为n2，则有关系：n0=n2+1证明：设度为1的结点数目为n1，则二叉树的结点总数n为n=n0+n1+n2,由于二叉树中除根结点以外，每个结点都有一个分支指向它，因此二叉树中总的分支数Z为Z=n-1所有这些分支均是由度为1或的2的结点发出的，而每个度为1的结点发出一个分支，每个度为2的结点发出两个分支。于是有Z=n1+2n2由以上三式可推得：n0=n2+1,(2)一棵非空二叉树的第i层最多有2i-1个结点(i1)。该性质可用归纳法证明：当i=1时，二叉树只有一个结点，即二叉树的根结点。显然性质(1)成立。假设对所有k(1ki-1)性质(1)成立，即第k层上最多有2k-1个结点。面证明当k=i时性质（2）也成立。根据归纳假设，第i-1层上最多有2i-2个结点，又由于每个结点最多有2棵子树，所以第i层的结点数目最多是第i-1层上最大结点数目的2倍，即有22i-2=2i-1。性质（2）得证。,(3)高度为k的二叉树最多有2k-1个结点(k1)。显然，高度为k的二叉树只有在每一层都达到最大结点数时，整个二叉树的结点数才能达到最大。即当每层的结点数目都达到该层的最大结点数2i-1时（性质(2)），对应的二叉树的结点数目取得最大值：,故性质(3)得证。若一棵二叉树高度为k且有2k-1个结点，则称该二叉树为满二叉树。满二叉树的特点就是每层的结点数目都达到该层的最大结点数。图8.6(a)所示的是一棵高度为4的满二叉树。,图8.6满二叉树与完全二叉树(a)满二叉树；(b)完全二叉树,若在一棵二叉树中，除最后一层外，其余层都是满的（结点数目达到该层的最大结点数），并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则称此树为完全二叉树。满二叉树是完全二叉树的特例。图8.6(b)为一棵高度为4的完全二叉树，与等高度的满二叉树相比，它在最后一层的右边缺少了5个结点。由图8.6还可看出，对于一棵完全二叉树，若按照高度相同的满二叉树的同样方法对其结点进行编号，则其每个结点的编号都与满二叉树的结点编号相同。完全二叉树有如下特点：叶结点仅在层数最大的两层上出现；对其中任意结点，若右子树的高度为kr，则左子树的高度为kr或kr+1。完全二叉树有(4)、(5)两个重要性质：,(4)具有n0个结点的完全二叉树的高度k=log2n+1。符号表示取不超过符号内的数字的最大的整数。性质(4)证明如下：根据完全二叉树定义以及二叉树的性质(3)，有2k-11n2k1或2k-1nn，则序号为i的结点无左孩子。若2i1n，则序号为i的结点的右孩子结点的序号为2i+1；若2i+1n，则序号为i的结点无右孩子。该性质可采用归纳法证明，此处从略。通过具体实例也可以验证性质（5）的正确性。,8.2.3存储结构,1.数组表示当在数据处理过程中，二叉树的大小和形态不发生大的变化时，可以采用数组方式来表示二叉树的抽象数据类型。使用数组方式存储二叉树结构，就是用一组连续的存储单元存储二叉树的数据元素。为了反映各结点在二叉树中的位置及相互关系，必须适当安排各结点的存储次序。设有一棵完全二叉树，对它所有的结点按照层次次序自顶向下，同一层自左向右顺序编号1,n，就得到一个结点的顺序（线性）序列。按这个线性序列，可把这棵完全二叉树放在一个一维数组中，如图8.7(a)所示。,图8.7二叉树的数组表示(a)完全二叉树；(b)一般二叉树,设有一棵一般的二叉树，需要将它存放在一个一维数组中。为了能够简单地找到二叉树中任意一个结点的上下左右的关系，必须仿照满二叉树的编号方式对其结点进行编号，然后按编号存放到向量中去，如图8.7(b)所示。编号时，如遇到空子树，应在编号时假定有此子树进行编号，而在顺序存储时当作有此子树那样把位置留出来。这样才能反映二叉树结点之间的相互关系，并由其存储位置找到它的双亲、儿子、兄弟结点的位置，但是，这样做有可能会消耗大量的存储空间。例如，图8.7(b)给出的高度为4的二叉树，按照这种方式存储时，要求一个可存放15个结点的一维数组，但其结点数只有8个。除此之外，采用数组顺序地存储二叉树将会使二叉树插入、删除操作的实现变得十分不方便。因此，对于二叉树来说，更合适的还是采用链式存储方式。,2.链式存储结构二叉树的链式存储结构是指用一个链表来表示一棵二叉树。通常有下面两种形式。1)二叉链结构在二叉链结构中，链表的每个链结点由三个域组成。除了数据域data用来存结点的数据信息外，还有两个指针域lchild与rchild分别用来存放指向该结点左子树与右子树的指针，如图8.8(a)所示。,图8.8二叉树链式存储链结点构造(a)二叉链表；(b)三叉链表,(a),(b),图8.9二叉树及其链表表示(a)二叉树；(b)二叉链表；(c)三叉链表,当左子树或右子树不存在时，相应的指针域值为空（用符号或nil表示）。图8.9(b)为图8.9(a)二叉树的二叉链表示。我们可以给出二叉链表链结点数据类型描述如下：typeTlink=Tnode;Tnode=recorddata:elemtp;lchild,rchild:Tlink;end;,其中，Tnode为二叉链表链结点类型名，Tlink为指向链结点的指针类型，elemtp为结点数据的类型。那么，如何根据输入的数据来建立二叉链表呢？我们可以采取以下的方法：首先建立二叉树根结点所对应的链结点，然后再从这个链结点出发，分别建立根结点的左子树与右子树。假设二叉树结点数据按照类似图8.7(b)的方式存储在一个数组中，则我们首先创建一个链结点，在其数据域中存放数组中的第一个元素，这样就建立了二叉树的根结点；接下来，需要分别建立根结点的左子树与右子树，而建立子树又必须先建立子树的根结点。显然，这个过程可以用递归过程来描述。,设二叉树结点数据类型为字符型，各结点数据按照二叉树的数组表示方式存储在字符串str中，字符串变量为s:string、整型变量为n:integer及指针为root:Tlink，它们已在外部说明，则二叉链表的建立过程可表示为procedurebuild(str:string)；其功能为根据字符串str的内容建立二叉树的二叉链表，并让root指向这个二叉链表。其处理过程为：以1为参数调用递归子函数functionbuild0(i:integer):Tlink完成二叉链表的建立，并让root指向该链表。递归子函数functionbuild0(i:integer):Tlink的功能为：以字符串str的第i个元素为二叉树的根结点递归地建立二叉链表，并返回指向该链表的指针。其处理过程为：,(1)若i小于字符串的长度，且字符串的第i个元素为非空格符，则创建一个链结点，在其数据域中存放字符串的第i个元素；(2)以2*i为参数，调用build0建立这个结点的左子树；(3)以2*i+1为参数，调用build0建立这个结点的右子树。这里用到了二叉树的性质(5)。即n个结点的完全二叉树按层次从上到下，同一层中从左至右的规则对结点编号时，序号为i的结点若有左子树结点，则其结点序号为2i；若有右子树结点，则其结点序号为2i1。由于二叉树的数组表示采取了与完全二叉树相同的标号规则，故通过父结点的序号可推出儿子结点的序号。以下是程序清单：,procedurebuild(str:string);根据str中的内容建立二叉链表begins:=str;n:=length(s);root:=build0(1);调用递归子过程end;functionbuild0(i:integer):Tlink;以字符串str中第i个元素为varp:Tlink;l,r:integer;二叉树的根结点建立二叉链表,beginif(i)thenbeginnew(p);p.data:=si;l:=2*i;r:=2*i+1;p.lchild:=build0(l);p.rchild:=build0(r);result:=p;endelseresult:=nil;end;,2)三叉链结构使用二叉链表这种存储结构，可以很方便地根据结点指针lchild与rchild找到二叉树中结点的左孩子与右孩子，但要找到它的双亲却不太方便。为了便于查找任一结点的双亲结点，可以在二叉链表链结点中再增加一个双亲指针域，如图8.8(b)所示。这种链表被称为三叉链表，图8.9(c)为图8.9(a)二叉树的三叉链表示。类似地，我们给出三叉链表链结点数据类型描述如下：typeTlink=Tnode;Tnode=recorddata:elemtp;parent,lchild,rchild:Tlink;end;,8.2.4二叉树的遍历二叉树的遍历是指按照一定次序访问树中所有结点，并且每个结点仅被访问一次的过程。所谓访问某结点可以理解为打印该结点的数据信息。但在实际处理过程中，访问某个结点并不一定就是如此。例如，修改结点的数据，或者判断结点是不是满足条件的结点等都可认为是对结点的访问。,根据二叉树的递归定义，一棵非空二叉树由根结点、左子树和右子树组成，因此，遍历一棵非空二叉树的问题可分解为三个子问题，即访问根结点、遍历左子树和遍历右子树。若分别用D、L和R表示上述三个子问题，则有DLR、LDR、LRD、DRL、RDL、RLD六种次序的遍历方案。其中前三种方案都是先遍历左子树，后遍历右子树，而后三种则相反，都是先遍历右子树，后遍历左子树。由于两者对称，故我们只讨论前三种次序的遍历方案。,在遍历方案DLR中，因为访问根结点的操作在遍历左、右子树之前，故称之为前序遍历(preorder)或先根遍历。类似地，在LDR方案中，访问根结点的操作在遍历左子树之后和遍历右子树之前，故称之为中序(inorder)遍历或中根遍历;在LRD方案中，访问根结点的操作在遍历左、右子树之后，故称之为后序(postorder)遍历或后根遍历。显然，遍历左、右子树的问题仍然是遍历二叉树的问题，所以二叉树的这三种遍历方式可以用递归算法实现。,1.递归算法1)中序遍历(LDR)中序遍历的过程是，若二叉树不为空，则(1)以中序遍历方式遍历根结点的左子树；(2)访问根结点；(3)以中序遍历方式遍历根结点的右子树。,因此，中序遍历过程可用递归算法描述。设p为指向二叉树根结点的指针，则中序遍历过程可表示为procedureinorder0(p:Tlink)，其功能为对p所指的二叉树进行中序遍历，输出中序遍历的结点序列，其处理过程为：若p非空，则(1)中序遍历p所指结点的左子树；(2)显示p所指的结点数据；(3)中序遍历p所指结点的右子树。,这里过程名以0结尾是为了区别下面相同功能的非递归过程。以下为程序清单：procedureinorder0(p:Tlink);中序遍历以p为根结点的二叉树beginifpnilthenbegininorder0(p.lchild);中序遍历p的左子树显示p.data;访问p所指的根结点数据inorder0(p.rchild);中序遍历p的右子树end;end;,图8.10表达式语法树,图8.11二叉树中序遍历递归执行过程,2)前序遍历(DLR)二叉树前序遍历的过程是，若二叉树不为空，则(1)访问根结点；(2)以前序遍历方式遍历根结点的左子树；(3)以前序遍历方式遍历根结点的右子树。设p为指向二叉树根结点的指针，则前序遍历过程可表示为procedurepreorder0(p:Tlink)，其功能为对p所指的二叉树进行前序遍历，输出前序遍历的结点序列，其处理过程为：,若p非空，则显示p所指的结点数据；前序遍历p所指结点的左子树；前序遍历p所指结点的右子树。,以下为程序清单：procedurepreorder0(p:Tlink);前序遍历以p为根结点的二叉树beginifpnilthenbegin显示p.data;访问p所指的根结点数据preorder0(p.lchild);前序遍历p的左子树preorder0(p.rchild);前序遍历p的右子树end;end;,3)后序遍历(LRD)后序遍历的过程是，若二叉树不为空，则(1)以后序遍历方式遍历根结点的左子树；(2)以后序遍历方式遍历根结点的右子树；(3)访问根结点。,设p为指向二叉树根结点的指针，则后序遍历过程可表示为procedurepostoder0(p:Tlink)，其功能为对p所指的二叉树进行后序遍历，输出后序遍历的结点序列，其处理过程为：若p非空，则后序遍历p所指二叉树的左子树；后序遍历p所指二叉树的右子树；显示p所指的结点数据。,以下为程序清单：procedurepostorder0(p:Tlink);后序遍历以p为根结点的二叉树beginifpnilthendobeginpostorder0(p.lchild);后序遍历p的左子树postorder0(p.rchild);后序遍历p的右子树显示p.data;访问p所指的根结点数据end;end;,对于图8.10所示的二叉树，按后序遍历方式得到的表达式为ab*c。这种由后序遍历所得的表达式被称为后缀表达式，也常被称为逆波兰式。从上面给出的三种不同次序的遍历二叉树的递归算法可知，它们只是访问根结点及遍历左子树、遍历右子树的先后次序不同。如果把访问根结点这个不涉及递归的语句抛开，则三个递归算法走过的路线是一样的。图8.12给出了递归遍历时走过的路线，其中，向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出。,图8.12遍历的递归执行路线,三种递归遍历算法的差别在于：前序遍历是每进入一层递归调用时先访问根结点，然后再依次向它的左、右子树执行递归调用；中序遍历是在执行完左子树递归调用后再访问根结点，然后向它的右子树递归调用；后序遍历则是在从右子树递归调用退出后访问根结点。,2.非递归算法以上给出了二叉树遍历的递归算法。递归算法形式简洁，可读性好，而且其正确性容易得到证明。因此，利用递归算法可以给程序的编制和调试带来很大的方便。然而，递归调用比非递归调用消耗的时间与存储空间多，运行的效率较低。实际上，所有的递归算法都可转化成相应的非递归算法。一般说来，将递归算法改成相应的非递归算法需要一个栈来记录调用返回的路径。通过分析递归调用的执行过程，并观察栈的变化就可得到相应的非递归算法。,利用中序遍历的递归算法研究图8.12所示的二叉树可知，最先访问的结点是沿二叉链的左子树链往下走的最后一个结点。在走向这个结点的过程中，沿途经过的结点必须被压入栈中储存起来。在访问完该结点后，位于栈顶的元素正好是其双亲结点。将这个双亲结点从栈退出后，对其进行访问，然后再向其右子树方向走。若该右子树非空，则又重复这一过程。因此，为实现二叉树的中序遍历，非递归算法中设立了一个栈s来记录遍历返回的路径。s被说明成一个顺序栈对象s:Tsxz，顺序栈的类定义已在第2章中给出，其中，顺序栈中存储的元素为指向二叉链结点的指针：,typesqstktp=recordelem:array1.maxofTlink;top:0.max;end;,设二叉树的根结点由指针p:Tlink指示，栈s:Tsxz已在过程外部被说明并被初始化，则非递归中序遍历二叉树的过程可表示为procedureinorder(p:Tlink)，其功能为对p所指的二叉树进行非递归的中序遍历，输出中序遍历的结点序列，其处理过程为：(1)当p非空时，将p所指结点的地址进栈，并将p指向该结点的左子树；(2)当p为空时，弹出栈顶元素，显示其结点数据，并将p指向该结点的右子树；(3)重复过程(1)、(2)，直至栈空且p也为空。,以下是程序清单：procedureinorder(p:Tlink);非递归中序遍历以p为根结点的二叉树beginifpnilthendobegins.makeempty;栈清空while(pnil)and(s.empty=false)dobeginwhilepnildo,begins.push(p);将p所指的结点压入栈p:=p.lchild;将p指向左子树end;p:=s.pop;取栈顶元素显示p.data;访问p所指的结点数据p:=p.rchild;end;end;end;,图8.13非递归中序遍历二叉树时栈s状态的变化,二叉树的前序遍历、中序遍历与后序遍历是最常用的三种遍历方式，除此之外，有时也使用按层次的遍历方式。这种遍历方式是先遍历二叉树第一层的结点，然后遍历第二层的结点，最后遍历最下一层的结点；对每一层的遍历又按照从左至右的先后顺序进行。图8.14显示了按层次序遍历时的结点访问次序。层次序遍历不是一个递归过程，其算法的实现可参照第9章中有关图的广度优先搜索遍历的算法。,图8.14层次序遍历的结点访问顺序,3.二叉树遍历的应用,1)计算二叉树结点个数为了计算二叉树的结点个数，可以遍历根结点的左子树和右子树，分别计算出左子树和右子树的结点个数，然后把访问根结点的语句改为相加语句：二叉树根结点左子树结点个数加上右子树结点个数，再加上根结点数1，便得到整个二叉树的结点个数。设p:Tlink为指向二叉树根结点的指针，则二叉树结点个数的计算可表示为函数functionnode-number(p:Tlink):integer，其功能为返回以p所指二叉树的结点个数，其处理过程为：,(1)求p所指二叉树左子树的结点个数n1；(2)求p所指二叉树右子树的结点个数n2；(3)返回n1+n2+1。,程序清单如下：functionnode-number(p:Tlink):integer;beginifp=nilthenresult:=0elseresult:=node-number(p.lchild)+node-number(p.rchild)+1;end;,2)计算二叉树的高度如果二叉树为空，则高度为0；否则先递归计算根结点左子树的高度和右子树的高度，再求出两者中的最大者，并加1（增加根结点时高度加1），便得到整个二叉树的高度。设p:Tlink为指向二叉树根结点的指针，则二叉树高度的计算可表示为函数functiondepth(p:Tlink):integer，其功能为返回以p所指二叉树的高度，其处理过程为：(1)求p所指二叉树左子树的高度l1；(2)求p所指二叉树右子树的高度l2；(3)返回max(l1+l2)+1。,程序清单如下：functiondepth(p:Tlink):integer;beginifp=nilthenresult:=0elseresult:=max(depth(p.lchild),depth(p.rchild)+1;end;,3)判断两个二叉树相等利用二叉树的前序遍历，可实现判断两个二叉树是否相等的算法：首先比较两个二叉树根结点中的数据（相当于访问根结点），然后再比较左子树和右子树（依次访问左子树与右子树）。若均相同，则两个二叉树相等。设p,t:Tlink分别为指向两个二叉树的指针，则两个二叉树相等的判断可表示为函数functionequal(p,t:Tlink):boolean，其功能为判断p、t所指的二叉树是否相等。,若相等，则返回true，否则返回false，其处理过程为：(1)若p、t均为空，则返回true；(2)若p、t均非空，且结点数据和左右子树均相等，则返回true；(3)否则返回false。,程序清单如下：functionequal(p,t:Tlink):boolean;beginif(a=nil)and(t=nil)thenresult:=trueelseif(anil)and(tnil)and(a.data=b.data)and(equal(a.lchild,t.lchild)and(equal(a.rchild,t.rchild)thenresult:=trueelseresult:=false;end;,8.2.5二叉树的类定义根据二叉树的特点及有关树的基本操作，我们可以给出以二叉链表为存储结构的二叉树类定义如下：,typeTnode=classprivatedata:char;lchild,rchild:Tnodeend;Trcs=class,privates:string;s用作建立二叉树的输入n:integer;n为二叉树的结点个数root:Tnode;root为二叉树的根结点指针functionbuild0(i:integer):Tnode;私有建树函数procedurepreorder0(p:Tnode);私有前序遍历过程,publicprocedurebuild(str:string);根据字符串str的内容建立二叉树procedurepreorder;前序遍历二叉树procedureinorder;中序遍历二叉树procedurepostorder;后序遍历二叉树procedureprnt;显示二叉树end;ImplementationprocedureTrcs.preorder;,beginpreorder0(root);调用私有前序遍历过程end;procedureTrcs.inorder;begininorder0(root);调用私有中序遍历过程end;procedureTrcs.postorder;beginpostorder0(root);调用私有后序遍历过程end;,注意，在上述类定义中，我们将二叉树的结点也定义成类Tnode，因此结点的指针类型即为Tnode，生成时要使用Tnode.create，引用时也不必加“”符号。另外，在这个类定义中，同时设置了私有和公有遍历过程。公有遍历过程通过调用私有遍历过程向外界提供服务，隐藏了二叉树的私有数据root。过程build根据字符串str的内容建立的二叉树，建树和遍历的操作在前面已详细讨论过，二叉树的显示过程prnt可参见本章的演示程序。,8.3线索二叉树,8.3.1二叉树的线索化当以某种次序（前序、后序、中序）对二叉树进行遍历后，可得到一个树中所有结点组成的序列，这个结点序列可以被看作为一个线性表。在该线性表中，除第一个结点外，每个结点有且仅有一个前驱；除最后一个结点外，每个结点有且仅有一个后继。根据这个序列，可以找到二叉树中某一个结点在这种次序下的前驱和后继。在容易混淆的地方，还可以对序列中结点的前驱或后继冠以某种遍历次序的名称。如把中序序列中结点的前驱称作中序前驱，后继称作中序后继等。,如果我们希望很快找到某一结点在某种次序下的前驱或后继，但不想每次都对二叉树遍历一遍，那么就需要把每个结点的前驱和后继信息记录下来。比如，我们可在原来的二叉链表结点中增加一个前驱指针域(pre)和一个后继指针域(suc)，让它们分别指向该结点在某种次序下的前驱结点和后继结点。图8.15表示了加有中序前驱和后继指针域的二叉链表。通过前驱和后继指针域，可以很容易地查找任意一个结点的前驱和后继，而无需遍历二叉树。,图8.15增加了前驱和后继指针域的二叉链表,一般说来，在一棵非完全二叉树的二叉链结点中，许多儿子指针域中存放的是空指针。为了充分利用存储空间，我们可以用原有的空指针域来存放结点的前驱和后继指针。一般利用空的lchild域存放结点的前驱结点指针，而利用空的rchild域存放后继结点指针。这种在结点的空指针域中存放的该结点在某次遍历次序下的前驱结点或后继结点的指针叫做线索(thread)，其中在空的左指针域中存放的指向其前驱结点的指针叫做左线索，在空的右指针域中存放的指向其后继结点的指针叫做右线索。对一棵二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫做线索化，被线索化了的二叉树就称作线索二叉树。图8.16(a)就是对图8.15中的二叉树加中序线索而得到的中序线索二叉树。,图8.16线索二叉树及其链表表示,在线索二叉树中，为了区别线索和儿子指针，必须在每个链结点中设置两个标志域ltag和rtag。可以约定，当ltag(rtag)1时，则表明lchild(rchild)域中存放的是结点的左线索（右线索），否则即为指向结点左子树（右子树）的指针。与之对应的数据类型定义可表达如下：typethTlink=thTnode;thTnode=recorddata:elemtp;lchild,rchild:thTlink;ltag,rtag:0.1;end;,从图中可看出，有两个线索为空指针，即在遍历中第一个被访问的结点B的前驱线索和最后一个被访问的结点D的后继线索。为此，可引入一个头结点，并让原来的线索二叉树成为它的左子树。图8.17显示了与图8.16(b)对应的带头结点的线索二叉树的存储链表。,图8.17带头结点的线索二叉树的存储链表,8.3.2二叉树的线索化算法二叉树的线索化实际上就是将二叉链中的空指针改为指向结点前驱或后继的线索。前驱或后继的信息可在遍历二叉树时得到。因此，为对二叉树进行线索化，我们可对二叉树进行遍历，并在遇到的空指针域中，填入前驱或后继线索。设p:thTlink为指向二叉树根结点的指针，则二叉树的中序线索化可表示为函数functioncreate-inthread(p:thTlink):thTlink。其功能为对p所指的二叉树加上一个头结点，进行中序线索化后，返回该头结点的指针。其处理过程为：,(1)创建一个头结点；(2)若p为空，则令头结点的左右子树指针指向自己；(3)若p非空，则令头结点的左子树指针指向p，调用递归子过程inthread对二叉树进行线索化；(4)返回头结点指针。递归子过程procedureinthread(p:thTlink,varpre:thTlink)的功能为利用前驱指针pre对指针p所指的二叉树进行中序线索化。其中，前驱指针pre用来指示指针p所指的子树在中序序列中第一个结点的前驱。其处理过程为：,若p非空，则(1)中序线索化p所指结点的左子树；(2)若p所指结点无左子树，则建立前驱线索；若p所指结点无右子树，则建立后继线索；(3)中序线索化p所指结点的右子树。,以下是程序清单：functioncreate-inthread(p:thTlink):thTlink;加入头结点，对p线索化var并返回该头结点指针head,pre:thTlink;beginnew(head);new(pre);初始化head.ltag:=0;head.rtag:=0;ifp=nilthen若为空二叉树，则头结点的左右子树指针指向自己,beginhead.lchild:=head;head.rchild:=head;endelsebeginhead.lchild:=p;pre:=head;inthread(p,pre);否则对p进行线索化pre.rchild:=head;pre.rtag:=1;end;result:=head;end;,procedureinthread(p:thTlink,varpre:thTlink);beginifpnilthenbegininthread(p.lchild,pre);线索化左子树ifp.lchild=nilthenbegin建立前驱线索p.ltag:=1;p.lchild:=pre;end;,ifpre.rchild=nilthenbegin建立后继线索p.rtag:=1;p.rchild:=p;end;pre指向以p.rchild为根pre:=p;的子树的中序遍历序列的前驱inthread(p.rchild,pre);线索化右子树end;,8.3.3线索二叉树的应用1.查找前驱或后继这里所指的前驱或后继指的是在某种遍历次序下的前驱或后继。(1)在中序线索二叉树中查找存储地址为p的结点的前驱。在中序线索二叉树中查找存储地址为p的结点的前驱结点的规律为：当p.ltag=1时，p.lchild指出的结点就是p所指结点的直接前驱结点，如图8.18(a)所示；当p.ltag=0时，说明该结点有左子树，则它的中序前驱结点应该是以p.lchild为根的左子树中的最右下方的结点，如图8.19(b)所示。顺着左子树的根的右指针链往下找，直到某结点的rchild域是线索（rtag=1）为止，即可得到所求前驱结点。,图8.18中序线索二叉树中结点p的前驱(a)有前驱链；(b)无前驱链,图8.19中序线索二叉树中结点p的后继(a)有后继链；(b)无后继链,2.遍历设指针head:thTlink指向非空中序线索二叉树的头结点，则中序线索二叉树的遍历可表示为过程procedureinorder(head:thTlink)，其功能为对head所指的非空中序线索二叉树进行中序遍历，输出遍历的结点序列，其处理过程为：(1)访问线索二叉树在中序遍历下的第一个结点；(2)调用子函数inorder-suc确定当前结点在中序序列下的后继结点，并访问；(3)重复过程(2)，直至回到头结点。,子函数functioninorder-suc(p:thTlink):thTlink的功能为返回p所指结点的中序后继结点的指针，其处理过程为：(1)若p的右子树域为线索，则返回p的右子树指针；(2)否则从p的右子树的根结点开始，沿着左子树链往下走，返回第一个左子树域为线索的结点指针。,以下是程序清单：procedureinorder(head:thTlink);遍历头结点为head的非空中序线索二叉树varp:thTlink;beginp:=inorder-suc(head);先将p指向中序遍历下的第一个结点whilepheaddobegin显示p.data;访问结点数据p:=inorder-suc(p);将p指向当前结点的后继,end;end;functioninorder-suc(p:thTlink):thTlink;返回p的后继vars:thTlink;begins:=p.rchild;ifp.rtag=0thenwhiles.ltag=0dos:=s.lchild;result:=s;end;,8.4排序二叉树,8.4.1排序二叉树的定义排序二叉树或为空树或为满足具有以下特点的二叉树：（1）所有结点的（数据）值均不相同；（2）若左子树为非空，则左子树中所有结点的值均小于根结点的值；（3）若右子树为非空，则右子树中所有结点的值均大于根结点的值；（4）左子树和右子树均是排序二叉树。,图8.20排序二叉树的图示,8.4.2排序二叉树的操作1.求树中结点关键码的最值排序二叉树的结构使得求树中关键码的最大值或最小值变得相当简单：排序二叉树中从根结点开始沿左子树链往下走，所得最后一个结点的关键码一定是最小的；而沿右子树链往下走，所得最后一个结点的关键码一定是最大的。,设p:Tlink为指向排序二叉树根结点的指针，则求树中结点关键码的最小值可表示为函数functionmin(p:Tlink):elemtp，其功能为返回p所指排序二叉树中结点关键码的最小值，其处理过程为：若p为空，则显示出错，否则，(1)若p所指结点有左子树，则令p指向该结点；(2)重复(1)，直至p所指结点的左子树指针为空；(3)返回p所指结点的关键码。,以下是程序清单：functionmin(p:Tlink):elemtp;求以p所指结点为根的排序二叉树中begin关键码的最小值if(p=nil)thenshowmessage(error)elsebeginwhilep.lchildnildop:=p.lchild;result:=p.data;end;end;,类似地，可求得p所指排序二叉树中结点关键码最大值的函数：functionmax(p:Tlink):elemtp;求以p所指结点为根的排序二叉树中begin关键码的最大值if(p=nil)thenshowmessage(error)elsebeginwhilep.rchildnildop:=p.rchild;result:=p.data;end;end;,2.查找从排序二叉树的构造方法不难看到，在一棵排序二叉树中查找关键码等于指定值的结点是否存在，比在线性表中顺序查找的效率要高得多。其查找过程为：若二排序树根指针为空，则查找失败；否则，将给定值与排序二叉树的根结点关键码进行比较，若相等，则查找成功；否则，若根结点关键码大于给定值，则在左子树中继续查找；若根结点关键码小于给定值，则在右子树中继续查找，直到查找成功或者失败。整个查找过程可以用递归来描述。,设要查找的结点关键码由item:elemtp给出，p:Tlink为指向排序二叉树根结点的指针，则在排序二叉树中查找指定关键码可表示为函数functionfind(item:elemtp,p:Tlink):Tlink，其功能为：若在p所指的排序二叉树中存在关键码等于item的结点，则返回指向该结点的指针，否则返回空指针nil，其处理过程为：若p为空，则返回空指针nil，否则，(1)若p所指结点的关键码大于item，则在p所指结点的左子树中查找；(2)若p所指结点的关键码小于item，则在p所指结点的右子树中查找；(3)否则返回p。,以下是程序清单：functionfind(item:elemtp,p:Tlink):Tlink;beginifp=nilthenresult:=nilelseifp.dataitemthenresult:=find(item,p.lchild)elseifp.dataitemthenp:=p.lchildelseifp.dataitemthenremove(item,p.lchild)elseifp.dataitemthenremove(item,p.rchild)elseifp.lchild=nilthenp:=p.rchild只有右子树的情况,elseifp.rchild=nilthenp:=p.lchild只有左子树的情况elsebegin左右子树均存在的情况t:=min(p.rght-child);p.data