数据结构简明教程（第3版）课件 第5、6章 数组和稀疏矩阵、树和二叉树

第5章数组和稀疏矩阵5.1数组4.2特殊矩阵的压缩存储5.3稀疏矩阵第5章数组和稀疏矩阵1/375.1数组5.1.1数组的定义一维数组是n（n>1）个相同性质的数据元素a1，a2，…，an构成的有限序列，它本身就是一个线性表。二维数组可以看成是这样的一个线性表，它的每个数据元素也是一个线性表。

5.1数组2/37例如，以下的二维数组A以m行n列的矩阵形式表示，它可以看成是一个线性表的线性表：A=(A1，A2，…，Ai，…，Am)其中每个数据元素Ai也是一个线性表：Ai=(ai,1，ai,2，…，ai,n)5.1数组3/37通常数组的基本运算主要有：存元素值取元素值5.1数组4/37几乎所有的高级程序设计语言都实现了数组数据结构，称为数组类型。在C/C++语言中，数组类型具有如下特点：一个数组中所有元素具有相同的数据类型。数组一旦被定义，它的维数和每维大小就不再改变。数组中每个元素对应唯一的下标，可以通过该下标对元素进行存取操作。5.1数组5/375.1.2数组的存储结构以二维数组为例，在C/C++语言中，由于数组下标从0开始，所以除特别指出外，后面的数组表示均统一为下标从0开始。5.1数组6/37二维数组的存储次序有按行优先和按列优先两种方式。按行优先存储a0,0

a0,1…a0,n-1

a1,0

a1,1…a1,n-1…am-1,0

am-1,1…am-1,n-1第0行第1行第m-1行5.1数组7/37对于元素ai,j，其存储地址为：a0,0

a0,1…a0,n-1…ai,0…ai,j

…ai,n-1…第0行第i行LOC(ai,j)=LOC(a0,0)+(i*n+j)*k每个元素占k个存储单元ai,j前面有0～i-1共i行，每行n个元素，共有i*n个元素在第i行中，ai,j前面j个元素5.1数组8/37按列优先存储a0,0

a1,0…am-1,0

a0,1

a1,1…an-1,1…a0,n-1

a1,n-1…am-1,n-1第0列第1列第n-1列5.1数组9/37对于元素ai,j，其存储地址为：a0,0

a1,0…am-1,0…a0,j…ai,j

…an-1,j…第0列第j列LOC(ai,j)=LOC(a0,0)+(j*m+i)*k每个元素占k个存储单元ai,j前面有0～j-1共j列，每列m个元素，共有j×m个元素在第j列中，ai,j前面i个元素5.1数组10/37

【例5.1】对于二维数组A[0..2][0..5]，当按行优先存储时，元素A[2][3]是第几个元素；

当按列优先存储时，元素A[2][4]是第几个元素。

解：这里m=3，n=6。

当按行优先存储时，元素A[2][3]的前面有2行计12个元素，在第2行中前面有3个元素，所以元素A[2][3]是12+3+1=16个元素。当按列优先存储时，元素A[2][4]的前面有4列计12个元素，在第4列中前面有2个元素，所以元素A[2][4]是12+2+1=15个元素。5.1数组11/375.1.3数组的算法设计示例【例5.2】设计一个算法，实现一个m×n的整型数组A的转置运算。voidTransMat(intA[][MAX],intB[][MAX],intm,intn){inti,j;

for(i=0;i<m;i++) for(j=0;j<n;j++)

B[j][i]=A[i][j];}

