递归及其在二叉树中的应用
一、递归的定义一、递归的定义递归：递归： 程序程序调用自身调用自身的编程技巧称为递归。的编程技巧称为递归。 递归函数：是直接调用自己或间接调用自己的函数。递归函数：是直接调用自己或间接调用自己的函数。举例：直观的递归举例：直观的递归 某些数学函数是递归定义的。某些数学函数是递归定义的。求求n n！。！。 具体实现如下：具体实现如下： long long fact(intfact(int n) n) if(nif(n=0) return 1;=0) return 1; else return n*fact(n-1);else return n*fact(n-1); 递归及其在二叉树中的应用递归及其在二叉树中的应用1二阶费波纳奇数列二阶费波纳奇数列具体实现如下：具体实现如下： long long Fib(intFib(int n) n) if(nif(n=0) return 0;=0) return 0; if(nif(n=1) return 1;=1) return 1; return Fib(n-1)+Fib(n-2);return Fib(n-1)+Fib(n-2); 2二、递归函数适用的场合二、递归函数适用的场合在解决现实问题中，对于求解一个复杂的或者问题规在解决现实问题中，对于求解一个复杂的或者问题规 模较大的问题，可以将其模较大的问题，可以将其划分为一些简单的或者规模较划分为一些简单的或者规模较 小的问题小的问题进行解决，如果这种划分满足：进行解决，如果这种划分满足：l l 所划分成的子问题性质与原来的大问题相同。所划分成的子问题性质与原来的大问题相同。 l l 当问题规模小到一定程度的时候直接有解。当问题规模小到一定程度的时候直接有解。对于满足以上条件的问题我们就可以考虑使用递归的对于满足以上条件的问题我们就可以考虑使用递归的 方法求解。方法求解。递归策略只需递归策略只需少量的程序少量的程序就可描述出解题过程所需要的就可描述出解题过程所需要的 多次重复计算多次重复计算，大大地减少了程序的代码量。递归的能，大大地减少了程序的代码量。递归的能 力在于力在于用有限的用有限的语句语句来定义对象的来定义对象的无限集合无限集合。 3hanoihanoi塔问题塔问题问题描述：问题描述： 假设有三个分别命名为假设有三个分别命名为X X、Y Y、Z Z的塔座，在的塔座，在X X塔座上叠放着塔座上叠放着 n n个小盘压大盘的圆盘堆，要求将塔座个小盘压大盘的圆盘堆，要求将塔座X X上的上的n n个圆盘移至塔个圆盘移至塔 座座Z Z上，并按同样顺序叠放。上，并按同样顺序叠放。要求：要求： 1 1、每次只能移动一个圆盘；、每次只能移动一个圆盘； 2 2、圆盘可以放在、圆盘可以放在X X、Y Y、Z Z中的任意塔座上；中的任意塔座上； 3 3、任何时刻都不能将大盘压在小盘上；、任何时刻都不能将大盘压在小盘上；XYZXYZ4l l 如果有一个盘子，直接从如果有一个盘子，直接从X X移到移到Z Z即可。即可。 l l 如果有如果有n n个盘子要从个盘子要从X X移到移到Z Z，Y Y作为辅助。问题可以转化为，先作为辅助。问题可以转化为，先 将上面将上面n-1n-1个从个从X X移动到移动到Y Y，Z Z作为辅助，然后将第作为辅助，然后将第n n个从个从X X移动到移动到Z Z ，最后将剩余的，最后将剩余的n-1n-1个从个从Y Y移动到移动到Z Z，X X作为辅助。作为辅助。hanoihanoi塔问题塔问题5Void Void hanoihanoi ( ( intint n, char x, char y, char z ) n, char x, char y, char z ) / /将塔座将塔座X X上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为1 1至至n n的的n n个圆盘按规则搬到塔座个圆盘按规则搬到塔座Z Z上，上，Y Y作为辅助塔座。作为辅助塔座。/搬动操作搬动操作move ( x, n, z )move ( x, n, z )if ( n= =1) if ( n= =1)move ( x, 1, z );/ move ( x, 1, z );/将编号为将编号为1 1的圆盘从的圆盘从X X搬到搬到Z Zelse else hanoihanoi ( n-1, x, z, y );/ ( n-1, x, z, y );/将将X X上编号为上编号为1 1至至n-1n-1的的圆盘移到圆盘移到Y Y，Z Z作辅助塔座作辅助塔座move ( x, n, z );/ move ( x, n, z );/将编号为将编号为n n的圆盘从的圆盘从X X搬到搬到Z Zhanoihanoi ( n-1, y, x, z );/ ( n-1, y, x, z );/将将Y Y上编号为上编号为1 1至至n-1n-1的的圆盘移到圆盘移到Z Z，Y Y作辅助塔座作辅助塔座 hanoihanoi塔问题塔问题6void void PreOrderTraversePreOrderTraverse ( ( BiTreeBiTree T ) T ) / /采用二叉链表存储结构先序遍历二叉树采用二叉链表存储结构先序遍历二叉树T T的递归算法的递归算法if (T)if (T) Visit(T->data) Visit(T->data)； PreOrderTraverse(TPreOrderTraverse(T->->lchildlchild); );PreOrderTraverse(TPreOrderTraverse(T->->rchildrchild); ); 先序遍历递归算法先序遍历递归算法三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现7中序遍历递归算法中序遍历递归算法void void InOrderTraverseInOrderTraverse ( ( BiTreeBiTree T ) T ) if (T) if (T) InOrderTraverse(TInOrderTraverse(T->->lchildlchild); ); Visit(T->data)Visit(T->data)； InOrderTraverse(TInOrderTraverse(T->->rchildrchild); ); 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现8后序遍历递归算法后序遍历递归算法void void PostOrderTraversePostOrderTraverse ( ( BiTreeBiTree T ) T ) if (T) if (T) PostOrderTraverse(TPostOrderTraverse(T->->lchildlchild); ); PostOrderTraverse(TPostOrderTraverse(T->->rchildrchild); ); Visit(T->data)Visit(T->data)； 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现9intint Leaf_Count1(Bitree T) Leaf_Count1(Bitree T) if(!Tif(!T) return 0; /) return 0; /空树没有叶子结点空树没有叶子结点else else if(! T-> if(! T->lchildlchild) / return 1; /只有一个根结点只有一个根结点else else return Leaf_Count1(T-lchild)+Leaf_Count1(T-rchild); return Leaf_Count1(T-lchild)+Leaf_Count1(T-rchild); / /左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶子结点数 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现1. 1.求二叉树中叶子结点个数求二叉树中叶子结点个数10void nodes ( void nodes ( BiTreeBiTree T ) T ) / /计算以二叉链表为存储结构的二叉树的所有结点数计算以二叉链表为存储结构的二叉树的所有结点数if (!T) if (!T) return 0; return 0;else else if (! T-> if (! T->lchild) return 1;else else return(nodes(Treturn(nodes(T->->lchild)+nodes(Tlchild)+nodes(T->rchild)+1)->rchild)+1)； 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现2. 2. 求二叉树中所有结点数求二叉树中所有结点数11intint f1( f1( BiTreeBiTree T ) T ) if (T) if (T) if (T-> if (T->lchildlchild ) n+;if (!T-> if (!T->lchildlchild) ) n+;f1(T-> f1(T->lchildlchild) )；f1(T->f1(T->rchildrchild); ); 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现3. 3.求二叉树中度为求二叉树中度为1 1的结点个数的结点个数12intint f2 ( f2 ( BiTreeBiTree T ) T ) if (T) if (T) if (T-> if (T->lchildlchild ) n+;f2(T-> f2(T->lchildlchild) )；f2(T->f2(T->rchildrchild); ); 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现4. 4.编写求二叉树中度为编写求二叉树中度为2 2的结点个数的结点个数13void Exchange ( void Exchange ( BiTreeBiTree S; if (T) if (T) S=T-> S=T->lchildlchild; ;T-> T->lchildlchild=T->=T->rchildrchild; ;T-> T->rchildrchild=S;=S;Exchange(T-> Exchange(T->lchildlchild); );Exchange(T-> Exchange(T->rchildrchild); ); 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现5. 5. 交换二叉树的左右子树交换二叉树的左右子树14
