数据结构简明教程（第3版）课件 第6章 树和二叉树(上)（下）

第6章树和二叉树6.1树6.2二叉树6.3递归算法设计方法6.4二叉树的基本运算算法6.5二叉树的遍历6.6二叉树的构造6.7二叉树与树之间的转换6.8线索二叉树6.9哈夫曼树第6章树和二叉树1/1156.1树6.1.1树的定义从数据结构角度看，树包含n（n≥0）个结点，当n=0时，称为空树；非空树的定义如下：

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

【例6.1】

有一棵树T=(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>}画出其逻辑结构图。6.1树3/115

A是根结点，其余结点分成三个互不相交的子集：

T1={B}，T2={C，E，F，H}，T3={D，G}。T1、T2、T3都是根结点A的子树，且各自本身也是一棵树。说明：树中结点之间的关系应为有向关系，在上图中，结点之间的连线即分支线都是有向的，默认箭头向下的。ABCDEFHG6.1树4/1156.1.2树的逻辑结构表示树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。ABCDEFHG6.1树5/115文氏图表示法。使用集合以及集合的包含关系描述树结构。ABCDEFHG6.1树6/115凹入表示法。使用线段的伸缩关系描述树结构。ABCDEFHG6.1树7/115括号表示法。将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号分隔。A(B,C(E(H),F),D(G))ABCDEFHG6.1树8/1156.1.3树的基本术语度为3度为1结点的度。树中每个结点具有的子树数或者后继结点数称为该结点的度。ABCDEFHG6.1树9/115树的度。树中所有结点的度的最大值称之为树的度。树的度为3ABCDEFHG6.1树10/115分支结点。度大于0的结点称为分支结点或非终端结点。度为1的结点称为单分支结点，度为2的结点称为双分支结点，依次类推。ABCDEFHGA、C、D、E为分支结点6.1树11/115叶子结点（或叶结点）。度为零的结点称为叶子结点或终端结点。ABCDEFHGB、H、F、G为叶子结点6.1树12/115孩子结点。一个结点的后继称之为该结点的孩子结点。结点A的孩子结点为B、C和DABCDEFHG6.1树13/115双亲结点（或父亲结点）。一个结点称为其后继结点的双亲结点。结点E和F的双亲结点均为CABCDEFHG6.1树14/115子孙结点。一个结点的子树中除该结点外的所有结点称之为该结点的子孙结点。ABCDEFHG结点C结点的子孙结点为E、F和H6.1树15/115祖先结点。从树根结点到达某个结点的路径上通过的所有结点称为该结点的祖先结点（不含该结点自身）。ABCDEFHG结点F的祖先结点为A、C6.1树16/115兄弟结点。具有同一双亲的结点互相称之为兄弟结点。结点E和F是兄弟结点ABCDEFHG6.1树17/115结点层次。树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次。1234ABCDEFHG6.1树18/115树的高度。树中结点的最大层次称为树的高度或深度。1234ABCDEFHG高度是46.1树19/115森林。零棵或多棵互不相交的树的集合称为森林。ABCDEFHG4棵树构成的森林6.1树20/115性质1：

树中的结点数等于所有结点的度数加1。度之和＝分支数分支数=n-1所以，n=度之和+16.1.4树的性质6.1树ABCDEFHGn=8度之和＝3+2+1+1=7分支数=7n=度之和+121/115性质2：度为m的树中第i层上至多有mi-1个结点（i≥1）。6.1树22/115

推广：当一棵m次树的第i层有mi-1个结点（i≥1）时，称该层是满的，若一棵m次树的所有叶子结点在同一层，并且每一层都是满的，称为满m次树。显然，满m次树是所有相同高度的m次树中结点总数最多的树。也可以说，对于n个结点，构造的m次树为满m次树或者接近满m次树，此时树的高度最小。6.1树23/115性质3：

高度为h的m次树至多有个结点。6.1树24/115

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

