数据结构教程（C++语言描述）（第3版微课视频版）课件 李春葆 第6-10章 递归 - 排序

第6章

递归6.1什么是递归6.2递归算法的设计CONTENTS提纲6.3递归算法转换为非递归算法1/77在定义一个算法时出现调用本算法的成分，称之为递归。若调用自身，称之为直接递归。若算法A调用算法B，而B又调用A，称之为间接递归。在算法设计中，任何间接递归算法都可以转换为直接递归算法来实现，所以主要讨论直接递归。6.1.1递归的定义6.1什么是递归2/77【例6.1】以下是求n!（n为正整数）的递归算法。它属于什么类型的递归。intfun(intn){if(n==1) //语句1return1; //语句2else //语句3returnfun(n-1)*n; //语句4}直接递归函数。3/77递归算法通常把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解。递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了算法的代码量。原问题小问题1小问题2小问题k…4/77一般来说，能够用递归解决的问题应该满足以下3个条件：需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。递归调用的次数必须是有限的。必须有结束递归的条件来终止递归。5/776.1.2何时使用递归1.定义是递归的

有许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci（斐波那契）数列等。intFib(intn){ //求Fibonacci数列的第n项if(n==1||n==2)return1;elsereturnFib(n-1)+Fib(n-2);}6/772.数据结构是递归的有些数据结构是递归的。如单链表就是一种递归数据结构。template<typenameT>classLinkNode { //单链表结点类public:Tdata;

//存放数据元素LinkNode<T>*next;

//指向下一个结点的指针域LinkNode():next(NULL){} //构造函数

LinkNode(Td):data(d),next(NULL){} //重载构造函数

};head=（a1,head->next）a1an∧a2…headhead->next也是一个单链表不带头结点单链表7/77求一个不带头结点单链表p中所有data成员（假设为int型）之和。示例intSum(LinkNode<int>*p){//求不带头结点单链表p所有结点值之和if(p==NULL)return0;elsereturnp->data+Sum(p->next);}a1an∧a2…pp->next8/773.问题的求解方法是递归的Hanoi问题设Hanoi(n，x，y，z)表示将n个盘片从x塔座借助y塔座移动到z塔座上:Hanoi(n，x，y，z)Hanoi(n-1，x，z，y)；move(n，x，z)：将第n个圆盘从x移到z；Hanoi(n-1，y，x，z)9/77voidHanoi(intn,charx,chary,charz){ //Hanoi递归算法if(n==1) //只有一个盘片的情况printf("将第%d个盘片从%c移动到%c\n",n,x,z);else { //有两个或多个盘片的情况

Hanoi(n-1,x,z,y);printf("将第%d个盘片从%c移动到%c\n",n,x,z);

Hanoi(n-1,y,x,z);}}10/77n=3结束11/776.1.3递归模型递归模型是递归算法的抽象，它反映一个递归问题的递归结构。f(n)=1 n=1f(n)=n*f(n-1) n>1递归模型intfun(intn){if(n==1) //语句1return1; //语句2else //语句3returnfun(n-1)*n; //语句4}12/77f(n)=1 n=1f(n)=n*f(n-1) n>1递归出口递归体一般地，一个递归模型是由递归出口和递归体两部分组成。递归出口确定递归到何时结束，即指出明确的递归结束条件。递归体确定递归求解时的递推关系。13/77递归出口的一般格式如下：递归体的一般格式如下：f(s1)=m1f(sn)=g(f(si)，f(si+1)，…，f(sn-1)，cj，cj+1，…，cm)f(sn)f(si)f(si+1)f(sn-1)…大问题求解若干个相似子问题求解转化非递归函数14/776.1.4递归与数学归纳法采用数学归纳法证明1+2+…+n=n(n+1)/2当n=1时，左式=1，右式=(1×2)/2=1，左右两式相等，等式成立。假设当n=k-1时等式成立，有1+2+…+(k-1)=k(k-1)/2。当n=k时，左式=1+2+…+k=[1+2+…+(k-1)+k=k(k-1)/2+k=k(k+1)/2。先考虑特殊情况。然后假设n=k-1成立（第二数学归纳法是假设n≤k-1均成立），再证明n=k时成立，即假设“小问题”成立，再推导出“大问题”成立。15/77先考虑特殊情况。然后假设n=k-1成立（第二数学归纳法是假设n≤k-1均成立），再证明n=k时成立，即假设“小问题”成立，再推导出“大问题”成立。递归出口递归体递归出口相当于数学归纳法的特殊情况。递归体相当于数学归纳法的归纳步骤。区别：数学归纳法是一种论证方法，递归是算法和程序设计的一种实现技术。数学归纳法是递归求解问题的理论基础。16/77简化的递归模型6.1.5递归的执行过程f(s1)=m1

f(sn)=g(f(sn-1)，cn-1)f(sn)↓

f(sn-1)↓

…↓f(s2)↓f(s1)求f(sn)的分解过程如下：求大问题f(sn)：分解（递推）和求值17/77遇到递归出口发生“质变”，原递归问题便转化成可以直接求解的问题。求值过程：f(s1)=m1↓f(s2)=g(f(s1),c1)↓f(s3)=g(f(s2),c2)↓…↓f(sn)=g(f(sn-1),cn-1)18/77例如求5!。fun(5)fun(4)fun(3)fun(2)fun(1)r返回1fun(2)=2fun(3)=6fun(4)=24fun(5)=120分解过程求值过程19/77系统内部如何执行递归算法一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。

（1）执行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址。

（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址进栈。

（3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。20/77示例例如，有以下程序段：intS(intn){if(n<=0)return0;elsereturnS(n-1)+n;}intmain(){print("%d\n",S(1));return0;}

程序执行时使用一个栈来保存调用过程的信息，这些信息用main()、S(0)和S(1)表示，那么自栈底到栈顶保存的信息的顺序是怎么样呢？21/77main()S(1)S(0)栈顶栈底执行过程：

调用main()

调用S(1)

调用S(0)

从S(0)返回

从S(1)返回

从main()返回intS(intn){if(n<=0)return0;elsereturnS(n-1)+n;}intmain(){print("%d\n",S(1));return0;}22/77用递归算法的形参值表示状态，由于递归算法执行中系统栈保存了递归调用的值参、局部变量和返回地址。所以在递归算法中一次递归调用后会自动恢复该次递归调用前的状态。23/77voidHanoi(intn,charx,chary,charz){ //Hanoi递归算法if(n==1) //只有一个盘片的情况printf("将第%d个盘片从%c移动到%c\n",n,x,z);else { //有两个或多个盘片的情况

Hanoi(n-1,x,z,y);printf("将第%d个盘片从%c移动到%c\n",n,x,z);

Hanoi(n-1,y,x,z);}}

