《递归及其在二叉树中的应用优秀课件.ppt》由会员分享，可在线阅读，更多相关《递归及其在二叉树中的应用优秀课件.ppt（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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);ret
2、urn 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 Z上
6、，并按同上，并按同上，并按同上，并按同样顺序叠放。样顺序叠放。样顺序叠放。样顺序叠放。要求：要求：要求：要求：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)Void
9、 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)i
10、f(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的的的的 圆盘移到圆盘移到圆盘移到圆盘移到Z Z
12、 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(T)Vis
13、it(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);InOrderTrave
15、rse(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 PostOrderTraverse(Bi
16、Tree T)void PostOrderTraverse(BiTree T)void PostOrderTraverse(BiTree T)if(T)if(T)if(T)if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-lchild);PostOrderTraverse(T-lchild);PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);PostOrderTraverse(T-rchild);PostOrderTraverse(T-rchild);PostOrderTrav
17、erse(T-rchild);Visit(T-data)Visit(T-data)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(Bitree T)if(!T)return 0;/if(!T)return 0;/if(!T)return 0;/if(!T)return 0;/空树没有叶子结点空树没有叶子结点空树没有叶子结点空树没有
18、叶子结点 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_C
19、ount1(T-rchild);return Leaf_Count1(T-lchild)+Leaf_Count1(T-rchild);return Leaf_Count1(T-lchild)+Leaf_Count1(T-rchild);/左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶子结点数左子树中的叶子结点数加上右子树中的叶子结点数 三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现1.1.求二叉树中叶子结点个数求二叉树中叶子结点个数求二叉树中叶子结点个数求二叉树中叶子结点个数10第10页，本讲稿共14页vo
20、id 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-
21、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
22、.求二叉树中所有结点数求二叉树中所有结点数求二叉树中所有结点数求二叉树中所有结点数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-lchild&(!T-rchild)n+;if(T-lchild&(!T-rchild)n+;if(!T-lchild)&T-rchild)n+;if(!T-lchild)&T-rchild)n+;if(!T
23、-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第12页，本讲稿共14页int f2(BiTree T)int f2(BiTree T)int f2(BiTree T)int f2(
24、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+;f2(T-lchild)f2(T-lchild)f2(T-lchild)f2(T-lchild)；f2(T-rchild);f2(T-rchild);f2(T-rchild);f2(T-rchild);三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现4.4.编写求二叉树中度为编写求二叉树中度为编写求二叉树中度为编写求二叉树中度为2 2的结点
25、个数的结点个数的结点个数的结点个数13第13页，本讲稿共14页void Exchange(BiTree&T)void Exchange(BiTree&T)void Exchange(BiTree&T)void Exchange(BiTree&T)BiTree S;BiTree S;BiTree S;BiTree S;if(T)if(T)if(T)if(T)S=T-lchild;S=T-lchild;S=T-lchild;S=T-lchild;T-lchild=T-rchild;T-lchild=T-rchild;T-lchild=T-rchild;T-lchild=T-rchild;T-rchild=S;T-rchild=S;T-rchild=S;T-rchild=S;Exchange(T-lchild);Exchange(T-lchild);Exchange(T-lchild);Exchange(T-lchild);Exchange(T-rchild);Exchange(T-rchild);Exchange(T-rchild);Exchange(T-rchild);三、二叉树相关算法的递归实现三、二叉树相关算法的递归实现5.5.交换二叉树的左右子树交换二叉树的左右子树交换二叉树的左右子树交换二叉树的左右子树14第14页，本讲稿共14页