设该三次树中总结点个数、度为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树26/1156.1.5树的基本运算树的运算主要分为三大类：查找满足某种特定关系的结点，如寻找当前结点的双亲结点等；插入或删除某个结点，如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；遍历树中结点。6.1树27/115

树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。

有以下三种遍历方法：树的遍历

先根遍历后根遍历层次遍历注意：先根和后根遍历算法都是递归的。6.1树28/115先根遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。层次遍历:若树不空，则自上而下自左至右访问树中每个结点。6.1树29/115ABCDEFGHJIK先根遍历的顶点访问次序：ABEFCDGHIJK后根遍历的顶点访问次序：EFBCIJKHGDA层次遍历的顶点访问次序：ABCDEFGHIJK6.1树30/1156.1.6树的存储结构

这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。1.双亲存储结构ABCDEFHG位置dataparent0A-11B02C03D04E25F26G37H46.1树31/115孩子链存储结构可按树的度（即树中所有结点度的最大值）设计结点的孩子结点指针域个数。2.孩子链存储结构ABCDEFHG6.1树32/115孩子兄弟链存储结构是为每个结点设计三个域：一个数据元素域，一个该结点的第一个孩子结点指针域，一个该结点的下一个兄弟结点指针域。3.孩子兄弟链存储结构ABCDEFHG6.1树33/1156.2二叉树6.2.1二叉树的定义二叉树的递归定义：二叉树或者是一棵空树。或者是一棵由一个根结点和两棵互不相交的分别称做根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。6.2二叉树34/115注意：二叉树与度为2的树是不同的。度为2的树至少有3个结点，而二叉树的结点数可以为0。度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。6.2二叉树35/115归纳起来，二叉树的5种形态：Ø(a)空二叉树(b)只有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树非空的二叉树6.2二叉树36/115

【例6.3】给出由3个结点A、B和C构成的所有形态的二叉树（不考察结点值的差异）。解：含有3个结点A、B和C的所有形态的二叉树：ABCABCABCABCABC6.2二叉树37/115性质1

非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1。约定：二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2，6.2.2二叉树性质总结点数n=n0+n1+n2。一个度为1的结点贡献1个度，一个度为2的结点贡献2个度，所以总的度数=n1+2n2。总的度数=总分支数=n-1。则n1+2n2=n0+n1+n2-1，求出n0=n2+1。证明：6.2二叉树38/115

【例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。6.2二叉树39/115性质2非空二叉树上第i层上至多有2i-1个结点，这里应有i≥1。

由树的性质2可推出。性质3高度为h的二叉树至多有2h-1个结点（h≥1）。

由树的性质3可推出。6.2二叉树40/115满二叉树：在一棵二叉树中，当第i层的结点数为2i-1个时，则称此层的结点数是满的，当一棵二叉树中的每一层都满时，且叶子结点在同一层上，则称此树为满二叉树。满二叉树特性：除叶子结点以外的其他结点的度皆为2。

6.2二叉树41/115高度为h的满二叉树中的结点数为2h-1个。层序编号：从根结点为1开始，按照层次从小到大、同一层从左到右的次序顺序编号。可以对满二叉树的结点进行连续编号。一棵高度为4的满二叉树，其结点数为24-1=15。图中每个结点旁的编号是层序编号ABDHIEJKCFLMGNO1248951011361213714156.2二叉树42/115完全二叉树：在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则称此树为完全二叉树。完全二叉树特性：二叉树中至多只有最下边两层结点的度数小于2。高度为h的完全二叉树若按层序编号,它与高度为h的满二叉树中结点的编号一一对应。6.2二叉树43/115一棵完全二叉树，它与等高度的满二叉树相比，在最后一层的右边缺少了3个结点。ABDHIEJKCFLG1248951011361276.2二叉树44/115

性质4对完全二叉树中编号为i的结点（1≤i≤n，n≥1，n为结点数）有：