【例6.3】对例6.2的递归算法Hanoi()，给出调用Hanoi(3,a,b,c)时系统栈的变化过程。24/77将第1个盘片从a移动到c将第2个盘片从a移动到b将第1个盘片从c移动到b将第3个盘片从a移动到c将第1个盘片从b移动到a将第2个盘片从b移动到c将第1个盘片从a移动到cHanoi(3,a,b,c)的执行过程输出结果f(3,a,b,c)f(2,a,c,b)3,a→cf(2,b,a,c)f(1,a,b,c)2,a→bf(1,c,a,b)1,a→c1,c→bf(1,b,c,a)2,b→cf(1,a,b,c)1,b→a1,a→cvoidHanoi(intn,charx,chary,charz){ //Hanoi递归算法if(n==1) //只有一个盘片的情况printf("将第%d个盘片从%c移动到%c\n",n,x,z);else { //有两个或多个盘片的情况

Hanoi(n-1,x,z,y);printf("将第%d个盘片从%c移动到%c\n",n,x,z);

Hanoi(n-1,y,x,z);}}25/77执行Hanoi(3,'a','b','c')时系统栈的变化过程3abcnxyz2acb1abc将第1个盘片从a移动到c将第2个盘片从a移动到b将第1个盘片从c移动到b将第3个盘片从a移动到c将第1个盘片从b移动到a将第2个盘片从b移动到c将第1个盘片从a移动到c输出结果：1abcf(3,a,b,c)f(2,a,c,b)3,a→cf(2,b,a,c)f(1,a,b,c)2,a→bf(1,c,a,b)1,a→c1,c→bf(1,b,c,a)2,b→cf(1,a,b,c)1,b→a1,a→c1abc2bac1bca栈空结束26/77【例6.4】有以下递归算法，说明调用f(4)的过程。voidf(intn){ //递归函数if(n==0) //递归出口return;else { //递归体printf("Pre:n=%d\n",n);printf("执行f(%d)\n",n-1);

f(n-1);printf("Post:n=%d\n",n);}}27/77调用f(4)的结果Pre:n=4执行f(3) //递归调用f(3)Pre:n=3执行f(2) //递归调用f(2)Pre:n=2执行f(1) //递归调用f(1)Pre:n=1执行f(0) //递归调用f(0)Post:n=1 //恢复f(0)调用前的n值Post:n=2 //恢复f(1)调用前的n值Post:n=3 //恢复f(2)调用前的n值Post:n=4

//恢复f(3)调用前的n值voidf(intn){ //递归函数if(n==0) //递归出口return;else{ //递归体printf("Pre:n=%d\n",n);printf("执行f(%d)\n",n-1);

