递归及其在二叉树中的应用精选PPT.ppt

《递归及其在二叉树中的应用精选PPT.ppt》由会员分享，可在线阅读，更多相关《递归及其在二叉树中的应用精选PPT.ppt（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归及其在二叉树中的应用1第1页，此课件共14页哦二阶费波纳奇数列二阶费波纳奇数列二阶费波纳奇数列二阶费波纳奇数列具体实现如下：具体实现如下：具体实现如下：具体实现如下：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);re

2、turn Fib(n-1)+Fib(n-2);return Fib(n-1)+Fib(n-2);return Fib(n-1)+Fib(n-2);2第2页，此课件共14页哦二、递归函数适用的场合二、递归函数适用的场合 在解决现实问题中，对于求解一个复杂的或者问题规模较大的在解决现实问题中，对于求解一个复杂的或者问题规模较大的在解决现实问题中，对于求解一个复杂的或者问题规模较大的在解决现实问题中，对于求解一个复杂的或者问题规模较大的问题，可以将其问题，可以将其问题，可以将其问题，可以将其划分为一些简单的或者规模较小的问题划分为一些简单的或者规模较小的问题划分为一些简单的或者规模较小的问题划分为一

3、些简单的或者规模较小的问题进进进进行解决，如果这种划分满足：行解决，如果这种划分满足：行解决，如果这种划分满足：行解决，如果这种划分满足：所划分成的子问题性质与原来的大问题相同。所划分成的子问题性质与原来的大问题相同。所划分成的子问题性质与原来的大问题相同。所划分成的子问题性质与原来的大问题相同。当问题规模小到一定程度的时候直接有解。当问题规模小到一定程度的时候直接有解。当问题规模小到一定程度的时候直接有解。当问题规模小到一定程度的时候直接有解。对于满足以上条件的问题我们就可以考虑使用递归的方法求解。对于满足以上条件的问题我们就可以考虑使用递归的方法求解。对于满足以上条件的问题我们就可以考虑使

4、用递归的方法求解。对于满足以上条件的问题我们就可以考虑使用递归的方法求解。递归策略只需递归策略只需递归策略只需递归策略只需少量的程序少量的程序少量的程序少量的程序就可描述出解题过程所需要的就可描述出解题过程所需要的就可描述出解题过程所需要的就可描述出解题过程所需要的多次重复多次重复多次重复多次重复计算计算计算计算，大大地减少了程序的代码量。递归的能力在于，大大地减少了程序的代码量。递归的能力在于，大大地减少了程序的代码量。递归的能力在于，大大地减少了程序的代码量。递归的能力在于用有限的语用有限的语用有限的语用有限的语句来定义对象的无限集合。句来定义对象的无限集合。句来定义对象的无限集合。句来定

5、义对象的无限集合。3第3页，此课件共14页哦 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

6、 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第4页

7、，此课件共14页哦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作为辅助，然后将第作为辅助，然后

8、将第作为辅助，然后将第作为辅助，然后将第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第5页，此课件共14页哦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

9、)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,

10、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的的的的 圆盘移到圆盘移

11、到圆盘移到圆盘移到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的的的的 圆盘移到圆盘移到圆盘移到圆盘

12、移到Z Z Z Z，Y Y Y Y作辅助塔座作辅助塔座作辅助塔座作辅助塔座 hanoi塔问题塔问题6第6页，此课件共14页哦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

13、(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);先序遍历递归算法先序遍历递归算法先序遍历递归算法先序遍历

14、递归算法三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现7第7页，此课件共14页哦中序遍历递归算法中序遍历递归算法中序遍历递归算法中序遍历递归算法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);InOrd

15、erTraverse(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第8页，此课件共14页哦后序遍历递归算法后序遍历递归算法后序遍历递归算法后序遍历递归算法void PostOrderTraverse(BiTree T)void PostOrderTra

16、verse(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第9页，此课件共14页哦int Leaf_Count1(Bitree T)int Leaf_Count1(Bitree T)int Leaf_Count1(Bitree T)int Leaf_Count1(Bitr

17、ee 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

18、 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);/左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶

19、子结点数 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现1.1.求二叉树中叶子结点个数求二叉树中叶子结点个数求二叉树中叶子结点个数求二叉树中叶子结点个数10第10页，此课件共14页哦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;r

20、eturn 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-l

21、child)+nodes(T-rchild)+1)return(nodes(T-lchild)+nodes(T-rchild)+1)；三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现2.2.求二叉树中所有结点数求二叉树中所有结点数求二叉树中所有结点数求二叉树中所有结点数11第11页，此课件共14页哦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-lchil

22、d&(!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.求二叉树中度为求二叉树中度为求二叉树中度为

23、求二叉树中度为1 1的结点个数的结点个数的结点个数的结点个数12第12页，此课件共14页哦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第13页，此课件共14页哦void Exc

24、hange(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第14页，此课件共14页哦