《递归及递归算法》由会员分享，可在线阅读，更多相关《递归及递归算法（32页珍藏版）》请在金锄头文库上搜索。
1、 递归的实现及应用1.递归:一个直接调用自己或通过一系列的调用语句间接的调用自 己的函数,称做递归.分为直接递归和间接递归在递归函数的递归调用过程中，当有多个函数构成嵌套调用时， 函数之间的信息传递和控制转移必须通过栈来实现。2.用递归解决的问题: 其一:数学函数采用递归定义如:阶乘函数Fact(n)= 1 n=0 n Fact(n-1) n0其二：有的数据结构，如二叉树，广义表，图的遍历，查找算 法等由于结构本身固有的递归特性，其操作可以递归的描述；其三：没有明显的递归结构但用递归求解更简单，如Hanoi塔 问题求解 3、递归程序的一般形式Status function (参数表）； lon
2、g fact(int n) If 数据为递归出口 if (n data) ; InOrderTraverse ( T-lchild ) ;InOrderTraverse ( T-rchild ) ;If (T) void InOrderTraverse ( BiTree T ) /中序遍历算法 6.2 中序遍历递归算法（或其他遍历算法）树的递归算法思路拓展 设计算法由此导出许多实用的算法：如求二叉树的 高度， 度为0，1，2的结点数，二叉树 的相似、复制等。表达式求值 例1 设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点 的数目。 .void Count(BiTree bt,int *n
3、0,*n) /统计二叉树bt上叶子结点数n0和 非叶子结点数nif(bt)if (bt-lchild=null /非叶结点Count(bt-lchild,Count(bt-rchild, /结束 Count 例2试写出复制一棵二叉树的算法。二叉树采用标准链接结构。 BiTree Copy(BiTree t)/复制二叉树t BiTree bt;if (t=null) bt=null;elsebt=(BiTree)malloc(sizeof(BiNode); bt-data=t-data;bt-lchild=Copy(t-lchild);bt-rchild=Copy(t-rchild); retu
4、rn(bt); /结束Copy例3 ：用孩子兄弟链表作为树的存储结构，请编写求树的深度的算 法。分析：一棵树的深度定义为：若树为空，则深度为0，否则树的深 度为所有子树深度的最大值加1。 ADCBADCB结点类型定义为：type struct node char data;struct node *fristchild nextbrotherCsnodefristchild 指向结点的第一个孩子结点，nextbrother指 向结点的右邻兄弟结点。 由孩子兄弟链表表示的树，求高度的递归模型是：若树为空 ，高度为零；若第一孩子为空，高度为1和兄弟子树的高度的 大者；否则，高度为第一孩子树高度加1
5、和兄弟子树高度的大 者。其非递归算法使用队列，逐层遍历树，取得树的高度。 int Height(CSTree bt) /递归求以孩子兄弟链表表示的树的 深度 int hc,hs; if (bt=null) return (0); else if (!bt-firstchild) return (1+height(bt-nextsibling);/孩子 空，查兄弟的深度 else / 结点既有第一孩子又有兄弟，高度取孩子高度+1和兄 弟子树高度的大者 hc=height(bt-firstchild)； /第一孩子树高 hs=height(bt-nextsibling)；/兄弟树高 if(hc+1
6、hs)return(hc+1); else return (hs); 例4：假设一棵平衡二叉树的每个结点都表明了平衡因子，设计一个算法，求平 衡二叉树的高度。（燕山大学 2001）分析：因为二叉树各结点已标明了平衡因子，故从根结点记录树的层次。根结点 的层次为1，每下一层，层次加1，直到层数最大的结点，这就是平衡二叉树的高 度。当结点的平衡因子b为0时，任选左右一分支向下查找，若b不为0，则沿左（ 当 b=1时）或右（当b=-1时）向下查找。算法如下：Int height (BSTree t)level=0;p=t;While (p)level+;/树的高度if (p-bfrchild;/bf
7、=-1沿右分支向下else p=p-lchild; /bf=0沿右分支向下whileReturn (level);/平衡二叉树的高度 例5：表达式求值1假设一个仅包含二元运 算符的算术表达式以链表形式存储在二叉树 BT中，写出计算该算术表达式值的算法。 题目分析以二叉树表示算术表达式，根结点 用于存储运算符。若能先分别求出左子树和 右子树表示的子表达式的值，最后就可以根 据根结点的运算符的要求，计算出表达式的 最后结果。 typedef struct node ElemType data; float val; char optr; /只取+， -， *，/ struct node *lchi
8、ld，*rchild BiNode,*BiTree;float PostEval(BiTree bt) / 以后序遍历算法求以二叉树表示的算术 表达式的值 float lv,rv; if(bt!=null) lv=PostEval(bt-lchild); / 求左子树表示的子表达式的值 rv=PostEval(bt-rchild); / 求右子树表示的子表达式的值 switch(bt-optr) case +: value=lv+rv; break; case -: value=lv-rv;break; case *: value=lv*rv;break;case /: value=lv/rv
9、; return(value); 6 6、一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存 于两个一维数组pre1n 和mid1n 中，试遍写算法建立该二叉树的二 叉链表。. 下面给出递归算法。 void PreInCreat(BiTree root,ElemType pre,in,int l1,h1,l2,h2) /根据二叉树前序序列pre和中序序列in建立二叉树。l1,h1,l2,h2是序列第 一和最后元素下标。 root=(BiTree)malloc(sizeof(BiNode); /申请结点 root-data=prel1; /prel1是根 for(i=l2;ilchild
10、=null; /无左子树 else PreInCreat(root-lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)； /递归建立左子 树 if(i=h2) root-rchild=null; /无右子树 else PreInCreat(root)-rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2) /递归建立右 子树 /结束PreInCreat 题目分析叶子结点只有在遍历中才能知道，这里使用中 序递归遍历。设置前驱结点指针pre，初始为空。第一 个叶子结点由指针head指向，遍历到叶子结点时，就将 它前驱的rchild指针指向它，最后叶子结点的r
11、child为空 。 7、请设计一个算法，要求该算法把二叉树的叶子结点 按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指 针域来存放单链表指针。 LinkedList head,pre=null; /全局变量 LinkedList InOrder(BiTree bt) /中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头 指针为head if(bt)InOrder(bt-lchild); /中序遍历左子树 if(bt-lchild=null pre=bt; /处理第一个叶子结点 elsepre-rchild=bt; pre=bt; /
12、将叶子结点链入链表 InOrder(bt-rchild); /中序遍历左子树 pre-rchild=null; /设置链表尾 return(head); /InOrder 时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)二叉树遍历的非递归算法及其应用基本思想：1、从二叉树的根结点开始，沿左枝 一走到没有左孩子的结点为止，同 时将所遇结点入栈，2、待到遍历完左子树时，从栈顶退 出结点并访问，然后再遍历其右子 树. 3、重复上述操作完成遍历。中序遍历非递归方法Int i=0 ; BiTree *sm，*p; p=T; P=s- -i ; /从栈顶退出 结点 并访问 Prin
13、tf(“%ct”,p-data);P=p-rchildIf ( i 0)Do while ( p ) si+=p; /沿左枝一走到没有左孩子的结点为止，同时将所遇结点入栈 P=p-lchild ;Void inOrderTraverse ( BiTree *T ) 中序遍历非递归算法 While(i0|p!=null)1245367前序遍历的非递归算法基本思想前序遍历的非递归算法基本思想基本思想：1、从二叉树的根结点开始，沿左枝一走到没 有左孩子的结点为止，同时访问所遇结点， 并把非空右孩子入栈；2、找到没有左孩子的结点时， 从栈顶退出某 结点的右孩子，此时该结点的左子树已遍历 结束 ，然后按
14、上述过程遍历该结点的右子树3、重复上述操作完成遍历。1245367Int i=0 ; BiTree *sm; p=T; P=s- -i ; /从栈顶退出某结点的右孩子结点 If (p-rchild!=null) si+= p-rchild ; /非空右孩子 进栈P=p-lchild /沿左枝If ( i 0)Do while ( p ) Printf(“%ct”,p-data);沿左枝一走到没有左孩子的结点为止， 同时访问所遇结点Void preOrderTraverse ( BiTree *T ) 前序遍历非递归算法While(i0|p!=null)1245367后序遍历的非递归算法基本思想后序遍历的非递归算法基本思想基本思想：使用栈来实现。每个结点要等到遍历完左，右子树后才能 访问， 所以在遍历左，右子树之前结点都需 要进栈，为了区分这两者，除设结点栈s外， 另设一个标记栈b,标记“0”表示结点在遍历左 子树时进栈，标记“1”表示结点在遍历右子树 时进栈。1245367Int I=0 ; BiTree *sm; int b
