递归及其在二叉树中的应用精选文档.ppt
递归及其在二叉树中的应用1本讲稿第一页，共十四页二阶费波纳奇数列二阶费波纳奇数列具体实现如下：具体实现如下：具体实现如下：具体实现如下：long Fib(int n)long Fib(int n)long Fib(int n)long Fib(int n)if(n=0)return 0;if(n=0)return 0;if(n=0)return 0;if(n=0)return 0;if(n=1)return 1;if(n=1)return 1;if(n=1)return 1;if(n=1)return 1;return Fib(n-1)+Fib(n-2);return Fib(n-1)+Fib(n-2);return Fib(n-1)+Fib(n-2);return Fib(n-1)+Fib(n-2);2本讲稿第二页，共十四页二、递归函数适用的场合二、递归函数适用的场合 在解决现实问题中，对于求解一个复杂的或者问题规模在解决现实问题中，对于求解一个复杂的或者问题规模在解决现实问题中，对于求解一个复杂的或者问题规模在解决现实问题中，对于求解一个复杂的或者问题规模较大的问题，可以将其较大的问题，可以将其较大的问题，可以将其较大的问题，可以将其划分为一些简单的或者规模较小的问划分为一些简单的或者规模较小的问划分为一些简单的或者规模较小的问划分为一些简单的或者规模较小的问题题题题进行解决，如果这种划分满足：进行解决，如果这种划分满足：进行解决，如果这种划分满足：进行解决，如果这种划分满足：所划分成的子问题性质与原来的大问题相同。所划分成的子问题性质与原来的大问题相同。所划分成的子问题性质与原来的大问题相同。所划分成的子问题性质与原来的大问题相同。当问题规模小到一定程度的时候直接有解。当问题规模小到一定程度的时候直接有解。当问题规模小到一定程度的时候直接有解。当问题规模小到一定程度的时候直接有解。对于满足以上条件的问题我们就可以考虑使用递归的方法求对于满足以上条件的问题我们就可以考虑使用递归的方法求对于满足以上条件的问题我们就可以考虑使用递归的方法求对于满足以上条件的问题我们就可以考虑使用递归的方法求解。解。解。解。递归策略只需递归策略只需递归策略只需递归策略只需少量的程序少量的程序少量的程序少量的程序就可描述出解题过程所需要的就可描述出解题过程所需要的就可描述出解题过程所需要的就可描述出解题过程所需要的多次多次多次多次重复计算重复计算重复计算重复计算，大大地减少了程序的代码量。递归的能力在于，大大地减少了程序的代码量。递归的能力在于，大大地减少了程序的代码量。递归的能力在于，大大地减少了程序的代码量。递归的能力在于用用用用有限的语句来定义对象的无限集合。有限的语句来定义对象的无限集合。有限的语句来定义对象的无限集合。有限的语句来定义对象的无限集合。3本讲稿第三页，共十四页 hanoi hanoi塔问题塔问题问题描述：问题描述：问题描述：问题描述：假设有三个分别命名为假设有三个分别命名为假设有三个分别命名为假设有三个分别命名为X X X X、Y Y Y Y、Z Z Z Z的塔座，在的塔座，在的塔座，在的塔座，在X X X X塔座上叠放着塔座上叠放着塔座上叠放着塔座上叠放着n n n n个小个小个小个小盘压大盘的圆盘堆，要求将塔座盘压大盘的圆盘堆，要求将塔座盘压大盘的圆盘堆，要求将塔座盘压大盘的圆盘堆，要求将塔座X X X X上的上的上的上的n n n n个圆盘移至塔座个圆盘移至塔座个圆盘移至塔座个圆盘移至塔座Z Z Z Z上，并上，并上，并上，并按同样顺序叠放。按同样顺序叠放。按同样顺序叠放。按同样顺序叠放。要求：要求：要求：要求：1 1 1 1、每次只能移动一个圆盘；、每次只能移动一个圆盘；、每次只能移动一个圆盘；、每次只能移动一个圆盘；2 2 2 2、圆盘可以放在、圆盘可以放在、圆盘可以放在、圆盘可以放在X X X X、Y Y Y Y、Z Z Z Z中的任意塔座上；中的任意塔座上；中的任意塔座上；中的任意塔座上；3 3 3 3、任何时刻都不能将大盘压在小盘上；、任何时刻都不能将大盘压在小盘上；、任何时刻都不能将大盘压在小盘上；、任何时刻都不能将大盘压在小盘上；X XY YZ ZX XY YZ Z4本讲稿第四页，共十四页l l如果有一个盘子，直接从如果有一个盘子，直接从如果有一个盘子，直接从如果有一个盘子，直接从X X X X移到移到移到移到Z Z Z Z即可。即可。即可。即可。l l如果有如果有如果有如果有n n n n个盘子要从个盘子要从个盘子要从个盘子要从X X X X移到移到移到移到Z Z Z Z，Y Y Y Y作为辅助。问题可以转化为，先将上面作为辅助。问题可以转化为，先将上面作为辅助。问题可以转化为，先将上面作为辅助。问题可以转化为，先将上面n-1n-1n-1n-1个从个从个从个从X X X X移动到移动到移动到移动到Y Y Y Y，Z Z Z Z作为辅助，然后将第作为辅助，然后将第作为辅助，然后将第作为辅助，然后将第n n n n个从个从个从个从X X X X移动到移动到移动到移动到Z Z Z Z，最后将剩余的，最后将剩余的，最后将剩余的，最后将剩余的n-1n-1n-1n-1个从个从个从个从Y Y Y Y移移移移动到动到动到动到Z Z Z Z，X X X X作为辅助。作为辅助。作为辅助。作为辅助。hanoi塔问题塔问题5本讲稿第五页，共十四页Void hanoi(int n,char x,char y,char z)Void hanoi(int n,char x,char y,char z)Void hanoi(int n,char x,char y,char z)Void hanoi(int n,char x,char y,char z)/将塔座将塔座将塔座将塔座X X X X上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为1 1 1 1至至至至n n n n的的的的 n n n n个圆盘按规则搬到塔座个圆盘按规则搬到塔座个圆盘按规则搬到塔座个圆盘按规则搬到塔座Z Z Z Z上，上，上，上，Y Y Y Y作为辅助塔座。作为辅助塔座。作为辅助塔座。作为辅助塔座。/搬动操作搬动操作搬动操作搬动操作move(x,n,z)move(x,n,z)move(x,n,z)move(x,n,z)if(n=1)if(n=1)if(n=1)if(n=1)move(x,1,z);/move(x,1,z);/move(x,1,z);/move(x,1,z);/将编号为将编号为将编号为将编号为1 1 1 1的圆盘从的圆盘从的圆盘从的圆盘从X X X X搬到搬到搬到搬到Z Z Z Z else else else else hanoi(n-1,x,z,y);/hanoi(n-1,x,z,y);/hanoi(n-1,x,z,y);/hanoi(n-1,x,z,y);/将将将将X X X X上编号为上编号为上编号为上编号为1 1 1 1至至至至n-1n-1n-1n-1的的的的 圆盘移到圆盘移到圆盘移到圆盘移到Y Y Y Y，Z Z Z Z作辅助塔座作辅助塔座作辅助塔座作辅助塔座 move(x,n,z);/move(x,n,z);/move(x,n,z);/move(x,n,z);/将编号为将编号为将编号为将编号为n n n n的圆盘从的圆盘从的圆盘从的圆盘从X X X X搬到搬到搬到搬到Z Z Z Z hanoi(n-1,y,x,z);/hanoi(n-1,y,x,z);/hanoi(n-1,y,x,z);/hanoi(n-1,y,x,z);/将将将将Y Y Y Y上编号为上编号为上编号为上编号为1 1 1 1至至至至n-1n-1n-1n-1的的的的 圆盘移到圆盘移到圆盘移到圆盘移到Z Z Z Z，Y Y Y Y作辅助塔座作辅助塔座作辅助塔座作辅助塔座 hanoi塔问题塔问题6本讲稿第六页，共十四页void PreOrderTraverse(BiTree T)void PreOrderTraverse(BiTree T)void PreOrderTraverse(BiTree T)void PreOrderTraverse(BiTree T)/采用二叉链表存储结构先序遍历二叉树采用二叉链表存储结构先序遍历二叉树采用二叉链表存储结构先序遍历二叉树采用二叉链表存储结构先序遍历二叉树T T T T的递归算法的递归算法的递归算法的递归算法 if(T)if(T)if(T)if(T)Visit(T-data)Visit(T-data)Visit(T-data)Visit(T-data)；PreOrderTraverse(T-lchild);PreOrderTraverse(T-lchild);PreOrderTraverse(T-lchild);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);PreOrderTraverse(T-rchild);PreOrderTraverse(T-rchild);PreOrderTraverse(T-rchild);先序遍历递归算法先序遍历递归算法三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现7本讲稿第七页，共十四页中序遍历递归算法中序遍历递归算法中序遍历递归算法中序遍历递归算法void InOrderTraverse(BiTree T)void InOrderTraverse(BiTree T)void InOrderTraverse(BiTree T)void InOrderTraverse(BiTree T)if(T)if(T)if(T)if(T)InOrderTraverse(T-lchild);InOrderTraverse(T-lchild);InOrderTraverse(T-lchild);InOrderTraverse(T-lchild);Visit(T-data)Visit(T-data)Visit(T-data)Visit(T-data)；InOrderTraverse(T-rchild);InOrderTraverse(T-rchild);InOrderTraverse(T-rchild);InOrderTraverse(T-rchild);三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现8本讲稿第八页，共十四页后序遍历递归算法后序遍历递归算法后序遍历递归算法后序遍历递归算法void PostOrderTraverse(BiTree T)void PostOrderTraverse(BiTree T)if(T)if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);PostOrderTraverse(T-rchild);Visit(T-data)Visit(T-data)；三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现9本讲稿第九页，共十四页int Leaf_Count1(Bitree T)int Leaf_Count1(Bitree T)int Leaf_Count1(Bitree T)int Leaf_Count1(Bitree T)if(!T)return 0;/if(!T)return 0;/if(!T)return 0;/if(!T)return 0;/空树没有叶子结点空树没有叶子结点空树没有叶子结点空树没有叶子结点 else else else else if(!T-lchild)&(!T-rchild)if(!T-lchild)&(!T-rchild)if(!T-lchild)&(!T-rchild)if(!T-lchild)&(!T-rchild)return 1;/return 1;/return 1;/return 1;/只有一个根结点只有一个根结点只有一个根结点只有一个根结点 else else else else return Leaf_Count1(T-lchild)+Leaf_Count1(T-rchild);return Leaf_Count1(T-lchild)+Leaf_Count1(T-rchild);return Leaf_Count1(T-lchild)+Leaf_Count1(T-rchild);return Leaf_Count1(T-lchild)+Leaf_Count1(T-rchild);/左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶子结点数 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现1.求二叉树中叶子结点个数求二叉树中叶子结点个数10本讲稿第十页，共十四页void nodes(BiTree T)void nodes(BiTree T)void nodes(BiTree T)void nodes(BiTree T)/计算以二叉链表为存储结构的二叉树的所有结点数计算以二叉链表为存储结构的二叉树的所有结点数计算以二叉链表为存储结构的二叉树的所有结点数计算以二叉链表为存储结构的二叉树的所有结点数 if(!T)if(!T)if(!T)if(!T)return 0;return 0;return 0;return 0;else else else else if(!T-lchild)&(!T-rchild)return 1;if(!T-lchild)&(!T-rchild)return 1;if(!T-lchild)&(!T-rchild)return 1;if(!T-lchild)&(!T-rchild)return 1;else else else else return(nodes(T-lchild)+nodes(T-rchild)+1)return(nodes(T-lchild)+nodes(T-rchild)+1)return(nodes(T-lchild)+nodes(T-rchild)+1)return(nodes(T-lchild)+nodes(T-rchild)+1)；三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现2.2.求二叉树中所有结点数求二叉树中所有结点数求二叉树中所有结点数求二叉树中所有结点数11本讲稿第十一页，共十四页int f1(BiTree T)int f1(BiTree T)int f1(BiTree T)int f1(BiTree T)if(T)if(T)if(T)if(T)if(T-lchild&(!T-rchild)n+;if(T-lchild&(!T-rchild)n+;if(T-lchild&(!T-rchild)n+;if(T-lchild&(!T-rchild)n+;if(!T-lchild)&T-rchild)n+;if(!T-lchild)&T-rchild)n+;if(!T-lchild)&T-rchild)n+;if(!T-lchild)&T-rchild)n+;f1(T-lchild)f1(T-lchild)f1(T-lchild)f1(T-lchild)；f1(T-rchild);f1(T-rchild);f1(T-rchild);f1(T-rchild);三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现3.3.求二叉树中度为求二叉树中度为求二叉树中度为求二叉树中度为1 1的结点个数的结点个数的结点个数的结点个数12本讲稿第十二页，共十四页int f2(BiTree T)int f2(BiTree T)if(T)if(T)if(T-lchild&T-rchild)n+;if(T-lchild&T-rchild)n+;f2(T-lchild)f2(T-lchild)；f2(T-rchild);f2(T-rchild);三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现4.4.编写求二叉树中度为编写求二叉树中度为编写求二叉树中度为编写求二叉树中度为2 2的结点个数的结点个数的结点个数的结点个数13本讲稿第十三页，共十四页void Exchange(BiTree&T)void Exchange(BiTree&T)BiTree S;BiTree S;if(T)if(T)S=T-lchild;S=T-lchild;T-lchild=T-rchild;T-lchild=T-rchild;T-rchild=S;T-rchild=S;Exchange(T-lchild);Exchange(T-lchild);Exchange(T-rchild);Exchange(T-rchild);三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现5.5.交换二叉树的左右子树交换二叉树的左右子树交换二叉树的左右子树交换二叉树的左右子树14本讲稿第十四页，共十四页