（1）若i≤

n/2，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点。

（2）若n为奇数，则每个分支结点都既有左孩子结点，也有右孩子结点；

若n为偶数，则编号最大的分支结点只有左孩子结点，没有右孩子结点，其余分支结点都有左、右孩子结点。6.2二叉树45/115

（3）若编号为i的结点有左孩子结点，则左孩子结点的编号为2i；若编号为i的结点有右孩子结点，则右孩子结点的编号为(2i+1)。

（4）除树根结点外,若一个结点的编号为i，则它的双亲结点的编号为

i/2，也就是说，当i为偶数时，其双亲结点的编号为i/2,它是双亲结点的左孩子结点，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子结点。i/2i2i2i+16.2二叉树46/115【例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二叉树47/1156.2.3二叉树的存储结构1．顺序存储结构顺序存储一棵二叉树时，就是用一组连续的存储单元存放二叉树中的结点。由二叉树的性质4可知，对于完全二叉树（或满二叉树），树中结点层序编号可以唯一地反映出结点之间的逻辑关系，所以可以用一维数组按从上到下、从左到右的顺序存储树中所有结点值，通过数组元素的下标关系反映完全二叉树或满二叉树中结点之间的逻辑关系。6.2二叉树48/115一棵完全二叉树的顺序存储结构1234567891011121314…ABCDEFGHIJKL###位置dataABDHIEJKCFLG1248951011361276.2二叉树49/115一般的二叉树的顺序存储结构设计：ABDEGHCFKABDEGHCFK1248951011361271413增添空结点补齐为一棵完全二叉树并对所有结点进行编号6.2二叉树50/115ABDEGHCFK12489510113612714131234567891011121314…ABCDE#F##GH##K#位置data仅保留实际存在的结点值，其他为空6.2二叉树51/115二叉树顺序存储结构的类型定义如下：typedefElemTypeSqBinTree[MaxSize];其中，ElemType为二叉树中结点的数据值类型，MaxSize为顺序表的最大长度。为了方便运算，通常将下标为0的位置空着，值为'#'的结点为空结点。

6.2二叉树52/115完全二叉树或满二叉树采用顺序存储结构比较合适，既能够最大可能地节省存储空间，又可以利用数组元素的下标确定结点在二叉树中的位置以及结点之间的关系。对于一般二叉树，如果它接近于完全二叉树形态，需要增加的空结点个数不多，也可适合采用顺序存储结构。6.2二叉树53/115如果需要增加很多空结点才能将一棵二叉树改造成为一棵完全二叉树，采用顺序存储结构会造成空间的大量浪费，这时不宜用顺序存储结构。h=4MazSize=24-1=15空间利用率=4/15=27%6.2二叉树54/1152．二叉链存储结构对于一般的二叉树，通常采用二叉链表示。链表中的每个结点包含两个指针，分别指向对应结点的左孩子和右孩子（注意在树的孩子兄弟链表存储结构中，每个结点的两个指针分别指向对应结点的第一个孩子和下一个兄弟）。6.2二叉树55/115在二叉链存储中，结点的类型声明如下：typedefstructtnode{ElemTypedata;

//数据域

structtnode*lchild,*rchild; //指针域}BTNode;data表示数据域，用于存储放入结点值（默认情况下为单个字母）。lchild和rchild分别表示左指针域和右指针域，分别存储左孩子和右孩子结点（即左、右子树的根结点）的存储地址。当某结点不存在左或右孩子时，其lchild或rchild指针域取特殊值NULL。6.2二叉树56/115ABDEGHCFKA

B

∧D∧

E

∧G∧

∧H∧

∧C

F∧

∧K∧

b6.2二叉树57/1156.3递归算法设计方法6.3.1什么是递归在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身，称之为直接递归。若过程或函数p调用过程或函数q，而q又调用p，称之为间接递归。后面主要介绍直接递归。6.3递归算法设计方法58/115例如，有以下递归函数：对应的求解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));}6.3递归算法设计方法59/115计算fun(5)的过程求解fun(5)fun(3)=fun(2)+fun(1)n=3返回22fun(3)=fun(2)+fun(1)n=3fun(4)=fun(3)+fun(2)n=43返回3fun(5)=fun(4)+fun(3)n=5返回22返回11返回11返回11返回11返回11返回5=56.3递归算法设计方法60/115递归树fun(5)fun(4)fun(3)fun(2)fun(1)fun(2)fun(3)fun(2)fun(1)6.3递归算法设计方法61/115一般地，递归模型由两部分组成，一部分为递归出口，它给出了递归的终止条件。另一部分为递归体，它确定递归求解时的递推关系。例如，前面例子中的f(1)=1和f(2)=1就是递归出口；f(n)=f(n-1)+f(n-2)就是递归体。6.3递归算法设计方法62/115递归算法求解过程的特征：先将不能直接求解的问题转换成若干个相似的小问题，通过分别求解各子问题，最后获得整个问题的解。当这些子问题不能直接求解时，还可以再将它们转换成若干个更小的子问题，如此反复进行，直到遇到递归出口为止。这种自上而下将问题分解、求解，再自上而下引用、合并，求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。6.3递归算法设计方法63/1156.3.2递归算法设计一般方法递归算法的设计方法是，先确定对应的递归模型，再将其转换为递归算法。其核心思想是把问题简化分解为几个子问题，其中子问题的形式和算法与原问题算法相似，只是比原来简化。6.3递归算法设计方法64/115获取求解问题的递归模型的一般步骤对原问题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.3递归算法设计方法65/115【例6.7】设计一个递归算法求一个整数数组中所有元素之和。

