递归及其在二叉树中的应用

1一、递归的定义递归：程序调用自身的编程技巧称为递归。递归函数：是直接调用自己或间接调用自己的函数。举例：直观的递归某些数学函数是递归定义的。求n！。具体实现如下：longfact(intn){if(n==0)return1;elsereturnn*fact(n-1);}递归及其在二叉树中的应用2二阶费波纳奇数列1n)2()1(1n10n0)(若若若nFibnFibnFib具体实现如下：longFib(intn){if(n==0)return0;if(n==1)return1;returnFib(n-1)+Fib(n-2);}3二、递归函数适用的场合在解决现实问题中，对于求解一个复杂的或者问题规模较大的问题，可以将其划分为一些简单的或者规模较小的问题进行解决，如果这种划分满足：所划分成的子问题性质与原来的大问题相同。当问题规模小到一定程度的时候直接有解。对于满足以上条件的问题我们就可以考虑使用递归的方法求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。4hanoi塔问题问题描述：假设有三个分别命名为X、Y、Z的塔座，在X塔座上叠放着n个小盘压大盘的圆盘堆，要求将塔座X上的n个圆盘移至塔座Z上，并按同样顺序叠放。要求：1、每次只能移动一个圆盘；2、圆盘可以放在X、Y、Z中的任意塔座上；3、任何时刻都不能将大盘压在小盘上；XYZXYZ5如果有一个盘子，直接从X移到Z即可。如果有n个盘子要从X移到Z，Y作为辅助。问题可以转化为，先将上面n-1个从X移动到Y，Z作为辅助，然后将第n个从X移动到Z，最后将剩余的n-1个从Y移动到Z，X作为辅助。hanoi塔问题6Voidhanoi(intn,charx,chary,charz){//将塔座X上按直径由小到大且自上而下编号为1至n的n个圆盘按规则搬到塔座Z上，Y作为辅助塔座。//搬动操作move(x,n,z)if(n==1)move(x,1,z);//将编号为1的圆盘从X搬到Zelse{hanoi(n-1,x,z,y);//将X上编号为1至n-1的圆盘移到Y，Z作辅助塔座move(x,n,z);//将编号为n的圆盘从X搬到Zhanoi(n-1,y,x,z);//将Y上编号为1至n-1的圆盘移到Z，Y作辅助塔座}}hanoi塔问题7voidPreOrderTraverse(BiTreeT){//采用二叉链表存储结构先序遍历二叉树T的递归算法if(T){Visit(T-data)；PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);}}先序遍历递归算法三、二叉树相关算法的递归实现8中序遍历递归算法voidInOrderTraverse(BiTreeT){if(T){InOrderTraverse(T-lchild);Visit(T-data)；InOrderTraverse(T-rchild);}}三、二叉树相关算法的递归实现9后序遍历递归算法voidPostOrderTraverse(BiTreeT){if(T){PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);Visit(T-data)；}}三、二叉树相关算法的递归实现10intLeaf_Count1(BitreeT){if(!T)return0;//空树没有叶子结点elseif((!T-lchild)&&(!T-rchild))return1;//只有一个根结点elsereturnLeaf_Count1(T-lchild)+Leaf_Count1(T-rchild);//左子树中的叶子结点数加上右子树中的叶子结点数}三、二叉树相关算法的递归实现1.求二叉树中叶子结点个数11voidnodes(BiTreeT){//计算以二叉链表为存储结构的二叉树的所有结点数if(!T)return0;elseif((!T-lchild)&&(!T-rchild))return1;elsereturn(nodes(T-lchild)+nodes(T-rchild)+1)；}三、二叉树相关算法的递归实现2.求二叉树中所有结点数12intf1(BiTreeT){if(T){if(T-lchild&&(!T-rchild))n++;if((!T-lchild)&&T-rchild)n++;f1(T-lchild)；f1(T-rchild);}}三、二叉树相关算法的递归实现3.求二叉树中度为1的结点个数13intf2(BiTreeT){if(T){if(T-lchild&&T-rchild)n++;f2(T-lchild)；f2(T-rchild);}}三、二叉树相关算法的递归实现4.编写求二叉树中度为2的结点个数14voidExchange(BiTree&T){BiTreeS;if(T){S=T-lchild;T-lchild=T-rchild;T-rchild=S;Exchange(T-lchild);Exchange(T-rchild);}}三、二叉树相关算法的递归实现5.交换二叉树的左右子树