第6章树和二叉树

第6章树和二叉树6.1树6.1.1树的定义从数据结构角度看，树包含n（n≥0）个结点，当n=0时，称为空树；非空树的定义如下：

T=(D,R)其中，D为树中结点的有限集合，关系R满足以下条件：有且仅有一个结点k0∈D，它对于关系R来说没有前驱结点，结点k0称作树的根结点。除根结点k0外，D中的每个结点有且仅有一个前驱结点，但可以有多个后继结点。D中可以有多个终端结点。

【例6.1】有一棵树T1=(D,R)，其中D={A，B，C，D，E，F，G，H},

R={r}

r={<A,B>，<A,C>，<A,D>，<C,E>，<C,F>，<D,G>，<E,H>}画出其逻辑结构图。

解：该树中结点A没有前驱结点，它是树的根结点，该树的逻辑结构图如右图所示。在这棵树中，A是根结点，其余结点分成三个互不相交的子集：T1={B}，T2={C，E，F，H}，T3={D，G}。T1、T2、T3都是根结点A的子树，且各自本身也是一棵树。说明：树中结点之间的关系应为有向关系，在上图中，结点之间的连线即分支线都是有向的，默认箭头向下的。6.1.2树的逻辑结构表示树的逻辑结构表示：树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。文氏图表示法。使用集合以及集合的包含关系描述树结构。凹入表示法。使用线段的伸缩关系描述树结构。括号表示法。将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号分隔。6.1.3树的基本术语

1.结点的度与树的度：树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度，通常将度为m的树称为m次树。2.分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点。度为零的结点称为终端结点或叶结点。在分支结点中，每个结点的分支数就是该结点的度。如对于度为1的结点,其分支数为1，被称为单分支结点；对于度为2的结点，其分支数为2，被称为双分支结点，其余类推。ABCDEFGJHIKLM度为3度为2

3.路径与路径长度：对于任意两个结点di和dj，若树中存在一个结点序列di,di1,di2,…,din,dj，使得序列中除di外的任一结点都是其在序列中的前一个结点的后继，则称该结点序列为由di到dj的一条路径，用路径所通过的结点序列(di,di1,di2,…,dj)表示这条路径。

路径长度等于路径所通过的结点数目减1（即路径上分支数目）。ABCDEFGJHIKLMA到K的路径为A,D,I,K，其长度为3

4.孩子结点、双亲结点和兄弟结点：在一棵树中，每个结点的后继，被称作该结点的孩子结点（或子女结点）。相应地，该结点被称作孩子结点的双亲结点（或父母结点）。

具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系，可以把每个结点的所有子树中的结点称为该结点的子孙结点。

从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。ABCDEFGJHIKLM5.结点的层次和树的高度：树中的每个结点都处在一定的层次上。结点的层次从树根开始定义，根结点为第1层，它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度（或树的深度）。

ABCDEFGJHIKLM12346.森林：n（n＞0）个互不相交的树的集合称为森林。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给n棵独立的树加上一个结点，并把这n棵树作为该结点的子树，则森林就变成了树。6.1.4树的性质

性质1树中的结点数等于所有结点的度数加1。证明：根据树的定义，在一棵树中，除树根结点外，每个结点有且仅有一个前驱结点。也就是说，每个结点与指向它的一个分支一一对应，所以除树根之外的结点数等于所有结点的分支数（度数），从而可得树中的结点数等于所有结点的度数加1。度之和＝分支数分支数=n-1所以，n=度之和+1ABCDEFGJHIKLM性质2度为m的树中第i层上至多有mi-1个结点，这里应有i≥1。

证明（采用数学归纳法）

对于第一层,因为树中的第一层上只有一个结点，即整个树的根结点,而由i=1代入mi-1，得mi-1=m1-1=1，也同样得到只有一个结点，显然结论成立。假设对于第(i-1)层（i＞1）命题成立，即度为m的树中第(i-1)层上至多有mi-2个结点。则根据树的度的定义，度为m的树中每个结点至多有m个孩子结点，所以第i层上的结点数至多为第(i-1)层上结点数的m倍，即至多为mi-2×m=mi-1个，这与命题相同，故命题成立。

推广：当一棵m次树的第i层有mi-1个结点（i≥1）时，称该层是满的，若一棵m次树的所有叶子结点在同一层，除该层外其余每一层都是满的，称为满m次树。显然，满m次树是所有相同高度的m次树中结点总数最多的树。也可以说，对于n个结点，构造的m次树为满m次树或者接近满m次树，此时树的高度最小。性质3高度为h的m次树至多有个结点。证明：由树的性质2可知,第i层上最多结点数为mi-1（i=1,2,…,h），显然当高度为h的m次树（即度为m的树）上每一层都达到最多结点数时，整个m次树具有最多结点数，因此有：整个树的最多结点数=每一层最多结点数之和=m0+m1+m2+…+mh-1=。

【例6.1】若一棵三次树中度为3的结点为2个，度为2的结点为1个，度为1的结点为2个，则该三次树中总的结点个数和度为0的结点个数分别是多少？

解：设该三次树中总结点个数、度为0的结点个数、度为1的结点个数、度为2的结点个数和度为3的结点个数分别为n、n0、n1、n2和n3。显然，每个度为i的结点在所有结点的度数之和中贡献i个度。依题意有：n1=2，n2=1，n3=2。由树的性质1可知n=所有结点的度数之和+1=0×n0+1×n1+2×n2+3×n3+1=1×2+2×1+3×2+1=11又因为n=n0+n1+n2+n3即：n0=n-n1-n2-n3=11-2-1-2=6所以该三次树中总的结点个数和度为0的结点个数分别是11和6。6.1.5树的基本运算

树的运算主要分为三大类：第一类，寻找满足某种特定关系的结点，如寻找当前结点的双亲结点等；第二类，插入或删除某个结点，如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；第三类，遍历树中每个结点，这里着重介绍。