解：对于一个m×n的数组Am×n，其转置矩阵是一个n×m的矩阵Bn×m，且B[i][j]=A[j][i]，0≤i<m，0≤j<n。5.1数组12/375.2特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。为了节省存储空间，特别是在高阶矩阵的情况下，可以利用特殊矩阵的规律，对它们进行压缩存储。5.2特殊矩阵的压缩存储13/37一个n阶方阵的元素可以分为主对角线、上三角和下三角部分1.对称矩阵的压缩存储若一个n阶方阵A[n][n]的元素满足ai,j=aj,i（0≤i，j≤n-1），则称其为n阶对称矩阵。5.2特殊矩阵的压缩存储14/37由于对称矩阵中的元素关于主对角线对称，因此在存储时可只存储对称矩阵中上三角+对角线或下三角+对角线中的元素，使得对称的元素共享一个存储空间。这样，就可以将n2个元素压缩存储到n(n+1)/2个元素的空间中。不失一般性，以行序为主序存储其下三角+对角线的元素。5.2特殊矩阵的压缩存储15/37B={bk}第0行有1个元素第1行有2个元素…第i-1行有i个元素在第i行中，元素ai,j的前面亦有j个元素k=

i(i+1)/2+j5.2特殊矩阵的压缩存储16/37则A中任一元素ai,j和bk之间存在着如下对应关系：对于A中上三角部分元素ai,j（i<j），它的值等于aj,i，而aj,i元素在B中的存储位置k=j(j+1)/2+i。5.2特殊矩阵的压缩存储17/372.三角矩阵的压缩存储所谓n阶下（上）三角矩阵，是指矩阵的上（下）三角（不包括对角线）中的元素均为常数c的n阶方阵。设以一维数组B[0..n(n+1)/2]作为n阶三角矩阵A的存储结构。5.2特殊矩阵的压缩存储18/37上三角矩阵：下三角矩阵：其中，B的元素bn(n+1)/2中存放常数c。5.2特殊矩阵的压缩存储19/373.对角矩阵的压缩存储若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称其为n阶对角矩阵。其主对角线上下方各有b条次对角线，称b为矩阵半带宽。5.2特殊矩阵的压缩存储20/37

对于b=1的三对角矩阵A，只存储其非零元素，并按行优先存储到一维数组B中，将A的非零元素ai,j存储到B的元素bk中：

k=2i+j

5.2特殊矩阵的压缩存储21/375.3稀疏矩阵一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时，即s<<t时，称该矩阵为稀疏矩阵。例如一个100×100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。稀疏矩阵的压缩存储方法是只存储非零元素，主要有三元组和十字链表两种方法。5.3稀疏矩阵22/375.3.1稀疏矩阵的三元组表示由于稀疏矩阵中非零元素的分布没有任何规律，所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标。这样稀疏矩阵中的每一个非零元素需由一个三元组（i,j,ai,j）唯一确定，稀疏矩阵中的所有非零元素构成三元组线性表。5.3稀疏矩阵23/37((0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4))5.3稀疏矩阵24/37三元组顺序表的数据结构可定义如下：#defineMaxSize100 //矩阵中非零元素的最多个数typedefstruct{intr; //行号

intc; //列号

ElemTyped;

//元素值为ElemType类型}TupNode; //三元组定义typedefstruct{introws; //行数

intcols; //列数

intnums; //非零元素个数

TupNode

data[MaxSize];}TSMatrix; //三元组顺序表定义5.3稀疏矩阵25/37（1）从一个二维稀疏矩阵创建其三元组表示以行序方式扫描二维稀疏矩阵A，将其非零的元素插入到三元组t中。voidCreatMat(TSMatrix&t,ElemTypeA[M][N]){inti,j;

t.rows=M;t.cols=N;t.nums=0;

for(i=0;i<M;i++)

