数据结构电子课件教案-第6章-二叉树与递归.ppt

1,栈、递归、树,1递归基本概念2用二叉树分析递归程序的执行过程3递归程序的执行过程4递归消除5二叉树遍历的非递归算法,栈、递归程序（递归算法）、二叉树和树的遍历有着紧密的联系，这一节，将就这些有关内容进行阐述,2,1递归基本概念,递归在计算机科学和数学中是一个很重要的工具，它在程序设计语言中用来定义句法，在数据结构中用来解决表或树形结构的遍历和排序等问题。数学家在研究组合问题时用到递归。递归是一个重要的课题，在计算方法、运筹学模型、行为策略和图论研究中，从理论到实践，都得到广泛的应用,3,定义：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的，若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。,在以下三种情况下，常常要用到递归的方法数学函数的定义是递归的数据结构是递归的问题的解法是递归的(分治的),从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事：从前有座山，,4,数学函数的定义是递归的,菲波那契函数,阿克曼函数,阶乘函数,5,数据结构是递归的链表可以递归定义，链表使用递归定义，其算法设计会比较简单(思考：如何对链表进行递归定义？如何设计递归算法？)树是递归定义的,6,问题的解法是递归的：有些问题用递归的方法求解比较方便，典型的便子：hanoi塔问题8皇后问题迷宫问题快速排序、归并排序方法树的遍历,7,递归问题特点对于一个较为复杂的问题，如果能够分解成几个相对简单的且解法相同或类似的子问题时，只要解决了这些子问题，那么原问题就迎刃而解了，这就是递归求解。这种分解-求解的策略叫做“分治法”。当分解后的子问题可以直接解决时，就停止分解。我们把这些可以直接求解的问题叫做递归终止条件。任何递归问题都必须有递归终止条件。有些问题可以先设计出递归算法，然后为了提高运行效率，再将递归算法变换成非递归算法,8,2.用二叉树分析递归程序执行过程,#includeintF(intn)intf,r;if(n=1)return1;elser=F(n-1);f=n*r;returnf;/main()y=F(5);coutn=ny=y;,F(5),F(4),F(3),F(2),F(1),后序遍历,9,#includevoidfun(intn,int*s)intf1,f2;if(n=1|n=2)*s=1;elsefun(n-1,voidmain()intx;fun(4,程序输出的第一行是第二行是：最后一行是：,1,14,1x=10,写出下列程序的输出结果,10,例Hanoi问题(以3个盘子为例),B,C,A,A、B、C三个柱子，A柱上有n个大小不一的盘子，盘子由大到小从下到上放置，要求将A柱上的盘子移到C柱上，要求如下：一次只能移动一只盘子；可以借助三根柱子，但任何时候都不允许大盘子在小盘子上面。,11,#includevoidmove(intn,charx,chary)coutn:xyendl;/voidhanoi(intn,charA,charB,charC)if(nn;coutB1:C-B3:A-C1:B-A2:B-C1:A-C,voidhanoi(intn,charA,charB,charC)if(nC2:A-B1:C-B3:A-C1:B-A2:B-C1:A-C,14,3递归算法,课后练习与讨论用递归方法实现单链表的基本操作插入（创建）删除遍历逆置排序递归插入排序递归选择排序,15,实现函数调作的基本设施栈阶乘函数递归调用栈的变化,4递归程序的执行过程,16,一般的函数调用,说明每调用函数一次，在内存栈区分配空间，用于存放函数形式参数、局部变量、返回值、返回地址等信息。,intf(intx)inty,z;z=f1(y);.return(2*z);,17,下一条要执行的语句,函数调用栈,intf(intx)inty,z;z=f1(y);.return(2*z);,18,例求n的阶乘(取n=5),#includelongfac(intn)intf;if(n=1)f=1;elsef=n*fac(n-1);return(f);main()intn,longy;cinn;y=factorial(n);coutn=ny=lchild;push(S,p);,while(p)push(S,p);p=p-lchild;,22,A,C,P=NULL,B,D,E,E,G,G,D,F,F,A,pop(S,p);visit(p);p=p-rchild;,while(p)push(S,p);p=p-lchild;,23,p=T;push(S,P);p=lchild;push(S,p);p=p-lchild;push(S,p);,while(p)push(S,p);p=p-lchild;,pop(S,p);visit(p);p=p-rchild;,while(),p|StackEmpty(),24,voidInorderTraverse(BiTreeT,(*visit)(ETypee)IniStack(S);p=T;while(p|!StackEmpty(S)while(p)/向左走到尽头push(S,p);p=p-lchild;pop(S,p);/空指针，退栈visit(p);/处理节点p=p-rchild;/进入右分支,中序遍历非递归算法,25,voidPreorderTraverse(BiTreeT,(*visit)(ETypee)IniStack(S);p=T;while(p|!StackEmpty(S)while(p)/向左走到尽头visit(p);/处理节点push(S,p);p=p-lchild;pop(S,p);/空指针，退栈p=p-rchild;/进入右分支,前序遍历非递归算法,26,voidPostorderTraverse(BiTreeT,(*visit)(ETypee)IniStack(S);p=T;while(p|!StackEmpty(S)while(p)/向左走到尽头push(S,p);p=p-lchild;q=NULL;flag=1;while(flag/while,后序遍历非递归算法,27,另一种非递归遍历方法（数据结构定义）,Typedefenumbypass=1,visit=0TasktypestructSlemBtnode*p;Tasktypetask;,28,另一种非递归遍历方法（中序）,voidInOrder_iter(BiTreeBT)Eleme;StackS(30);e.p=BT;e.task=bypass;/e为栈元素if(BT)Push(S,e);/布置初始任务while(!StackEmpty(S)/每次处理一项任务Pop(S,e);if(e.task=visit)visit(e.p);/处理访问任务elseif(e.p)/处理非空树的遍历任务p=e.p;e.p=p-rchild;e.task=bypass;Push(S,e);/右孩子进栈e.p=p;e.task=visit;Push(S,e);/本节点（根）进栈e.p=p-lchild;e.task=bypass;Push(S,e);/左孩子进栈/if/while/InOrder_iter,29,另一种非递归遍历方法(前序),voidPreOrder_iter(Btnode*BT)Sleme;StackS(30);e.p=BT;e.task=bypass;/e为栈元素if(BT)Push(S,e);/布置初始任务while(!StackEmpty(S)/每次处理一项任务Pop(S,e);if(e.task=visit)visit(e.ptr);/处理访问任务elseif(e.p)/处理非空树的遍历任务p=e.p;e.p=p-rchild;e.task=bypass;Push(S,e);/右孩子进栈e.p=p-lchild;e.task=bypass;Push(S,e);/左孩子进栈e.p=p;e.task=visit;Push(S,e);/根进栈/if/while/InOrder_iter,30,另一种非递归遍历方法(后序),voidPostOrder_iter(BiTreeBT)Sleme;StackS(30);e.p=BT;e.task=bypass;/e为栈元素if(BT)Push(S,e);/布置初始任务while(!S.Empty(S)/每次处理一项任务Pop(S,e);if(e.task=visit)visit(e.ptr);/处理访问任务elseif(e.p)/处理非空树的遍历任务p=e.p;e.p=p;e.task=visit;Push(S,e);/根进栈e.p=p-rchild;e.task=bypass;Push(S,e);/右孩子进栈e.p=p-lchild;e.task=bypass;Push(S,e);/左孩子进栈/if/while/InOrder_iter,31,6.5.4递归消除,递归算法通常具有非常清晰的结构。而且大多数递归算法都具有超常的功能。善于阅读和设计递归算法对计算机科学和技术专业的学生是至关重要的。有两个原因要研究递归算法的非递归化对于递归算法往往其难理解其内部工作过程。递归算法的时间效率和空间效率往往都不尽人意,递归程序的几种基本形式尾递归消除方法一般递归消除方法,32,递归程序的几种基本形式,intfunc()if(不满足递归终止条件)func(),简单前序递归（尾递归）,33,递归程序的几种基本形式,intfunc()if(不满足递归终止条件)func(),简单后序递归,34,递归程序的几种基本形式,intfunc()if(不满足递归终止条件)func()func(),双重递归（前序）,35,递归程序的几种基本形式,intfunc()if(不满足递归终止条件)func()func(),双重递归（中序）,36,递归程序的几种基本形式,intfunc()if(不满足递归终止条件)func()func(),双重递归（后序）,37,递归的本质,voidfunc(p1,p2,pm)if(cond(p1,p2,pm)return;elsevisit1(p1,p2,pm);func(f(p1,p2,pm);visit2(p1,p2,pm);,38,递归的本质,voidfunc(p1,p2,pm)if(cond(p1,p2,pm)return;while(!cond(p1,p2,pm)visit1(p1,p2,pm);push(f(p1,p2,pm);while(!StackEmpty(S)pop(f(p1,p2,pm);visit2(p1,p2,pm);,39,简单前序递归（尾递归）消除,intfunc()if(不满足递归终止条件)func(),尾递归的递归调用语句只有一个，而且是放在程序的最后。当递归调用返回时，返回到上一层递归调用语句的下一语句，这个位置正好是程序的末尾，因此，不必利用递归工作栈保存返回地址，而且除了返回值和引用值外，其它的参数和局部变量值都不再需要保留，因此可以不用栈，直接用循环形式写非递归过程，从而提高程序的执行效率。,40,/尾递归循环实现voidrecfun(intA,intn)while(n=0)cout;n-;,/尾递归函数voidrecfun(intA,intn)if(n=0)cout;recfun(n-1);,41,简单后序递归,intfunc()if(不满足递归终止条件)func(),这种形式的递归程序要实现非递归化，一般来说要利用栈作辅助存储空间以保存上次调用的返回值、局部