f(n-1);printf("Post:n=%d\n",n);}}28/77输出Pre:n=4f(4)f(3)输出Post:n=4输出Pre:n=3f(2)输出Post:n=3输出Pre:n=2f(1)输出Post:n=2输出Pre:n=1f(0)输出Post:n=1调用f(4)的过程29/775.1.6递归算法的时空分析递归算法执行过程不同于非递归算法，所以其时空分析也不同于非递归算法。非递归算法分析是定长时空分析。递归算法分析就是变长时空分析。30/771.递归算法的时间分析执行Hanoi(n,x,y,z)的时间复杂度为O(1)吗？?voidHanoi(intn,charx,chary,charz){ //Hanoi递归算法if(n==1) //只有一个盘片的情况printf("将第%d个盘片从%c移动到%c\n",n,x,z);else{ //有两个或多个盘片的情况Hanoi(n-1,x,z,y);printf("将第%d个盘片从%c移动到%c\n",n,x,z);

Hanoi(n-1,y,x,z);}}31/77设大问题Hanoi(n，x，y，z)的执行时间为T(n)，则小问题Hanoi(n-1，x，y，z)的执行时间为T(n-1)。递推式：T(n)=1 当n=1时T(n)=2T(n-1)+1 当n>1时voidHanoi(intn,charx,chary,charz){ //Hanoi递归算法if(n==1) //只有一个盘片的情况printf("将第%d个盘片从%c移动到%c\n",n,x,z);else { //有两个或多个盘片的情况

Hanoi(n-1,x,z,y);printf("将第%d个盘片从%c移动到%c\n",n,x,z);

Hanoi(n-1,y,x,z);}}32/77T(n)=1 当n=1时T(n)=2T(n-1)+1 当n>1时T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=22T(n-2)+2+1=22(2T(n-3)+1)+2+1=23T(n-3)+22+2+1=…=2n-1T(1)+2n-2+…+22+2+1=2n-1=O(2n)33/772.递归算法的空间分析执行Hanoi(n,x,y,z)的空间复杂度为O(1)吗？?voidHanoi(intn,charx,chary,charz){ //Hanoi递归算法if(n==1) //只有一个盘片的情况printf("将第%d个盘片从%c移动到%c\n",n,x,z);else { //有两个或多个盘片的情况

Hanoi(n-1,x,z,y);printf("将第%d个盘片从%c移动到%c\n",n,x,z);

Hanoi(n-1,y,x,z);}}34/77设大问题Hanoi(n，x，y，z)的占用空间为S(n)，则小问题Hanoi(n-1，x，y，z)的占用空间为S(n-1)。递推式：S(n)=1 当n=1时S(n)=S(n-1)+1 当n>1时voidHanoi(intn,charx,chary,charz){ //Hanoi递归算法if(n==1) //只有一个盘片的情况printf("将第%d个盘片从%c移动到%c\n",n,x,z);else { //有两个或多个盘片的情况

Hanoi(n-1,x,z,y);printf("将第%d个盘片从%c移动到%c\n",n,x,z);

Hanoi(n-1,y,x,z);}}35/77S(n)=S(n-1)+1=S(n-2)+1+1=S(n-2)+2=…=S(1)+(n-1)=1+(n-1)=n

=O(n)S(n)=1 当n=1时S(n)=S(n-1)+1 当n>1时36/77确定问题规模n确定终止情况确定递推情况递推式由递推式求出T(n)/S(n)用复杂度表示T(n)/S(n)递归算法分析37/776.2递归算法的设计6.2.1递归算法设计的步骤设计求解问题的递归模型。转换成对应的递归算法。递归模型递归算法38/77

（1）对原问题f(s)进行分析，称为“大问题”，假设出合理的“小问题”f(s’)；

求递归模型的步骤如下：（3）确定一个特定情况（如f(1)或f(0)）的解

递归出口。（2）假设f(s’)是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s’)之间的关系

递归体。数学归纳法假设n=k-1时等式成立求证n=k时等式成立求证n=1时等式成立39/77【例6.5】采用递归算法求整数数组a[0..n-1]中的最小值。当i=0时，有f(a，i)=a[0]。假设f(a，i-1)已求出，显然有f(a，i)=MIN(f(a，i-1)，a[i])，其中MIN()为求两个值较小值函数。f(a，i)=a[0] 当i=0时f(a，i)=MIN(f(a，i-1)，a[i]) 其他情况假设f(a，i)求数组元素a[0..i]（共i+1个元素）中的最小值。得到递归模型40/77f(a，i)=a[0] 当i=0时f(a，i)=MIN(f(a，i-1)，a[i]) 其他情况intMin(inta[],inti){ //求a[0..i]中的最小值if(i==0) //递归出口returna[0];else { //递归体intmind=Min(a,i-1); //递归调用returnmin(mind,a[i]); //合并}}41/776.2.2基于递归数据结构的递归算法设计递归数据结构的数据特别适合递归处理递归算法种瓜得瓜：递归性数据：D={瓜的集合}运算：Op={种瓜}递归性：Op(x∈D)∈D42/2242/77【例6.6】假设有一个不带头结点的单链表p，完成以下两个算法设计：（1）设计一个算法正向输出所有结点值。（2）设计一个算法反向输出所有结点值。a0an-1∧a1…pp->next大问题：f(p)f(p->next)为什么在这里设计单链表的递归算法时不带头结点？如何将带头结点转换为不带头结点的单链表？43/77a0an-1∧a1…pp->next大问题：f(p)输出a0到an-1f(p->next)输出a1到an-1f(p)

不做任何事件

当p=NULL时f(p)

输出p结点值;f(p->next) 其他情况voidPositive(LinkNode<int>*p){ //正向输出所有结点值if(p==NULL)return;else{printf("%d",p->data);

Positive(p->next);}}(1)正向输出44/77a0an-1∧a1…pp->next大问题：f(p)输出an-1到a0f(p->next)输出an-1到a1f(p)