{for(j=0;j<N;j++)

if(A[i][j]!=0) //只存储非零元素

{

t.data[t.nums].r=i;t.data[t.nums].c=j;

t.data[t.nums].d=A[i][j];t.nums++;

}

}}5.3稀疏矩阵26/37（2）三元组元素赋值对于稀疏矩阵A，执行A[i][j]=x。intValue(TSMatrix&t,ElemTypex,inti,intj){intk=0,k1;

if(i>=t.rows||j>=t.cols)return0; //参数错误

while(k<t.nums&&i>t.data[k].r)k++; //查找行while(k<t.nums&&i==t.data[k].r&&j>t.data[k].c)k++;

//查找列if(t.data[k].r==i&&t.data[k].c==j) //存在元素t.data[k].d=x;

else

//不存在这样的元素时插入一个元素

{for(k1=t.nums-1;k1>=k;k1--)

{t.data[k1+1].r=t.data[k1].r;

t.data[k1+1].c=t.data[k1].c;

t.data[k1+1].d=t.data[k1].d;

}

t.data[k].r=i;t.data[k].c=j;t.data[k].d=x;t.nums++;

}

return1; //成功时返回1}5.3稀疏矩阵27/37（3）将指定位置的元素值赋给变量

对于稀疏矩阵A，执行x=A[i][j]。intAssign(TSMatrixt,ElemType&x,inti,intj){intk=0;

if(i>=t.rows||j>=t.cols)return0;

//参数错误

while(k<t.nums&&i>t.data[k].r)k++; //查找行

while(k<t.nums&&i==t.data[k].r&&j>t.data[k].c)k++; //查找列

if(t.data[k].r==i&&t.data[k].c==j) x=t.data[k].d;

else x=0; //在三元组中没有找到表示是零元素

return1; //成功时返回1}5.3稀疏矩阵28/37（4）输出三元组运算算法从头到尾扫描三元组t，依次输出元素值。voidDispMat(TSMatrixt){inti;

if(t.nums<=0) //没有非零元素时返回return;

printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);

printf("\t------------------\n");

for(i=0;i<t.nums;i++)printf("\t%d\t%d\t%d\n", t.data[i].r,t.data[i].c,t.data[i].d);}5.3稀疏矩阵29/37

【例5.4】一个稀疏矩阵采用三元组表示压缩存储后，和直接采用二维数组存储相比会失去（）特性。A.顺序存储

B.随机存取

C.输入输出 D.以上都不对5.3稀疏矩阵30/375.3稀疏矩阵5.3.2稀疏矩阵的十字链表表示31/37对于稀疏矩阵中每个非零元素创建一个结点存放它，包含元素的行号、列号和元素值。这里有4个非零元素，创建4个数据结点。将同一行的所有结点构成一个带头结点的循环单链表，行号为i的单链表的头结点为hr[i]。这里有3行，对应有3个循环单链表，头结点分别为hr[0]～hr[2]。hr[i]（0≤i≤2）头结点的行指针指向行号为i的单链表的首结点。5.3稀疏矩阵32/37将同一列的所有结点构成一个带头结点的循环单链表，列号为j的单链表的头结点为hd[j]。这里有4列，对应有4个循环单链表，头结点分别为hd[0]～hd[3]。hd[j]（0≤j≤3）头结点的列指针指向列号为j的单链表的首结点。5.3稀疏矩阵33/37由此，创建了3+4=7个循环单链表，头结点个数也为7个。实际上，可以将hr[i]和hd[i]合起来变为h[i]，即h[i]同时包含有行指针和列指针。h[i]（0≤i≤2）头结点的行指针指向行号为i的单链表的首结点，h[i]（0≤i≤3）头结点的列指针指向列号为i的单链表的首结点，这样，头结点的个数为MAX{3，4}=4个。5.3稀疏矩阵34/37再将所有头结点h[i]（0≤i≤3）链起来构成一个带头结点的循环单链表，这样需要增加一个总头结点hm。总头结点中存放稀疏矩阵的行数和列数等信息。5.3稀疏矩阵35/375.3稀疏矩阵36/37十字链表结点结构和头结点合起来声明的结点类型如下：#defineM3 //矩阵行数#defineN4 //矩阵列数#defineMax((M)>(N)?(M):(N)) //矩阵行列中较大者typedefstructmtxn{inti; //行号intj; //列号structmtxn*right,*down; //向右和向下的指针union{ElemTypevalue; //存放非零元素值structmtxn*link;}tag;}MatNode; //十字链表类型定义5.3稀疏矩阵37/37第6章树和二叉树6.1树6.2二叉树6.3递归算法设计方法6.4二叉树的基本运算算法6.5二叉树的遍历6.6二叉树的构造6.7二叉树与树之间的转换6.8线索二叉树6.9哈夫曼树第6章树和二叉树38/1156.1树6.1.1树的定义从数据结构角度看，树包含n（n≥0）个结点，当n=0时，称为空树；非空树的定义如下：

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

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

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

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

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

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