相应的递归算法如下：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.3递归算法设计方法设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]。对应的递归模型如下：66/115

【例6.8】对于不带头结点的非空单链表L（结点类型用SLinkNode表示），其结点值均为整数，设计以下递归算法：（1）求最大的结点值；（2）求最小的结点值；（3）正向输出所有结点值；（4）反向输出所有结点值。a1a2an∧…LL->nextf(L->next)f(L)6.3递归算法设计方法67/115

（1）设f1(L)计算单链表L中最大结点值，这是原问题，小问题为f1(L->next)计算以单链表L->next中最大结点值。假设f1(L->next)已计算出来，显然有：

f1(L)=max(L->data，f1(L->next))；

当单链表L中只有一个结点时有：f1(L)=L->data。a1a2an∧…LL->nextf(L->next)f(L)递归模型f1(L)=L->data

当L中只有一个结点时f1(L)=max{L->data，f1(L->next)}

其他情况6.3递归算法设计方法68/115intf1(SLinkNode*L){intm;

if(L->next==NULL)returnL->data;else

{m=f1(L->next); //递归求小问题的解

if(m>L->data)returnm;

elsereturnL->data;

}}f1(L)=L->data

当L中只有一个结点时f1(L)=max{L->data，f1(L->next)}

其他情况6.3递归算法设计方法69/115（2）分析同（1）小题。对应的递归算法如下：intf2(SLinkNode*L){intm;

if(L->next==NULL) returnL->data;

else

{m=f2(L->next); //递归求小问题的解

if(m<L->data)returnm;

elsereturnL->data;

}}a1a2an∧…LL->nextf(L->next)f(L)6.3递归算法设计方法70/115

（3）设f3(L)正向输出单链表L的所有结点值，这是原问题。则小问题就是f3(L->next)，它正向输出单链表L->next的所有结点值。

假设f3(L->next)已输出，显然f3(L)等价于先输出L->data值，再调用f3(L->next))。当单链表L为空时，不做任何输出。a1a2an∧…LL->nextf(L->next)f(L)6.3递归算法设计方法71/115对应的递归模型如下：f3(L)