树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。有以下三种遍历方法：树的遍历先根遍历后根遍历层次遍历注意：先根和后根遍历算法都是递归的。先根遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。ABCDEFGHJIK先根遍历的顶点访问次序：ABEFCDGHIJK后根遍历的顶点访问次序：EFBCIJKHGDA层次遍历的顶点访问次序：ABCDEFGHIJK6.1.6树的存储结构1.双亲存储结构

这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。树的双亲存储结构示意图2.孩子链存储结构

孩子链存储结构可按树的度（即树中所有结点度的最大值）设计结点的孩子结点指针域个数。以下左图的树对应的孩子链存储结构如右图所示。树的孩子链存储结构示意图3.孩子兄弟链存储结构

孩子兄弟链存储结构是为每个结点设计三个域：一个数据元素域，一个该结点的第一个孩子结点指针域，一个该结点的下一个兄弟结点指针域。树的孩子兄弟链存储结构示意图6.2二叉树6.2.1二叉树的定义二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称做根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。

注意：二叉树与度为2的树是不同的。度为2的树至少有3个结点，而二叉树的结点数可以为0；度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。归纳起来，二叉树的5种形态如下图所示。

【例6.3】给出由3个结点A、B和C构成的所有形态的二叉树（不考察结点值的差异）。

解：含有3个结点A、B和C的所有形态的二叉树如下图所示。6.2.2二叉树性质

性质1非空二叉树上叶结点数等于双分支结点数加1。证明：设二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数n=n0+n1+n2。在一棵二叉树中，所有结点的分支数（即度数）应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n1+2n2。由于二叉树中除根结点以外，每个结点都有唯一的一个分支指向它，因此二叉树中有：总的分支数=总结点数-1。由上述三个等式可得：n1+2n2=n0+n1+n2-1即：n0=n2+1

【例6.4】一棵二叉树中总结点个数为200，其中单分支结点个数为19，求其叶子结点个数。

解：依题意，n=200，n1=19。又n=n0+n1+n2，由性质1得，n2=n0-1，所以有：n=2n0-1+n1，即n0=(n-n1+1)/2=91。所以这样的二叉树中叶子结点个数为91。

性质2非空二叉树上第i层上至多有2i-1个结点，这里应有i≥1。由树的性质2可推出。性质3高度为h的二叉树至多有2h-1个结点（h≥1）。由树的性质3可推出。

满二叉树：在一棵二叉树中，当第i层的结点数为2i-1个时，则称此层的结点数是满的，当一棵二叉树中的每一层都满时，则称此树为满二叉树。满二叉树具有这样的特性：除叶子结点以外的其他结点的度皆为2，且叶子结点在同一层上。由二叉树性质3可知，高度为h的满二叉树中的结点数为2h-1个。图(a)为一棵高度为4的满二叉树，其结点数为24-1=15。图中每个结点旁的编号是层序编号，即从根结点为1开始，按照层次从小到大、同一层从左到右的次序顺序编号。按这种方式可以对满二叉树的结点进行连续编号。

完全二叉树：在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则称此树为完全二叉树。由此可知，满二叉树是完全二叉树的特例。完全二叉树具有这样的特性：二叉树中至多只有最下边两层结点的度数小于2，且若二叉树中任意一个结点其右子树的高度若为h，则其左子树的高度只能是h或h+1。因此高度为h的完全二叉树若按层次从上到下、从左到右按自然数编号，它与高度为h的满二叉树中结点的编号一一对应。图(b)是一棵完全二叉树，它与等高度的满二叉树相比，在最后一层的右边缺少了3个结点。该树中每个结点上面的数字为该结点的编号，编号的方法同满二叉树。性质4对完全二叉树中编号为i的结点（1≤i≤n，n≥1，n为结点数）有：（1）若i≤n/2，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点。（2）若n为奇数，则每个分支结点都既有左孩子结点，也有右孩子结点；若n为偶数，则编号最大的分支结点只有左孩子结点，没有右孩子结点，其余分支结点都有左、右孩子结点。i/2i2i2i+1（3）若编号为i的结点有左孩子结点，则左孩子结点的编号为2i；若编号为i的结点有右孩子结点，则右孩子结点的编号为(2i+1)。（4）除树根结点外,若一个结点的编号为i，则它的双亲结点的编号为i/2，也就是说，当i为偶数时，其双亲结点的编号为i/2,它是双亲结点的左孩子结点，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子结点。

【例6.5】一棵完全二叉树中总结点个数为200，求其叶子结点个数。