【例6.1】若一棵三次树中度为3的结点为2个，度为2的结点为1个，度为1的结点为2个，则该三次树中总的结点个数和度为0的结点个数分别是多少？6.1树62/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树63/1156.1.5树的基本运算树的运算主要分为三大类：查找满足某种特定关系的结点，如寻找当前结点的双亲结点等；插入或删除某个结点，如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；遍历树中结点。6.1树64/115

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

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

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

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

【例6.3】给出由3个结点A、B和C构成的所有形态的二叉树（不考察结点值的差异）。解：含有3个结点A、B和C的所有形态的二叉树：ABCABCABCABCABC6.2二叉树74/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二叉树75/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二叉树76/115性质2非空二叉树上第i层上至多有2i-1个结点，这里应有i≥1。

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

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

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

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

（1）若i≤

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

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

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

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

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

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

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

//数据域

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

B

∧D∧

E

∧G∧

∧H∧

∧C

F∧

∧K∧

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

【例6.8】对于不带头结点的非空单链表L（结点类型用SLinkNode表示），其结点值均为整数，设计以下递归算法：（1）求最大的结点值；（2）求最小的结点值；（3）正向输出所有结点值；（4）反向输出所有结点值。a1a2an∧…LL->nextf(L->next)f(L)6.3递归算法设计方法104/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递归算法设计方法105/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递归算法设计方法106/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递归算法设计方法107/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递归算法设计方法108/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递归算法设计方法109/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递归算法设计方法110/1156.3.3二叉树的递归算法设计递归算法设计便是从递归数据结构的基本递归运算入手的。对于二叉树，以二叉链为存储结构，其基本递归运算就是求一个结点p的左子树（p->lchild）和右子树（p->rchild）。p->lchild和p->rchild一定是一棵二叉树（这是为什么二叉树的定义中空树也是二叉树的原因）。6.3递归算法设计方法111/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递归算法设计方法112/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。113/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二叉树的基本运算算法114/1156.4.2二叉树基本运算实现算法本小节采用二叉链存储结构，讨论二叉树基本运算算法。（1）创建二叉树CreateBTree(bt,str)

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

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

inttop=-1,k,j=0;

charch;

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

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

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

PreOrder(bt->lchild);

PreOrder(bt->rchild);

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

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

InOrder(bt->rchild);

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

{ PostOrder(bt->lchild);

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

}}后序遍历序列的特点：最后一个元素值为二叉树中根结点值。3．后序遍历6.5二叉树的遍历128/115层次遍历是从根结点出发，按照从上向下，同一层从左向右的次序访问所有的结点。采用层次遍历得到的访问结点序列称为层次遍历序列。层次遍历序列的特点：其第一个元素值为二叉树中根结点值。4.层次遍历算法6.5二叉树的遍历129/115在层次遍历算法中采用一个循环队列qu来实现。层次遍历算法的实现过程：先将根结点进队，在队不空时循环：从队列中出队一个结点p，访问它；若它有左孩子结点，将左孩子结点进队；若它有右孩子结点，将右孩子结点进队。如此操作直到队空为止。6.5二叉树的遍历130/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二叉树的遍历131/1156.5.2遍历算法的应用

【例6.9】假设以二叉链作为存储结构，设计一个算法求二叉树中单分支结点个数。采用后序递归遍历方式求解。6.5二叉树的遍历空树返回0.先求出左子树中单分支结点个数m，再求出右子树中单分支结点个数n。若根结点是单分支结点，则返回m+n+1，否则返回m+n。132/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二叉树的遍历133/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二叉树的遍历134/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