不做任何事情 当L==NULLf3(L)

输出L->data;f3(L->next)) 其他情况voidf3(SLinkNode*L){if(L!=NULL)

{ printf("%d",L->data);

f3(L->next);

}}其中“

”表示等价关系。6.3递归算法设计方法72/115（4）分析同（3）小题。对应的递归算法如下：voidf4(SLinkNode*L){if(L!=NULL)

{f4(L->next);

printf("%d",L->data);

}}a1a2an∧…LL->nextf(L->next)f(L)6.3递归算法设计方法73/1156.3.3二叉树的递归算法设计递归算法设计便是从递归数据结构的基本递归运算入手的。对于二叉树，以二叉链为存储结构，其基本递归运算就是求一个结点p的左子树（p->lchild）和右子树（p->rchild）。p->lchild和p->rchild一定是一棵二叉树（这是为什么二叉树的定义中空树也是二叉树的原因）。6.3递归算法设计方法74/115对于二叉树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或只有一个结点的特殊情况，从而得到递归出口。一般地，二叉树的递归结构如下：bf(b)b->lchildf(b->lchild)b->rchildf(b->rchild)6.3递归算法设计方法75/115例如，假设二叉树中所有结点值为整数，采用二叉链存储结构，求该二叉树b中所有结点值之和。f(b)=0

当b=NULLf(b)=b->data+f(b->lchild)+f(b->rchild) 其他情况intSum(BTNode*b){if(b==NULL)return0;

elsereturn(b->data+Sum(b->lchild)+Sum(b->rchild));}6.3递归算法设计方法设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。76/1156.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二叉树的基本运算算法77/1156.4.2二叉树基本运算实现算法本小节采用二叉链存储结构，讨论二叉树基本运算算法。（1）创建二叉树CreateBTree(bt,str)

str逻辑结构bt存储结构6.4二叉树的基本运算算法78/115

采用括号表示法表示的二叉树字符串str，且每个结点的值是单个字符。用ch扫描str，其中只有4类字符，各类字符的处理方式：若ch='('：表示前面刚创建的p结点存在着孩子结点，需将其进栈，以便建立它和其孩子结点的关系。然后开始处理该结点的左孩子，因此置k=1，表示其后创建的结点将作为这个结点（栈顶结点）的左孩子结点；若ch=')'：表示以栈顶结点为根结点的子树创建完毕，将其退栈；若ch=','：表示开始处理栈顶结点的右孩子结点，置k=2；其他情况：只能是单个字符，表示要创建一个新结点p，根据k值建立p结点与栈顶结点之间的联系，当k=1时，表示p结点作为栈顶结点的左孩子结点，当k=2时，表示p结点作为栈顶结点的右孩子结点。6.4二叉树的基本运算算法79/115对应的算法如下：voidCreateBTree(BTNode*&bt,char*str){BTNode*St[MaxSize],*p=NULL;

inttop=-1,k,j=0;

charch;

bt=NULL; //建立的二叉树初始时为空

ch=str[j];6.4二叉树的基本运算算法80/115while(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];}}6.4二叉树的基本运算算法81/115（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);

}}6.4二叉树的基本运算算法82/115（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);

//空树的高度为0

else

{lchilddep=BTHeight(bt->lchild);//求左子树的高度rchilddep=BTHeight(bt->rchild);//求右子树的高度

return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);

}}6.4二叉树的基本运算算法83/115（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) //为空树时返回0return0;

else

{num1=NodeCount(bt->lchild); //求左子树结点个数

num2=NodeCount(bt->rchild); //求右子树结点个数

return(num1+num2+1); //返回和加上1

}}6.4二叉树的基本运算算法84/115（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; //为叶子结点时返回1

else