不做任何事件

当p=NULL时f(p)

f(p->next);输出p结点值

其他情况voidInvert(LinkNode<int>*p){ //反向输出所有结点值if(p==NULL)return;else{

Invert(p->next);printf("%d",p->data);}}(2)反向输出45/77比较voidPositive(LinkNode<int>*p){ //正向输出所有结点值if(p==NULL)return;else{printf("%d",p->data);

Positive(p->next);}}voidInvert(LinkNode<int>*p){ //反向输出所有结点值if(p==NULL)return;else{

Invert(p->next);printf("%d",p->data);}}46/77

【例6.7】假设有一个不带头结点的单链表p，设计一个递归算法逆置该单链表，例如，p->1->2->3->4逆置后为p->4->3->2->1。Reverse(p)的功能是逆置单链表p并返回逆置后单链表的首结点，为大问题。Reverse(p->next)为小问题。47/77a0a1…pan-1∧Reverse(p->next)返回小单链表逆置后的首结点npan-2a1…an-1an-2a0pnp逆置大单链表①p->next->next=pa1…an-1an-2a0∧pnp②p->next=NULL48/77LinkNode<int>*Reverse(LinkNode<int>*p){ //逆置单链表pif(p==NULL) //空表的情况returnNULL;if(p->next==NULL) //只有一个结点的情况returnp;else { //有2个及以上结点的情况LinkNode<int>*np;np=Reverse(p->next); //求解子问题p->next->next=p; //将结点p作为尾结点p->next=NULL;returnnp; //返回逆置单链表的首结点}}49/776.2.3基于归纳方法的递归算法设计通过对求解问题的分析归纳来转换成递归方法求解（如皇后问题等）。关键是对问题本身进行分析，确定大、小问题解之间的关系，构造合理的递归体，而其中最重要的又是假设出“合理”的小问题。50/77【例6.8】若算法pow(x，n)用于计算xn（n为大于1的整数）。完成以下任务：

（1）采用递归方法设计pow(x，n)算法。

（2）问执行pow(x，10)发生几次递归调用？求pow(x,n)对应的算法复杂度是多少？51/77（1）设f(x，n)用于计算xn，则有以下递归模型：f(x，n)=x 当n=1f(x，n)=x*f(x，n/2)*f(x，n/2) 当n为奇数f(x，n)=f(x，n/2)*f(x，n/2) 当n为偶数doublepow(doublex,intn){ //求x的n次幂if(n==1)returnx;doublep=pow(x,n/2);if(n%2==1) //n为奇数returnx*p*p;else //n为偶数returnp*p;}52/77（2）执行pow(x，10)的递归调用顺序是：pow(x，10)→pow(x，5)→pow(x，2)→pow(x，1)

共发生4次递归调用。求pow(x，n)对应的算法复杂度是O(log2n)。53/77【例6.9】创建一个n阶螺旋矩阵并输出。例如，n=4时的螺旋矩阵如下：

1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 754/77设f(x，y，start，n)用于创建左上角为（x，y）、起始元素值为start的n阶螺旋矩阵，共n行n列，它是大问题。f(x+1，y+1，start，n-2)用于创建左上角为（x+1，y+1）、起始元素值为start的n-2阶螺旋矩阵，共n-2行n-2列，它是小问题。12341213145111615610987f(0，0，1，4)为大问题f(1，1，13，2)为小问题55/77对应的递归模型如下：f(x，y，start，n)

不做任何事情

当n≤0f(x，y，start，n)

产生只有一个元素的螺旋矩阵

当n=1f(x，y，start，n)

产生（x，y）的那一圈；

当n>1

f(x+1，y+1，start，n-2)12341213145111615610987f(0，0，1，4)为大问题f(1，1，13，2)为小问题56/77voidSpiral(intx,inty,intstart,intn){ //递归创建螺旋矩阵if(n<=0)return; //递归结束条件if(n==1){ //矩阵大小为1时a[x][y]=start;return;}for(intj=x;j<x+n-1;j++){ //上一行a[y][j]=start;start++;}for(inti=y;i<y+n-1;i++){ //右一列a[i][x+n-1]=start;start++;}for(intj=x+n-1;j>x;j--){ //下一行a[y+n-1][j]=start;start+=1;}for(inti=y+n-1;i>y;i--){ //左一列a[i][x]=start;start++;}

Spiral(x+1,y+1,start,n-2); //递归调用}(x,y)首元素值为start(x,y+n-1)(x+n-1,y)(x+n-1,y+n-1)57/77intmain(){intn=5;Spiral(0,0,1,n);for(inti=0;i<n;i++){for(intj=0;j<n;j++) printf("%3d",a[i][j]);printf("\n");}}程序验证58/77【例6.10】采用递归算法求解迷宫问题，并输出从入口到出口的所有迷宫路径。求解问题描述：

(xi，yi)(xe，ye)mgpath(xi，yi，xe，ye，path)出口mgpath(intxi，intyi，intxe，intye，Boxpath)：求从(xi，yi)到(xe，ye)的迷宫路径，用path变量保存迷宫路径。入口59/77(xi，yi)(xe，ye)mgpath(xi，yi，xe，ye，path)出口大问题入口(i，j)(xi，yi)走一步(xe，ye)mgpath(i,j,xe,ye,path)出口小问题大问题≡走一步+小问题入口60/77mgpath(xi,yi,xe,ye,path)

将(xi,yi)添加到path中;

置mg[xi][yi]=-1;

输出path中的迷宫路径;

恢复出口迷宫值为0即置mg[xe][ye]=0

若(xi,yi)=(xe,ye)即找到出口mgpath(xi,yi,xe,ye,path)

将(xi,yi)添加到path中;

置mg[xi][yi]=-1;

对于(xi,yi)每个相邻可走方块(i,j)，

调用mgpath(i,j,xe,ye,path);

从(xi,yi)回退一步即置mg[xi][yi]=0;

若(xi,yi)不是出口求解迷宫问题的递归模型如下：61/77#include<iostream>#include<vector>usingnamespacestd;constintMAX=10; //迷宫最大的行、列数intdx[]={-1,0,1,0}; //x方向的偏移量intdy[]={0,1,0,-1}; //y方向的偏移量intmg[MAX][MAX]={{0,1,0,0},{0,0,1,1},{0,1,0,0},{0,0,0,0}};intm=4,n=4;intcnt=0; //累计迷宫路径数classBox{

//方块类public:inti; //方块的行号intj; //方块的列号Box(inti1,intj1):i(i1),j(j1){} //重载构造函数};62/77voidmgpath(intxi,intyi,intxe,intye,vector<Box>path){//求解迷宫路径为:(xi,yi)->(xe,ye)Boxb(xi,yi); //建立入口方块的对象bpath.push_back(b); //将b添加的路径path中mg[xi][yi]=-1; //mg[xi][yi]=-1if(xi==xe&&yi==ye){ //找到了出口,输出一个迷宫路径cnt++;printf("迷宫路径%d:",cnt); //输出第cnt条迷宫路径for(intk=0;k<path.size();k++)printf("(%d,%d)",path[k].i,path[k].j);printf("\n");mg[xi][yi]=0; //从出口回退，恢复其mg值return;}63/77else{ //(xi,yi)不是出口intdi=0;while(di<4){ //处理(xi,yi)四周每个相邻方块(i,j)inti=xi+dx[di]; //找(xi,yi)的di方位的相邻方块(i,j)intj=yi+dy[di];if(i>=0&&i<m&&j>=0&&j<n&&mg[i][j]==0)

mgpath(i,j,xe,ye,path);//若(i,j)可走,从(i,j)查找路径di++; //继续处理(xi,yi)的下一个相邻方块}mg[xi][yi]=0;

//(xi,yi)所有相邻方块处理完,回退}}64/77intmain(){intxi=0,yi=0,xe=3,ye=3;printf("(%d,%d)到(%d,%d)的所有迷宫路径\n",xi,yi,xe,ye);vector<Box>path;

mgpath(xi,yi,xe,ye,path);return0;}1032321010323210程序验证65/77

迷宫问题的递归求解与用栈和队列求解有什么异同？66/776.3递归算法转换为非递归算法6.3.1迭代转换法尾递归和单向递归是两种特殊类型的递归，可以采用迭代转换法将它们转换为非递归算法，即将其递归结构用循环结构来替代。尾递归是递归调用语句只有一个，而且是处于算法的最后。单向递归是指执行过程总是朝着一个方向进行的，递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，参数相互之间无关。67/77【例6.11】采用非递归算法求Fibonacci数列。intFib(intn){ //求Fibonacci数列的第n项if(n==1||n==2)return1;elsereturnFib(n-1)+Fib(n-2);}intFib1(intn){ //求Fibonacci数列的非递归算法if(n==1||n==2)return1;inta=1,b=1,c;for(inti=3;i<=n;i++){c=a+b;a=b;b=c;}returnc;}68/776.3.2用栈模拟转换法递归算法是一种分而治之的方法，把“大问题”求解转换为若干个相似“子问题”求解。不能采用迭代转换法的递归算法执行中往往涉及回溯，可以采用栈来保存暂时不能执行的子问题，或者使用栈保存中间结果，称为用栈模拟转换法。用栈模拟转换法的一般框架如下：voidnonrecursive(si) {//非递归算法框架

将大问题状态si进栈;while(栈不为空){

退栈一个元素s;if(s可以直接解决)

直接求该问题解;else{

根据递归过程将s转换为若干个相似子问题的状态sj;

将每个sj进栈;}}}69/77【例6.12】采用非递归算法求Hanoi问题。voidHanoi(intn,charx,chary,charz){ //Hanoi递归算法if(n==1) //只有一个盘片的情况printf("将第%d个盘片从%c移动到%c\n",n,x,z);else { //有两个或多个盘片的情况

Hanoi(n-1,x,z,y);printf("将第%d个盘片从%c移动到%c\n",n,x,z);

Hanoi(n-1,y,x,z);}}70/77当n>1时，需要将Hanoi(n，x，y，z)转换成Hanoi(n-1，x，z，y)、move(n，x，z)、Hanoi(n-1，y，x，z)三步。用一个栈暂时存放Hanoi(n-1，x，z，y)和Hanoi(n-1，y，x，z)两步。栈的特点是先进后出，所以要先将Hanoi(n-1，y，x，z)进栈，后将Hanoi(n-1，x，z，y)进栈。Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)Hanoi(n-1,y,x,z)move(n,x,z)分解顺序进栈顺序71/77structSNode{

//栈元素类型

intn;charx,y,z;boolflag;

//是否可以直接移动SNode(){} //构造函数SNode(intn1,charx1,chary1,charz1,boolf1){ //重载构造函数n=n1;x=x1;y=y1;z=z1;flag=f1;}};这里栈st采用顺序栈，其元素类型定义如下：72/77voidHanoi1(intn,charx,chary,charz){ //Hanoi问题的非递归算法if(n==1){ //只有一个盘片时直接移动cout<<"盘片"<<n<<"从"<<x<<"移动到"<<z<<endl;return;}SNodee,e1,e2,e3;

stack<SNode>st;

//定义一个栈ste=SNode(n,x,y,z,false);st.push(e);73/77Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)Hanoi(n-1,y,x,z)move(n,x,z)分解顺序进栈顺序while(!st.empty()) { //栈不空时循环e=st.top();st.pop(); //出栈元素e,对应任务为Hanoi(n1,x1,y1,z1)boolflag1=e.flag;charx1=e.x,y1=e.y,z1=e.z;intn1=e.n;if(flag1) //该任务可以直接移动cout<<"盘片"<<n1<<"从"<<x1<<"移动到"<<z1<<endl;else{if(n1-1==1)e1=SNode(n1-1,y1,x1,z1,true);elsee1=SNode(n1-1,y1,x1,z1,false);st.push(e1); //Hanoi(n1-1,y1,x1,z1)任务进栈Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)Hanoi(n-1,y,x,z)move(n,x,z)分解顺序进栈顺序74/77e2=SNode(n1,x1,'',z1,true);st.push(e2); //move(n1,x1,z1)任务进栈Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)Hanoi(n-1,y,x,z)move(n,x,z)分解顺序进栈顺序75/77if(n1-1==1)e3=SNode(n1-1,x1,z1,y1,true);elsee3=SNode(n1-1,x1,z1,y1,false);st.push(e3); //Hanoi(n1-1,x1,z1,y1)任务进栈}}}Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)Hanoi(n-1,y,x,z)move(n,x,z)分解顺序进栈顺序76/7777/77第7章树和二叉树7.1树7.2二叉树CONTENTS提纲7.3二叉树先序、中序和后序遍历7.4二叉树的层次遍历7.5二叉树的构造7.6线索二叉树7.8二叉树与树、森林之间的转换7.7哈夫曼树7.9并查集78/44树是由n（n≥0）个结点组成的有限集合（记为T）。如果n=0，它是一棵空树，这是树的特例。如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点（root），其余结点可分为m（m≥0）个互不相交的有限集T1、T2、…、Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。7.1.1树的定义7.1树79/44树是一种非线性数据结构，具有以下特点：每一结点可以有零个或多个后继结点，但有且只有一个前驱结点（根结点除外）。数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。ab<a,b>80/44ADTTree{

数据对象：

D={ai

|0≤i≤n-1，n≥0，ai为E类型}

数据关系：

R={r}r={<ai，aj>|ai，aj∈D，0≤i，j≤n-1，其中每个结点最多只有

一个前驱结点、可以有零个或多个后继结点，有且仅有

一个结点即根结点没有前驱结点}

基本运算：CreateTree()：由树的逻辑结构表示建立其存储结构。DispTree()：输出树的括号表示串。EGetParent(inti)：求编号为i的结点的双亲结点值。

…}抽象数据类型树的描述81/447.1.2树的逻辑结构表示方法树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。ACGJBEDFIHMKL82/44文氏图表示法。使用集合以及集合的包含关系描述树结构。ACGJBEDFIHMKL83/44凹入表示法。使用线段的伸缩关系描述树结构。ACGJBEDFIHMKL84/44括号表示法。将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号分隔。A(B(E,F),C(G(J)),D(H,I(K,L,M)))根(子树1，子树2，…，子树m）ACGJBEDFIHMKL85/447.1.3树的基本术语度为3度为2结点的度。树中每个结点具有的子树数或者后继结点数称为该结点的度。ACGJBEDFIHMKL86/44树的度。树中所有结点的度的最大值称之为树的度。树的度为3ACGJBEDFIHMKL87/44分支结点。度大于0的结点称为分支结点或非终端结点。度为1的结点称为单分支结点，度为2的结点称为双分支结点，依次类推。A、B、C、D、G、I为分支结点ACGJBEDFIHMKL88/44叶子结点（或叶结点）。度为零的结点称为叶子结点或终端结点。E、F、J、H、K、L、M为叶子结点ACGJBEDFIHMKL89/44孩子结点。一个结点的后继称之为该结点的孩子结点。结点A的孩子结点为B、C和DACGJBEDFIHMKL90/44双亲结点（或父亲结点）。一个结点称为其后继结点的双亲结点。结点E和F的双亲结点均为BACGJBEDFIHMKL91/44子孙结点。一个结点的子树中除该结点外的所有结点称之为该结点的子孙结点。结点D结点的子孙结点为H、I、K、L、MACGJBEDFIHMKL92/44祖先结点。从树根结点到达某个结点的路径上通过的所有结点称为该结点的祖先结点（不含该结点自身）。结点K的祖先结点为A、D、IACGJBEDFIHMKL93/44兄弟结点。具有同一双亲的结点互相称之为兄弟结点。结点K、L、M是兄弟结点ACGJBEDFIHMKL94/44结点层次。树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次。1234ACGJBEDFIHMKL95/44树的高度。树中结点的最大层次称为树的高度或深度。高度是41234ACGJBEDFIHMKL96/44森林。零棵或多棵互不相交的树的集合称为森林。ABCDEFHG4棵树构成的森林97/447.1.4树的性质性质1：树中的结点数等于所有结点的度数加1。度之和=分支数分支数=n-1所以，n=度之和+1ABCDEFHG98/44性质2：度为m的树中第i层上至多有mi-1个结点，这里应有i≥1。数学归纳法证明当一棵m次树的第i层有mi-1个结点（i≥1）时，称该层是满的，若一棵m次树的所有叶子结点在同一层且每一层都是满的，称为满m次树。显然，满m次树是所有相同高度的m次树中结点总数最多的树。也可以说，对于n个结点，构造的m次树为满m次树或者接近满m次树，此时树的高度最小。推广99/44性质3：

高度为h的m次树至多有个结点。由性质2推出100/44性质4：具有n个结点的m次树的最小高度为

logm(n(m-1)+1)

。

证明：设具有n个结点的m次树的最小高度为h，若在该树中前h-1层都是满的，即每一层的结点数都等于mi-1个（1≤i≤h-1），第h层（即最后一层）的结点数可能满，也可能不满，则该树具有最小的高度。其高度h可计算如下：h层全满高度为h，结点个数最多的情况h-1层满高度为h，结点个数最少的情况+1101/44根据树的性质3可得：<

n≤乘(m-1)后得：

mh-1<n(m-1)+1≤

mh以m为底取对数后得：

h-1<logm(n(m-1)+1)≤

h即 logm(n(m-1)+1)≤

h<logm(n(m-1)+1)+1因h只能取整数，所以h=

logm(n(m-1)+1)

，结论得证。102/44

【例7.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。103/447.1.5树的基本运算树的运算主要分为三大类：查找满足某种特定关系的结点，如寻找当前结点的双亲结点等；插入或删除某个结点，如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；遍历树中每个结点。104/44树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。有以下3种遍历方法：先根遍历后根遍历层次遍历105/44先根遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。层次遍历:若树不空，则自上而下自左至右访问树中每个结点。先根和后根遍历算法都是递归的。注意106/44ABCDEFGHJIK先根遍历的顶点访问次序：ABEFCDGHIJK后根遍历的顶点访问次序：EFBCIJKHGDA层次遍历的顶点访问次序：ABCDEFGHIJK107/447.1.6树的存储结构1.双亲存储结构

这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。structPNode{ //双亲存储结构元素类型

chardata;

//存放结点值,假设为char类型intparent; //存放双亲索引PNode(chard,intp){ //构造函数data=d;parent=p;}};vector<PNode>t; //树的双亲存储结构108/44位置dataparent0A-11B02C03D14E15F16G4ABCFDEG109/44双亲存储结构：利用了每个结点（根结点除外）只有唯一双亲的性质。这种存储结构中，求某个结点的双亲结点十分容易，但求某个结点的孩子结点时需要遍历整个结构。优缺点110/44

【例7.2】若一棵树采用双亲存储结构t存储，设计一个算法求指定索引是i的结点的层次。intLevel(vector<PNode>t,inti){ //求t中索引i的结点的层次if(i<0||i>=t.size()) //参数错误返回0return0;intcnt=1;while(t[i].parent!=-1){ //没有到达根结点时循环cnt++;i=t[i].parent; //移动到双亲结点}returncnt;}111/44ABCFDEGit[i].parent2.孩子链存储结构每个结点包含结点值和所有孩子结点的指针，可按一个结点的度设计结点的孩子结点指针域个数。所有孩子结点指针用vector向量存储。ABCFDEGABCDEGF112/44孩子链存储结构的结点类型SonNode定义如下：structSonNode { //孩子链存储结构结点类

chardata;

//存放结点值,假设为char类型vector<SonNode*>sons; //指向孩子结点指针的向量SonNode(){} //构造函数SonNode(chard):data(d){} //重载构造函数};113/44ABCDEGF优点是查找某结点的孩子结点十分方便。缺点是查找某结点的双亲结点比较费时。优缺点114/44孩子链存储结构【例7.3】若一棵树采用孩子链存储结构t存储，设计一个算法求其高度。一棵树的高度为根的所有子树高度的最大值加1。求整棵树的高度为“大问题”，求每棵子树高度为“小问题”。设f(t)为求树t的高度，对应的递归模型如下：两棵子树的高度分别为3和1，树t的高度=max(3,1)+1=4ABCDEGFtt->sons[0]t->sons[1]115/44intHeight(SonNode*t){ //求t的高度if(t==NULL) //空树高度为0return0;intmaxsh=0;for(inti=0;i<t->sons.size();i++){ //遍历所有子树intsh=Height(t->sons[i]); //求子树t->sons[i]的高度maxsh=max(maxsh,sh); //求所有子树的最大高度}returnmaxsh+1;}两棵子树的高度分别为3和1，树t的高度=max(3,1)+1=4ABCDEGFtt->sons[0]t->sons[1]116/443.长子兄弟链存储结构

长子兄弟链存储结构是为每个结点设计三个域：一个数据元素域，一个指向该结点的长子的指针域，一个指向该结点的下一个兄弟结点指针域。ABCFDEGA∧BD∧G∧C∧∧EF∧∧117/44长子兄弟链存储结构中结点类型EBNode定义如下：structEBNode{

//长子兄弟链中结点类

chardata;

//结点的值

EBNode*brother;

//指向兄弟

EBNode*eson;

//指向长子结点EBNode():brother(NULL),eson(NULL){} //构造函数EBNode(chard){ //重载构造函数data=d;brother=eson=NULL;} };118/44A∧BD∧G∧C∧∧EF∧∧优点是查找某结点的孩子结点十分方便。缺点是查找某结点的双亲结点比较费时。优缺点119/44长子兄弟链存储结构【例7.4】若一棵树采用长子兄弟链存储结构t存储，设计一个算法求其高度。

一棵树的高度为根的所有子树高度的最大值加1。求整棵树的高度为“大问题”，求每棵子树高度为“小问题”。设f(t)为求树t的高度，对应的递归模型如下：A∧BD∧G∧∧C∧∧EF∧∧两棵子树的高度分别为3和1，树t的高度=max(3,1)+1=4brotheresont120/44intHeight(EBNode*t){ //求t的高度if(t==NULL)return0; //空树高度为0intmaxsh=0;EBNode*p=t->eson; //p指向t结点的长子while(p!=NULL){EBNode*q=p->brother; //q临时保存结点p的兄弟结点intsh=Height(p); //递归求结点p的子树的高度maxsh=max(maxsh,sh); //求结点t的所有子树的最大高度p=q;}returnmaxsh+1;}A∧BD∧G∧∧C∧∧EF∧∧两棵子树的高度分别为3和1，树t的高度=max(3,1)+1=4brotheresont121/44二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树中许多概念与树中的概念相同。在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结点个数，n1表示单分支结点个数，n2表示双分支结点个数。7.2.1二叉树的概念7.2二叉树1.二叉树的定义122/49度为2的树至少有3个结点，而二叉树的结点数可以为0。度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。提示二叉树与度为2的树是不同的。123/49归纳起来，二叉树的5种形态：Ø(a)空二叉树(b)只有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树非空的二叉树124/492.二叉树抽象数据类型的描述125/49ADTBT