解：依题意，n=200，由于n为偶数，所以n1=1。又n=n0+n1+n2，由性质1得，n2=n0-1，所以有：n=2n0-1+n1，n0=(n-n1+1)/2=100。这样的完全二叉树中叶子结点个数为100。6.2.3二叉树的存储结构1．顺序存储结构顺序存储一棵二叉树时，就是用一组连续的存储单元存放二叉树中的结点。由二叉树的性质4可知，对于完全二叉树和满二叉树，树中结点的编号可以唯一地反映出结点之间的逻辑关系，所以可以用一维数组按从上到下、从左到右的顺序存储树中所有结点值，通过数组元素的下标关系反映完全二叉树或满二叉树中结点之间的逻辑关系。一棵完全二叉树的顺序存储结构一般的二叉树的顺序存储结构设计：二叉树顺序存储结构的类型定义如下：typedefElemTypeSqBinTree[MaxSize];其中，ElemType为二叉树中结点的数据值类型，MaxSize为顺序表的最大长度。为了方便运算，通常将下标为0的位置空着，值为'#'的结点为空结点。显然，完全二叉树或满二叉树采用顺序存储结构比较合适，既能够最大可能地节省存储空间，又可以利用数组元素的下标确定结点在二叉树中的位置以及结点之间的关系。对于一般二叉树，如果它接近于完全二叉树形态，需要增加的空结点个数不多，也可采用顺序存储结构。如果需要增加很多空结点才能将一棵二叉树改造成为一棵完全二叉树，采用顺序存储结构会造成空间的大量浪费，这时不宜用顺序存储结构。2．二叉链存储结构对于一般的二叉树，通常采用二叉链表表示。链表中的每个结点包含两个指针，分别指向对应结点的左孩子和右孩子（注意在树的孩子兄弟链表存储结构中，每个结点的两个指针分别指向对应结点的第一个孩子和下一个兄弟）。在二叉树的链式存储中，结点的类型定义如下：typedefstructtnode{ElemTypedata; //数据域structtnode*lchild,*rchild; //指针域}BTNode;其中，data表示数据域，用于存储放入结点值（默认情况下为单个字母），lchild和rchild分别表示左指针域和右指针域，分别存储左孩子和右孩子结点（即左、右子树的根结点）的存储地址。当某结点不存在左或右孩子时，其lchild或rchild指针域取特殊值NULL。6.3递归算法设计方法6.3.1什么是递归在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身，称之为直接递归。若过程或函数p调用过程或函数q，而q又调用p，称之为间接递归。这里主要介绍直接递归。例如，有以下递归函数：对应的求解f(n)的递归算法fun()如下：f(1)=1f(2)=1f(n)=f(n-1)+f(n-2)n≥3intfun(inti){if(i==1||i==2) return(1);else return(fun(i-1)+fun(i-2));}计算fun(5)的过程如下图所示：递归树一般地，递归模型由两部分组成，一部分为递归出口，它给出了递归的终止条件，例如，前面例子中的f(1)=1和f(2)=1就是递归出口；另一部分为递归体，它确定递归求解时的递推关系，例如，前面例子中的f(n)=f(n-1)+f(n-2)就是递归体。

递归算法求解过程的特征是：先将不能直接求解的问题转换成若干个相似的小问题，通过分别求解各子问题，最后获得整个问题的解。当这些子问题不能直接求解时，还可以再将它们转换成若干个更小的子问题，如此反复进行，直到遇到递归出口为止。这种自上而下将问题分解、求解，再自上而下引用、合并，求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。6.3.2递归算法设计一般方法递归算法的设计方法是，先确定对应的递归模型，再将其转换为递归算法。其核心思想是把问题简化分解为几个子问题，其中子问题的形式和算法与原问题算法相似，只是比原来简化。递归算法设计的一般步骤如下：对原问题f(s)进行分析，假设出合理的“小问题”f(s')（与数学归纳法中假设n=k-1时等式成立相似）；假设f(s')是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s')之间的关系（与数学归纳法中求证n=k时等式成立的过程相似）；确定一个特定情况（如f(1)或f(0)）的解，由此作为递归出口（与数学归纳法中求证n=1或时n=0式成立相似）。

【例6.7】设计一个递归算法求一个整数数组中所有元素之和。

解：设f(i)为整数数组a中a[0]～a[i-1]这i个元素之和，这是原问题；小问题为f(i-1)，它为a[0]～a[i-2]这i-1个元素之和。假设f(i-1)已求出，显然有f(i)=f(i-1)+a[i-1]，另外，f[1]=a[0]。对应的递归模型如下：相应的递归算法如下：f(1)=a[0]f(i)=f(i-1)+a[i-1]intfun(inta[],inti){if(i==1)returna[0];elsereturn(fun(a,i-1)+a[i-1]);}

【例6.8】对于不带头结点的非空单链表L（结点类型用SLink表示），其结点值均为整数，设计以下递归算法：（1）求最大的结点值；（2）求最小的结点值；（3）正向输出所有结点值；（4）反向输出所有结点值。

解：（1）对于不带头结点的单链表L，L是第一个数据结点的指针，L->next也是一个不带头结点的单链表，它仅比单链表L少一个结点。设f1(L)计算单链表L中最大结点值，这是原问题，小问题为f1(L->next)计算以单链表L->next中最大结点值。假设f1(L->next)已计算出来，显然有f1(L)=max(L->data,f1(L->next))；当单链表L中只有一个结点时有：f1(L)=L->data。对应的递归模型如下：f1(L)=L->data 当L中只有一个结点时f1(L)=max(L->data,f1(L->next)) 其他情况intf1(SLink*L){intm;if(L->next==NULL)returnL->data;else{ m=f1(L->next); //递归求小问题的解 if(m>L->data)returnm; elsereturnL->data;}}（2）分析同（1）小题。对应的递归算法如下：intf2(SLink*L){intm;if(L->next==NULL) returnL->data;else{ m=f1(L->next); //递归求小问题的解 if(m<L->data)returnm; elsereturnL->data;}}（3）设f3(L)正向输出单链表L的所有结点值，这是原问题。小问题为f3(L->next)，它正向输出单链表L->next的所有结点值。假设f3(L->next)已输出，显然f3(L)等价于先输出L->data值，再调用f3(L->next))。当单链表L为空时，不做任何输出。对应的递归模型如下：f3(L)不做任何事情 当L==NULLf3(L)输出L->data;f3(L->next)) 其他情况voidf3(SLink*L){if(L!=NULL){ printf("%d",L->data); f3(L->next);}}其中“”表示等价关系。（4）分析同（3）小题。对应的递归算法如下：voidf4(SLink*L){if(L!=NULL){ f4(L->next); printf("%d",L->data);}}6.3.3二叉树的递归算法设计递归算法设计便是从递归数据结构的基本递归运算入手的。对于二叉树，以二叉链为存储结构，其基本递归运算就是求一个结点*p的左子树（p->lchild）和右子树（p->rchild），p->lchild和p->rchild一定是一棵二叉树（这是为什么二叉树的定义中空树也是二叉树的原因）。一般地，二叉树的递归结构如下图所示，对于二叉树b，设f(b)是求解的“大问题”，则f(b->lchild)和f(b->rchild)为“小问题”，假设f(b->lchild)和f(b->rchild)是可求的，在此基础上得出f(b)和f(b->lchild)、f(b->rchild)之间的关系，从而得到递归体，再考虑b=NULL或只有一个结点的特殊情况，从而得到递归出口。例如，假设二叉树中所有结点值为整数，采用二叉链存储结构，求该二叉树b中所有结点值之和。设f(b)为二叉树b中所有结点值之和，则f(b->lchild)和f(b->rchild)分别求根结点*b的左、右子树的所有结点值之和，显然有f(b)=b->data+f(b->lchild)+f(b->rchild)，当b=NULL时f(b)=0，从而得到以下递归模型：f(b)=0 当b=NULLf(b)=b->data+f(b->lchild)+f(b->rchild) 其他情况intfun(BTNode*b){if(b==NULL)return0;elsereturn(b->data+fun(b->lchild)+f(b->rchild));}6.4二叉树的基本运算算法6.4.1二叉树的基本运算一般地，二叉树有如下几个基本运算：CreateBTree(bt,str)：根据二叉树的括号表示法str建立二叉链存储结构bt。DestroyBTree(bt)：释放二叉树bt占用的内存空间。BTHeight(bt)：求一棵二叉树bt的高度。NodeCount(bt)：求一棵二叉树bt的结点个数。LeafCount(bt)：求一棵二叉树bt的叶子结点个数。DispBTree(bt)：以括号表示法输出一棵二叉树bt。包含有基本运算的二叉树如下图所示：6.4.2二叉树基本运算实现算法本小节采用二叉链存储结构，讨论二叉树基本运算算法。（1）创建二叉树CreateBTree(bt,str)假设采用括号表示法表示的二叉树字符串str是正确的，且每个结点的值是单个字符。用ch扫描str，其中只有4类字符，各类字符的处理方式如下：若ch='('：表示前面刚创建的p结点存在着孩子结点，需将其进栈，以便建立它和其孩子结点的关系（如果一个结点刚创建完毕，其后一个字符不是'('，表示该结点是叶子结点，不需要进栈）。然后开始处理该结点的左孩子，因此置k=1，表示其后创建的结点将作为这个结点（栈顶结点）的左孩子结点；若ch=')'：表示以栈顶结点为根结点的子树创建完毕，将其退栈；若ch=','：表示开始处理栈顶结点的右孩子结点，置k=2；其他情况：只能是单个字符，表示要创建一个新结点p，根据k值建立p结点与栈顶结点之间的联系，当k=1时，表示p结点作为栈顶结点的左孩子结点，当k=2时，表示p结点作为栈顶结点的右孩子结点。对应的算法如下：voidCreateBTree(BTNode*&bt,char*str){BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;bt=NULL; //建立的二叉树初始时为空ch=str[j];while(ch!='\0') //str未扫描完时循环{ switch(ch) { case'(':top++;St[top]=p;k=1;break; //为左孩子结点 case')':top--;break; case',':k=2;break; //为右孩子结点 default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(bt==NULL) //*p为二叉树的根结点 bt=p; else //已建立二叉树根结点 {switch(k) { case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; } } } j++;ch=str[j];}}例如，对于括号表示法字符串“A(B(D(,G)),C(E,F))”，建立二叉树链式存储结构的过程如下：ch算法执行的操作St（栈底栈顶）A建立A结点，r指向该结点空(A结点进栈，置k=1AB建立B结点，因k=1，将其作为栈顶A结点的左孩子结点A(B结点进栈，置k=1ABD建立D结点，因k=1，将其作为栈顶B结点的左孩子结点AB(D结点进栈，置k=1ABD,置k=2ABDG建立G结点，因k=2，将其作为栈顶D结点的右孩子结点ABD)退栈一次AB)退栈一次A,置k=2AC建立C结点，因k=2，将其作为栈顶A结点的右孩子结点A(C结点进栈，置k=1ACE建立E结点，因k=1，将其作为栈顶C结点的左孩子结点AC,置k=2ACF建立F结点，因k=2，将其作为栈顶C结点的右孩子结点AC)退栈一次A)退栈一次空ch扫描完毕算法结束最后生成的二叉链如下图所示。“A(B(D(,G)),C(E,F))”逻辑结构－括号表示法表示存储结构－二叉链表示（2）销毁二叉树bt的运算算法销毁二叉树bt的递归模型f(bt)如下：f(bt)不做任何事情 当bt=NULLf(bt)f(bt->lchild);f(bt->rchild);free(bt); 其他情况voidDestroyBTree(BTNode*&bt){if(bt!=NULL){ DestroyBTree(bt->lchild); DestroyBTree(bt->rchild); free(bt);}}（3）求二叉树高度运算算法求二叉树bt的高度的递归模型f(bt)如下：f(bt)=0 若bt=NULLf(bt)=max{f(bt->lchild),f(bt->rchild)}+1 其他情况intBTHeight(BTNode*bt){intlchilddep,rchilddep;if(bt==NULL)return(0); //空树的高度为0else{ lchilddep=BTHeight(bt->lchild); //求左子树的高度为lchilddep rchilddep=BTHeight(bt->rchild); //求右子树的高度为rchilddep return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}（4）求二叉树结点个数运算算法求二叉树bt中结点个数的递归模型f(bt)如下：f(bt)=0 当bt=NULLf(bt)=f(bt->lchild)+f(bt->rchild)+1 其他情况intNodeCount(BTNode*bt) //求二叉树bt的结点个数{intnum1,num2;if(bt==NULL) //为空树时返回0 return0;else{ num1=NodeCount(bt->lchild); //求左子树结点个数 num2=NodeCount(bt->rchild); //求右子树结点个数

return(num1+num2+1); //返回和加上1}}（5）求二叉树叶子结点个数运算算法求二叉树bt中叶子结点个数的递归模型f(bt)如下：f(bt)=0 当bt=NULLf(bt)=1 当*bt为叶子结点f(bt)=f(bt->lchild)+f(bt->rchild) 其他情况intLeafCount(BTNode*bt) //求二叉树bt的叶子结点个数{intnum1,num2;if(bt==NULL) //空树返回0 return0;elseif(bt->lchild==NULL&&bt->rchild==NULL) return1; //为叶子结点时返回1else{ num1=LeafCount(bt->lchild); //求左子树叶子结点个数 num2=LeafCount(bt->rchild); //求右子树叶子结点个数

return(num1+num2); //返回和

}}（6）以括号表示法输出二叉树运算算法其过程是：对于非空二叉树bt，先输出其元素值，当存在左孩子结点或右孩子结点时，输出一个“(”符号，然后递归处理左子树，输出一个“,”符号，递归处理右子树，最后输出一个“)”符号。voidDispBTree(BTNode*bt){if(bt!=NULL){ printf("%c",bt->data); if(bt->lchild!=NULL||bt->rchild!=NULL) { printf("("); //有子树时输出'(' DispBTree(bt->lchild); //递归处理左子树 if(bt->rchild!=NULL) //有右子树时输出',' printf(","); DispBTree(bt->rchild); //递归处理右子树 printf(")"); //右子树输出完毕，再输出一个')' }}}6.5二叉树的遍历6.5.1常用的二叉树遍历算法所谓二叉树的遍历是指按一定的次序访问树中的所有结点，使每个结点恰好被访问一次。其中遍历次序保证了二叉树上每个结点均被访问一次且仅有一次。遍历是二叉树中经常要用到的一种操作。因为在实际应用中，常常需要按一定顺序对二叉树中的每个结点逐个地进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。二叉树常用的遍历有先序（根）遍历、中序（根）遍历、后序（根）遍历和层次遍历。所谓先序、中序、后序，区别在于访问根结点的顺序。1．先序遍历若二叉树非空，则：①访问根结点；②先序遍历左子树；③先序遍历右子树。对应的递归算法如下：voidPreOrder(BTNode*bt){if(bt!=NULL){ printf("%c",bt->data); PreOrder(bt->lchild); PreOrder(bt->rchild);}}采用先序遍历得到的访问结点序列称为先序遍历序列，先序遍历序列的特点是：其第一个元素值为二叉树中根结点值。如图6.12(a)所示二叉树的先序遍历序列为ABDEGHCFI，其PreOrder算法的执行过程如下：2．中序遍历若二叉树非空，则：①中序遍历左子树；②访问根结点；③中序遍历右子树。对应的递归算法如下：voidInOrder(BTNode*bt){if(bt!=NULL){ InOrder(bt->lchild); printf("%c",bt->data); InOrder(bt->rchild);}}采用中序遍历得到的访问结点序列称为中序遍历序列，中序遍历序列的特点是：若已知二叉树的根结点值，以该值为界，将中序遍历序列分为两部分，前半部分为左子树的中序遍历序列，后半部分为右子树的中序遍历序列。如图6.12(a)所示的二叉树，中序遍历序列为DBGEHACIF，其InOrder算法的执行过程如下：3．后序遍历若二叉树非空，则：①后序遍历左子树；②后序遍历右子树；③访问根结点。对应的递归算法如下：voidPostOrder(BTNode*bt){if(bt!=NULL){ PostOrder(bt->lchild); PostOrder(bt->rchild); printf("%c",bt->data);}}采用后序遍历得到的访问结点序列称为后序遍历序列，后序遍历序列的特点是：其最后一个元素值为二叉树中根结点值。如图6.12(a)所示的二叉树，后序遍历序列为DGHEBIFCA，其PostOrder算法的执行过程如下：4.层次遍历算法层次遍历是从根结点出发，按照从上向下，同一层从左向右的次序访问所有的结点。在层次遍历算法中采用一个循环队列qu来实现。层次遍历的实现过程是：先将根结点进队，在队不空时循环：从队列中出队一个结点*p，访问它；若它有左孩子结点，将左孩子结点进队；若它有左孩子结点，将左孩子结点进队。如此操作直到队空为止。采用层次遍历得到的访问结点序列称为层次遍历序列，层次遍历序列的特点是：其第一个元素值为二叉树中根结点值。voidLevelOrder(BTNode*bt){BTNode*p;BTNode*qu[MaxSize]; //定义循环队列,存放二叉链结点指针intfront,rear; //定义队头和队尾指针front=rear=-1; //置队列为空队列rear++;qu[rear]=bt; //根结点指针进入队列while(front!=rear) //队列不为空循环{ front=(front+1)%MaxSize; p=qu[front]; //出队结点*p printf("%c",p->data); //访问该结点 if(p->lchild!=NULL) //有左孩子时将其进队 {rear=(rear+1)%MaxSize; qu[rear]=p->lchild; } if(p->rchild!=NULL) //有右孩子时将其进队 {rear=(rear+1)%MaxSize; qu[rear]=p->rchild; }}}如图6.12(a)所示的二叉树，其层次遍历序列为ABCDEFGHI，其遍历过程如下所示：6.5.2遍历算法的应用

【例6.9】假设以二叉链作为存储结构，设计一个算法求二叉树中单分支结点个数。

解：采用后序递归遍历方式求解。先求出左子树中单分支结点个数m，再求出右子树中单分支结点个数n，若根结点是单分支结点，则返回m+n+1，否则返回m+n。求左、右子树中的单分支结点个数相当于二叉树后序遍历算法中遍历左、右子树，而判断根结点是否为单分支结点并返回相应的值相当于二叉树后序遍历算法中访问根结点的语句。intonenodes1(BTNode*bt){intm,n;if(bt!=NULL){ m=onenodes1(bt->lchild); n=onenodes1(bt->lchild); if((bt->lchild==NULL&&bt->rchild!=NULL) //单分支结点 ||(bt->lchild!=NULL&&bt->rchild==NULL)) return(1+m+n); else //其他情况 return(m+n);}elsereturn0; //空树返回0}也可以直接采用递归的方法，设f(bt)求二叉树bt的单分支结点个数，则f(bt->lchild)求二叉树bt的左子树的单分支结点个数，f(bt->rchild)求二叉树bt的右子树的单分支结点个数，显然有以下递归模型：f(bt)=0 当bt=NULLf(bt)=1+f(bt->lchild)+f(bt->rchild) 当*bt为单分支结点f(bt)=f(bt->lchild)+f(bt->rchild) 其他情况intonenodes2(BTNode*bt){intm,n;if(bt==NULL) //空树返回0 return0;m=onenodes2(bt->lchild);n=onenodes2(bt->rchild);if((bt->lchild==NULL&&bt->rchild!=NULL) //单分支结点 ||(bt->lchild!=NULL&&bt->rchild==NULL)) return(1+m+n);else //其他情况 return(m+n);}从中看到，两种求解方式得到的结果是相同的。实际上，先序、中序和后序三种遍历方法本身就是递归的，所以采用递归模型设计方法求解更加基础。

【例6.11】假设以二叉链作为存储结构，设计一个算法复制一棵二叉树。

解：采用先序递归遍历方式求解。若二叉树bt不空，则首先复制根结点，相当于二叉树先序遍历算法中的访问根结点语句，然后分别复制二叉树根结点的左子树和右子树，这相当于二叉树先序遍历算法中的遍历左子树和右子树。可以直接采用递归模型设计方法。设f(bt,nt)是由二叉链bt复制产生nt，这是大问题。f(bt->lchild,nt->lchild)和f(bt->rchild,nt->rchild)分别复制左子树和右子树，它们是小问题。假设小问题可解，也就是说左、右子树都可复制，则只需复制根结点了，如下图所示。对应的递归模型如下：f(bt,nt)：nt=NULL 当bt=NULLf(bt,nt)：由*bt根结点复制产生*nt根结点;当bt≠NULL f(bt->lchild,nt->lchild); f(bt->rchild,nt->rchild);voidCopyBTree(BTNode*bt,BTNode*&nt)//由二叉树bt复制产生二叉树nt{if(bt!=NULL){ nt=(BTNode*)malloc(sizeof(BTNode)); //复制根结点 nt->data=bt->data; CopyBTree(bt->lchild,nt->lchild); //递归复制左子树 CopyBTree(bt->rchild,nt->rchild); //递归复制左子树}elsent=NULL; //bt为空树时nt也为空树}

【例6.12】设计一个算法，由给定的二叉树的二叉链存储结构建立其对应的顺序存储结构。

解：由二叉树的顺序存储结构sb可知，sb初始时是一个所有元素为‘#’的一维数组，它的空间是由系统自动分配的，二叉树中某一个结点值存放在sb[i]中，所以应由sb[i]指定一个结点而不仅仅是sb。在二叉树的二叉链存储结构bt中，bt指向一个结点即根结点。当给定二叉链bt要建立顺序存储结构sb时，应由根结点*bt修改sb中sb[1]元素值。f(bt,sb,i)sb[i]='#' 当bt=NULLf(bt,sb,i)sb[i]=bt->data; 其他情况 f(bt->lchild,sb,2*i); f(bt->rchild,sb,2*i+1);voidtrans1(BTNode*bt,SqBinTree&sb,inti){//i的初值为根结点编号1if(bt!=NULL){ sb[i]=bt->data; //创建根结点 trans1(bt->lchild,sb,2*i); //递归建立左子树 trans1(bt->rchild,sb,2*i+1); //递归建立右子树}

elsesb[i]='#'; //不存在的结点的对应位置值为'#'}不妨设f(bt,sb,i)的功能是由bt所指结点建立sb[i]结点，显然有如下递归模型：

【例6.13】设计一个算法，由给定的二叉树顺序存储结构建立其对应的二叉链存储结构。

解：由二叉树的顺序存储结构sb可知，对于sb[i]结点，如果有左孩子，左孩子为sb[2*i]，如果有右孩子，右孩子为sb[2*i+1]。void*trans2(BTNode*&bt,SqBinTreesb,inti){//i的初值为根结点编号1if(i<Maxsize&&sb[i]!='#') //存在有效结点时{ bt=(BTNode*)malloc(sizeof(BTNode)); //创建根结点 bt->data=sb[i]; trans2(bt->lchild,sb,2*i); //递归建立左子树 trans2(bt->rchild,sb,2*i+1); //递归建立右子树}elsebt=NULL; //无效结点对应的二叉链为NULL}

【例6.14】假设以二叉链作为存储结构，设计一个算法，输出每个叶子结点的所有祖先结点。并对图6.14所示的二叉树求解结果。

解法1：采用先序遍历的递归方法求解。用path数组保存从根结点开始的路径，pathlen保存path中的元素个数。在先序遍历时，当找到某个叶子结点时，path中恰好保存了它的所有祖先结点，输出即可。若不是叶子结点，将其保存到path中，再在左子树中递归查找，之后再在右子树中递归查找。voidancestor1(BTNode*bt,ElemTypepath[],intpathlen){inti;if(bt!=NULL){ if(bt->lchild==NULL&&bt->rchild==NULL) //*bt为叶子结点 {printf("%c结点的所有祖先结点:",bt->data); for(i=pathlen-1;i>=0;i--) printf("%c",path[i]); printf("\n"); } else {path[pathlen]=bt->data; //将当前结点放入路径中 pathlen++; //path中元素个数增1 ancestor1(bt->lchild,path,pathlen); //递归扫描左子树 ancestor1(bt->rchild,path,pathlen); //递归扫描右子树 }}}

解法2：采用层次遍历方法求解。设置一个非循环队列qu，其中元素有两个域：s为二叉树中结点指针，parent存放该结点的双亲结点在qu中的下标，另外front和rear为队头队尾指针，初值均为-1。先将根结点进队，其parent置为-1（根结点没有双亲）。当队不空时循环：出队一个结点*p，它在qu中的下标为front，如果*p结点为叶子结点，它的所有祖先必在队列qu中，通过结点的parent导出所有祖先结点并输出；否则，若*p结点有左孩子，将左孩子进队，并置左孩子的parent为front，若*p结点有右孩子，将右孩子进队，并置右孩子的parent为front。voidancestor2(BTNode*bt){BTNode*p;inti;struct{ BTNode*s; //存放结点指针intparent; //存放其双亲结点在qu中的下标}qu[MaxSize]; //qu存放队中元素intfront=-1,rear=-1; //队头队尾指针rear++;qu[rear].s=bt; //根结点进队qu[rear].parent=-1; //根结点没有双亲,其parent置为-1while(front!=rear) //队不空循环{ front++; p=qu[front].s; //出队一个结点*p,它在qu中的下标为front if(p->lchild==NULL&&p->rchild==NULL)//若*p为叶子结点 {printf("%c结点的所有祖先结点:",p->data); i=qu[front].parent; while(i!=-1) { printf("%c",qu[i].s->data); i=qu[i].parent; } printf("\n"); } if(p->lchild!=NULL) //*p有左孩子,将左孩子进队 {rear++; qu[rear].s=p->lchild; qu[rear].parent=front; //左孩子的双亲为qu[front]结点 } if(p->rchild!=NULL) //*p有右孩子,将右孩子进队 {rear++; qu[rear].s=p->rchild; qu[rear].parent=front; //右孩子的双亲为qu[front]结点 }}}设计如下主函数调用上述算法：#include<stdio.h>#include"BTree.h"voidmain(){BTNode*bt;ElemTypepath[MaxSize];CreateBTree(bt,"A(B(D,E(G,H)),C(,F(I)))");//建立图6.14的二叉链printf("bt括号表示法:");DispBTree(bt);printf("\n");printf("解法1:\n");printf("输出每个叶结点的所有祖先结点:\n");ancestor1(bt,path,0);printf("解法2:\n");printf("输出每个叶结点的所有祖先结点:\n");ancestor2(bt);}本程序的执行结果如下：bt括号表示法:A(B(D,E(G,H)),C(,F(I)))解法1:输出每个叶结点的所有祖先结点:D结点的所有祖先结点:BAG结点的所有祖先结点:EBAH结点的所有祖先结点:EBAI结点的所有祖先结点:FCA解法2:输出每个叶结点的所有祖先结点:D结点的所有祖先结点:BAG结点的所有祖先结点:EBAH结点的所有祖先结点:EBAI结点的所有祖先结点:FCA6.6二叉树的构造6.6.1什么是二叉树的构造一棵所有结点值不同的二叉树，其先序、中序、后序和层次遍历都是唯一的，也就是说一棵这样的二叉树，不可以有两种不同的先序遍历序列，也不可能有两种不同的中序序列。所谓二叉树的构造，就是给定某些遍历序列，反过来唯一地确定该二叉树的形态。一棵二叉树的形态由根结点N、左子树L和右子树R三部分构成，如果这三部分确定了，这棵二叉树的形态也就确定了。

【例6.15】一棵二叉树的先序遍历序列和中序遍历序列相同，说明该二叉树的形态。

解：二叉树的先序遍历序列为NLR，中序遍历序列为LNR，要使NLR=LNR，则L应为空（因为N为空后其L、R没有意义），所以这样的二叉树为右单支树（除叶子结点外每个结点只有一个右孩子）。6.6.2二叉树的构造方法对于图6.8所示的5棵二叉树，其先序、中序和后序遍历序列如下表所示。二叉树遍历序列图6.8(a)的二叉树图6.8(b)的二叉树图6.8(c)的二叉树图6.8(d)的二叉树图6.8(e)的二叉树先序遍历序列ABCABCABCABCABC中序遍历序列BACBCAACBCBAABC后序遍历序列BCACBACBACBACBA从中看到，对于不同形态的二叉树：先序遍历序列可能相同（图6.8中5棵二叉树的先序遍历序列均相同）。中序遍历序列可能相同（若没有C结点，图6.8(a)和6.8(b)的中序遍历序列均为BA）。后序遍历序列可能相同（图6.8(b)～6.8(e)的后序遍历序列均相同）先序遍历序列和后序遍历序列可能都相同（图6.8(d)和(e)的先序遍历序列和后序遍历序列均相同）。实际上，在先序、中序和后序遍历序列中：①由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。②由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。③由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。任何n（n≥0）个不同节点的二又树，都可由它的中序序列和先序序列唯一地确定。采用数学归纳法证明。当n=0时，二叉树为空，结论正确。假设节点数小于n的任何二叉树，都可以由其先序序列和中序序列唯一地确定。已知某棵二叉树具有n（n＞0）个不同节点，其先序序列是a0a1…an-1；中序序列是b0b1…bk-1bkbk+1…bn-1。因为在先序遍历过程中，访问根节点后，紧跟着遍历左子树，最后再遍历右子树。所以a0必定是二叉树的根节点，而且a0必然在中序序列中出现。也就是说，在中序序列中必有某个bk（0≤k≤n-1）就是根节点a0。1.由先序遍历序列和中序遍历序列构造一棵二叉树由于bk是根节点,而在中序遍历过程中,先遍历左子树,再访问根节点,最后再遍历右子树。所以在中序序列中,b0b1…bk-1必是根节点bk（也就是a0）左子树的中序序列,即bk的左子树有k个节点（注意k=0表示节点bk没有左子树）。而bk+1…bn-1必是根节点bk（也就是a0）右子树的中序序列,即bk的右子树有n-k-1个节点（注意k=n-1表示节点bk没有右子树）。。另外,在先序序列中,紧跟在根节点a0之后的k个节点a1…ak就是左子树的先序序列,ak+1…an-1这n-k-1就是右子树的先序序列。

【例6.16】已知先序序列为ABDECFG，中序序列为DBEACGF，给出构造该二叉树的过程。

解：构造该二叉树的过程如下图所示。

任何n（n＞0）个不同节点的二又树，都可由它的中序序列和后序序列唯一地确定。同样采用数学归纳法证明。

实际上，对于根节点ak的左右子树，在确定左右子树的子中序序列后，不需要确定左右子树的整个子后序序列，只需确定子中序序列中全部字符在后序序列中最右边的那个字符即可，因为这个字符就是子树的根节点。

2.由中序遍历序列和后序遍历序列构造一棵二叉树

【例6.17】已知一棵二叉树的后序遍历序列为DEBGFCA，中序遍历序列为DBEACGF，给出构造该二叉树的过程。

解：构造该二叉树的过程如下图所示。另外，由层次遍历序列和中序遍历序列也可以唯一构造一棵二叉树。其构造过程是，层次遍历序列的第一个结点是二叉树的根结点，确定根结点后，到二叉树的中序遍历序列中找到该结点，这个结点将二叉树分为左子树、根和右子树三部分。左子树中所有结点在层次遍历序列中出现的次序对应左子树的层次遍历序列，右子树中所有结点在层次遍历序列中出现的次序对应右子树的层次遍历序列，再采用同样的方式构造左、右子树，从而构造出整棵二叉树。6.7二叉树与树之间的转换6.7.1森林/树转换成二叉树将一棵树转换成二叉树的过程如下：①树中所有相邻兄弟之间加一条连线；②对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其他孩子结点之间的连线；③以树的根结点为轴心，将整棵树顺时针转动45度，使之结构层次分明。

【例6.18】将图6.27(a)所示的树转换成二叉树。

解：转换的过程如图6.27(b)～(d)所示，最终结果如图6.27(d)所示。当要转换为二叉树的森林由两棵或以上树构成时，将这样的森林转换为二叉树的过程如下：①将森林中的每棵树转换成相应的二叉树。②第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子结点，当所有二叉树连在一起后，此时所得到的二叉树就是由森林转换得到的二叉树。

【例6.19】将图6.28(a)所示的森林转换成二叉树。

解：转换的过程如图6.28(b)～(e)所示，最终结果如图6.28(e)所示。6.7.2二叉树还原为树/森林当一棵二叉树是由一棵树转换而来的，则该二叉树还原为树的过程如下：①若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、…、都与该结点的双亲结点用连线连起来。②删除原二叉树中所有双亲结点与右孩子结点之间的连线。③整理由①、②两步所得到的树，使之结构层次分明。

【例6.21】将图6.29(a)所示的一棵二叉树还原为森林。

解：转换的过程如图6.29(b)～(d)所示，最终结果如图6.29(d)所示。当一棵二叉树是由m棵树构成的森林转换而来的，该二叉树的根结点一定有m-1个右下孩子，则该二叉树还原为森林的过程如下：①抹掉二叉树根结点右链上所有结点之间的“双亲－右孩子”关系，将其分成若干个以右链上的结点为根结点的二叉树，设这些二叉树为bt1、bt2、…、btm。②分别将bt1、bt2、…、btm二叉树各自还原成一棵树。

【例6.22】将如图6.30(a)所示的二叉树还原为森林。

解：还原为森林的过程如图6.30(b)和(c)所示，最终结果如图6.30(c)所示。6.8线索二叉树6.8.1什么是线索对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。线索二叉树分为先序、中序和后序线索二叉树。3种不同的线索二叉树，图中虚线为线索。6.8.2线索二叉树的存储结构在原二叉链中增加了ltag和rtag两个标志域。线索二叉树的类型定义如下：typedefstructbthnode{ElemTypedata;structbthnode*lchild,*rchild;intltag,rtag;}BthNode;下面以中序线索二叉树为例，讨论线索二叉树的建立和相关算法。为了方便算法实现，为线索二叉树增加一个头结点。6.8.3建立线索二叉树及其销毁建立线索化二叉树称之为二叉树线索化。以中序线索化一棵二叉树为例，实质上就是中序遍历一棵二叉树，在遍历过程中，检查当前结点的左、右指针域是否为空；如果为空，将它们改为指向前驱结点或后继结点的线索。其算法思想是：先创建一个头结点*head，在进行中序遍历过程中需保留当前结点*p的前驱结点的指针，设为pre（全局变量，初值时指向头结点）。在p不空的情况下：①遍历左子树（即左子树线索化）。②对空指针线索化。若p->lchild为空，则置p->ltag=1，且p->lchild=pre；若p->rchild为空，则置pre->rtag=l，且pre->rchild=p；pre=p；③遍历右子树（即右子树线索化）。BthNode*CreaThread(BthNode*bt)//对以*bt为根结点的二叉树中序线索化,并增加一个头结点head{

BthNode*head;head=(BthNode*)malloc(sizeof(BthNode));head->ltag=0;head->rtag=1; //创建头结点*head

head->rchild=bt;

if(bt==NULL) //bt为空树时 head->lchild=head;else{ head->lchild=bt; pre=head; //pre是*p的前驱结点,供加线索用

Thread(bt); //中序遍历线索化二叉树 pre->rchild=head; //最后处理,加入指向根结点的线索 pre->rtag=1; head->rchild=pre; //根结点右线索化}returnhead;}BthNode*pre; //定义pre为全局变量voidThread(BthNode*&p)//对以*p为根结点的二叉树进行中序线索化{if(p!=NULL){ Thread(p->lchild); //左子树线索化 if(p->lchild==NULL) //前驱线索 {p->lchild=pre; //给结点*p添加前驱线索

p->ltag=1; } elsep->ltag=0; if(pre->rchild==NULL) { pre->rchild=p; //给结点*pre添加后继线索

pre->rtag=1; } elsepre