{ num1=LeafCount(bt->lchild); //求左子树叶子结点个数

num2=LeafCount(bt->rchild); //求右子树叶子结点个数

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

}}6.4二叉树的基本运算算法85/115（6）以括号表示法输出二叉树运算算法对于非空二叉树bt，先输出其元素值。当存在左孩子结点或右孩子结点时，输出一个'('符号。递归处理左子树。有右子树时输出一个','符号。递归处理右子树。最后输出一个')'符号。6.4二叉树的基本运算算法根（左子树，右子树）86/115voidDispBTree(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.4二叉树的基本运算算法87/1156.5二叉树的遍历6.5.1常用的二叉树遍历算法二叉树的遍历是指按一定的次序访问树中的所有结点，使每个结点恰好被访问一次。其中遍历次序保证了二叉树上每个结点均被访问一次且仅有一次。二叉树常用的遍历有先序（根）遍历、中序（根）遍历、后序（根）遍历和层次遍历。所谓先序、中序、后序，区别在于访问根结点的顺序。6.5二叉树的遍历88/115若二叉树非空，则：①访问根结点；②先序遍历左子树；③先序遍历右子树。voidPreOrder(BTNode*bt){if(bt!=NULL)

{ printf("%c",bt->data);

PreOrder(bt->lchild);

PreOrder(bt->rchild);

}}先序遍历序列的特点：其第一个元素值为二叉树中根结点值。1．先序遍历6.5二叉树的遍历89/115若二叉树非空，则：①中序遍历左子树；②访问根结点；③中序遍历右子树。voidInOrder(BTNode*bt){if(bt!=NULL)

{ InOrder(bt->lchild); printf("%c",bt->data);

InOrder(bt->rchild);

}}中序遍历序列的特点：若已知二叉树的根结点值，以该值为界，将中序遍历序列分为两部分，前半部分为左子树的中序遍历序列，后半部分为右子树的中序遍历序列。2．中序遍历6.5二叉树的遍历90/115若二叉树非空，则：①后序遍历左子树；②后序遍历右子树；③访问根结点。voidPostOrder(BTNode*bt){if(bt!=NULL)

{ PostOrder(bt->lchild);

PostOrder(bt->rchild); printf("%c",bt->data);

}}后序遍历序列的特点：最后一个元素值为二叉树中根结点值。3．后序遍历6.5二叉树的遍历91/115层次遍历是从根结点出发，按照从上向下，同一层从左向右的次序访问所有的结点。采用层次遍历得到的访问结点序列称为层次遍历序列。层次遍历序列的特点：其第一个元素值为二叉树中根结点值。4.层次遍历算法6.5二叉树的遍历92/115在层次遍历算法中采用一个循环队列qu来实现。层次遍历算法的实现过程：先将根结点进队，在队不空时循环：从队列中出队一个结点p，访问它；若它有左孩子结点，将左孩子结点进队；若它有右孩子结点，将右孩子结点进队。如此操作直到队空为止。6.5二叉树的遍历93/115voidLevelOrder(BTNode*bt){BTNode*p;

BTNode*qu[MaxSize]; //定义循环队列,存放二叉链结点指针

intfront,rear; //定义队头和队尾指针

front=rear=0;

//置队列为空队列

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.5二叉树的遍历94/1156.5.2遍历算法的应用

【例6.9】假设以二叉链作为存储结构，设计一个算法求二叉树中单分支结点个数。采用后序递归遍历方式求解。6.5二叉树的遍历空树返回0.先求出左子树中单分支结点个数m，再求出右子树中单分支结点个数n。若根结点是单分支结点，则返回m+n+1，否则返回m+n。95/115intonenodes1(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}6.5二叉树的遍历96/115也可以直接采用递归的方法：设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) 其他情况递归模型6.5二叉树的遍历97/115intonenodes2(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.5二叉树的遍历98/115

【例6.11】假设以二叉链作为存储结构，设计一个算法复制一棵二叉树。btbt->lchildbt->rchildntnt->lchildnt->rchildf(bt->lchild，nt->lchild)f(bt->rchild，nt->rchild)6.5二叉树的遍历设计思路99/115f(bt,nt)

nt=NULL当bt=NULLf(bt,nt)

由bt根结点复制产生nt根结点;

当bt≠NULL

f(bt->lchild,nt->lchild);

f(bt->rchild,nt->rchild);递归模型6.5二叉树的遍历100/115voidCopyBTree(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.5二叉树的遍历101/115

【例6.12】设计一个算法，由给定的二叉树的二叉链存储结构建立其对应的顺序存储结构。sb初始时是一个所有元素为'#'的一维数组，它的空间是由系统自动分配的。二叉树中某一个结点值存放在sb[i]中，应由sb[i]指定一个结点而不仅仅是sb。在二叉树的二叉链存储结构bt中，bt指向根结点。应由根结点bt修改sb中sb[1]元素值。6.5二叉树的遍历设计思路102/115f(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.5二叉树的遍历103/115

【例6.13】设计一个算法，由给定的二叉树顺序存储结构建立其对应的二叉链存储结构。6.5二叉树的遍历对于sb[i]结点，如果有左孩子，左孩子为sb[2*i]，如果有右孩子，右孩子为sb[2*i+1]。i2i2i+1设计思路104/115void*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.5二叉树的遍历105/115

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

ABDEGHCFK6.5二叉树的遍历106/115解法1：采用先序遍历的递归方法求解。用path数组保存从根结点开始的路径，pathlen保存path中的元素个数。在先序遍历时，当找到某个叶子结点时，path中恰好保存了它的所有祖先结点，输出即可。若不是叶子结点，将其保存到path中，再在左子树中递归查找，之后再在右子树中递归查找。6.5二叉树的遍历107/115voidancestor1(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);//扫描右子树

}

}}6.5二叉树的遍历108/115解法2：采用层次遍历方法求解。设置一个非循环队列qu，其中元素有两个域：s为二叉树中结点指针，parent存放该结点的双亲结点在qu中的下标，另外front和rear为队头队尾指针，初值均为0。先将根结点进队，其parent置为-1（根结点没有双亲）。当队不空时循环：出队一个结点p，它在qu中的下标为front。如果p结点为叶结点，它的所有祖先必在队列qu中，通过结点的parent导出所有祖先结点并输出。否则，若p结点有左孩子，将左孩子进队，并置左孩子的parent为front；若p结点有右孩子，将右孩子进队，并置右孩子的parent为front。6.5二叉树的遍历109/115voidancestor2(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置为-16.5二叉树的遍历110/115while(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");

}6.5二叉树的遍历111/115if(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]结点

}

}}6.5二叉树的遍历112/115ABDC非循环队列：数组模拟A↑-10B↑01C↑02D↑13C为叶子结点反推路径输出C:AD为叶子结点反推路径输出D:B

A所有叶子的祖先结点输出完毕示例6.5二叉树的遍历113/115设计如下主函数调用上述算法：#include<stdio.h>#include"BTree.cpp"intmain(){BTNode*bt;

ElemTypepath[MaxSize];

CreateBTree(bt,"A(B(D,E(G,H)),C(,F(K)))"); //建立图6.14的二叉链

printf("bt括号表示法:");DispBTree(bt);printf("\n");

printf("解法1:\n");

printf("输出每个叶结点的所有祖先结点:\n");

ancestor1(bt,path,0);

printf("解法2:\n");

printf("输出每个叶结点的所有祖先结点:\n");

ancestor2(bt);DestroyBTree(bt);}6.5二叉树的遍历114/115本程序的执行结果如下：bt括号表示法:A(B(D,E(G,H)),C(,F(K)))解法1:输出每个叶结点的所有祖先结点:D结点的所有祖先结点:BAG结点的所有祖先结点:EBAH结点的所有祖先结点:EBA

K结点的所有祖先结点:FCA解法2:输出每个叶结点的所有祖先结点:D结点的所有祖先结点:BAG结点的所有祖先结点:EBAH结点的所有祖先结点:EBA

K结点的所有祖先结点:FCA6.5二叉树的遍历115/115第6章树和二叉树6.1树6.2二叉树6.3递归算法设计方法6.4二叉树的基本运算算法6.5二叉树的遍历6.6二叉树的构造6.7二叉树与树之间的转换6.8线索二叉树6.9哈夫曼树第6章树和二叉树116/506.6二叉树的构造6.6.1什么是二叉树的构造一棵所有结点值不同的二叉树，其先序、中序、后序和层次遍历都是唯一的。二叉树的构造就是给定某些遍历序列，反过来唯一地确定该二叉树。6.6二叉树的构造117/50

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

二叉树的先序遍历序列为NLR，中序遍历序列为LNR:NLR=LNR则L应为空（因为N为空后其L、R没有意义）。所以这样的二叉树为右单支树（除叶子结点外每个结点只有一个右孩子）。高度为4的满足题目要求的二叉树6.6二叉树的构造118/506.6.2二叉树的构造方法二叉树遍历序列图(a)的二叉树图(b)的二叉树图(c)的二叉树图(d)的二叉树图(e)的二叉树先序遍历序列ABCABCABCABCABC中序遍历序列BACBCAACBCBAABC后序遍历序列BCACBACBACBACBAABCABCABCABCABC(a)(b)(c)(d)(e)6.6二叉树的构造119/50从中看到，对于不同形态的二叉树：先序遍历序列可能相同（图中5棵二叉树的先序遍历序列均相同）。中序遍历序列可能相同。后序遍历序列可能相同（图(b)～(e)的后序遍历序列均相同）先序遍历序列和后序遍历序列可能都相同（图(d)和(e)的先序遍历序列和后序遍历序列均相同）。ABCABCABCABCABC(a)(b)(c)(d)(e)6.6二叉树的构造120/50实际上，对于含2个或者以上结点的二叉树，在先序、中序和后序遍历序列中：由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。6.6二叉树的构造121/50任何n（n≥0）个不同结点的二又树，都可由它的中序序列b和先序序列a唯一地确定。1.由先序遍历序列和中序遍历序列构造一棵二叉树6.6二叉树的构造122/50左子树先序序列，有k个结点右子树先序序列，有n-k-1个结点先序序列：a0

a1

…

ak

ak+1

…

an-1左子树中序序列，有k个结点右子树中序序列，有n-k-1个结点中序序列：b0

b1

…

bk

bk+1

…

bn-1通过根结点a0在中序序列中找到bk由a0（根结点）找到bk。若bk前面有k个结点，则左子树有k个结点，右子树有n-k-1个结点。可以求出左右子树的中序序列和先序序列。这样根结点是确定的，左右子树也是确定的，则该二叉树是确定的。6.6二叉树的构造123/50

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

右先序：空右中序：空

右中序：空根：E左先序：空

右先序：空右中序：空

右中序：空根：F左先序：G右先序：空右中序：G右中序：空根：G左先序：空

右先序：空右中序：空

右中序：空根：B左先序：D右先序：E右中序：D右中序：E根：C左先序：空

右先序：FG右中序：空

右中序：GF6.6二叉树的构造构造该二叉树的过程如下所示。根：A左先序：BDE右先序：CFG右中序：DBE右中序：CGF124/50

任何n（n≥0）个不同结点的二又树，都可由它的中序序列和后序序列唯一地确定。2.由中序遍历序列和后序遍历序列构造一棵二叉树6.6二叉树的构造125/50左子树后序序列，有k个结点右子树后序序列，有n-k-1个结点后序序列：a0

a1…ak-1

ak…an-2

an-1左子树中序序列，有k个结点右子树中序序列，有n-k-1个结点中序序列：b0

b1

…

bk

bk+1

…

bn-1