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

1、递归及其在二叉树中的应用1第1页，共14页，2022年，5月20日，19点37分，星期三二阶费波纳奇数列具体实现如下：long Fib(int n)if(n=0) return 0;if(n=1) return 1;return Fib(n-1)+Fib(n-2);2第2页，共14页，2022年，5月20日，19点37分，星期三二、递归函数适用的场合 在解决现实问题中，对于求解一个复杂的或者问题规模较大的问题，可以将其划分为一些简单的或者规模较小的问题进行解决，如果这种划分满足：所划分成的子问题性质与原来的大问题相同。当问题规模小到一定程度的时候直接有解。 对于满足以上条件的问题我们就可以考虑

2、使用递归的方法求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。 3第3页，共14页，2022年，5月20日，19点37分，星期三 hanoi塔问题问题描述：假设有三个分别命名为X、Y、Z的塔座，在X塔座上叠放着n个小盘压大盘的圆盘堆，要求将塔座X上的n个圆盘移至塔座Z上，并按同样顺序叠放。要求：1、每次只能移动一个圆盘；2、圆盘可以放在X、Y、Z中的任意塔座上；3、任何时刻都不能将大盘压在小盘上；XYZXYZ4第4页，共14页，2022年，5月20日，19点37分，星期三如果有一个盘子，直接从X移到Z

3、即可。如果有n个盘子要从X移到Z，Y作为辅助。问题可以转化为，先将上面n-1个从X移动到Y，Z作为辅助，然后将第n个从X移动到Z，最后将剩余的n-1个从Y移动到Z，X作为辅助。 hanoi塔问题5第5页，共14页，2022年，5月20日，19点37分，星期三Void hanoi ( int n, char x, char y, char z ) /将塔座X上按直径由小到大且自上而下编号为1至n的 n个圆盘按规则搬到塔座Z上，Y作为辅助塔座。 /搬动操作move ( x, n, z ) if ( n= =1) move ( x, 1, z );/将编号为1的圆盘从X搬到Z else hanoi

4、( n-1, x, z, y );/将X上编号为1至n-1的 圆盘移到Y，Z作辅助塔座 move ( x, n, z );/将编号为n的圆盘从X搬到Z hanoi ( n-1, y, x, z );/将Y上编号为1至n-1的 圆盘移到Z，Y作辅助塔座 hanoi塔问题6第6页，共14页，2022年，5月20日，19点37分，星期三void PreOrderTraverse ( BiTree T ) /采用二叉链表存储结构先序遍历二叉树T的递归算法 if (T) Visit(T-data)； PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchil

5、d); 先序遍历递归算法三、二叉树相关算法的递归实现7第7页，共14页，2022年，5月20日，19点37分，星期三中序遍历递归算法void InOrderTraverse ( BiTree T ) if (T) InOrderTraverse(T-lchild);Visit(T-data)； InOrderTraverse(T-rchild);三、二叉树相关算法的递归实现8第8页，共14页，2022年，5月20日，19点37分，星期三后序遍历递归算法void PostOrderTraverse ( BiTree T ) if (T) PostOrderTraverse(T-lchild);P

6、ostOrderTraverse(T-rchild);Visit(T-data)； 三、二叉树相关算法的递归实现9第9页，共14页，2022年，5月20日，19点37分，星期三int Leaf_Count1(Bitree T) if(!T) return 0; /空树没有叶子结点 else if(! T-lchild)& (! T-rchild) return 1; /只有一个根结点 else return Leaf_Count1(T-lchild)+Leaf_Count1(T-rchild); /左子树中的叶子结点数加上右子树中的叶子结点数三、二叉树相关算法的递归实现1.求二叉树中叶子结点个

7、数10第10页，共14页，2022年，5月20日，19点37分，星期三void nodes ( BiTree T ) /计算以二叉链表为存储结构的二叉树的所有结点数 if (!T) return 0; else if (! T-lchild)&(!T-rchild) return 1; else return(nodes(T-lchild)+nodes(T-rchild)+1)；三、二叉树相关算法的递归实现2. 求二叉树中所有结点数11第11页，共14页，2022年，5月20日，19点37分，星期三int f1( BiTree T ) if (T) if (T-lchild &(!T-rchi

8、ld) n+; if (!T-lchild) &T-rchild) n+; f1(T-lchild)； f1(T-rchild); 三、二叉树相关算法的递归实现3.求二叉树中度为1的结点个数12第12页，共14页，2022年，5月20日，19点37分，星期三int f2 ( BiTree T ) if (T) if (T-lchild &T-rchild) n+; f2(T-lchild)； f2(T-rchild); 三、二叉树相关算法的递归实现4.编写求二叉树中度为2的结点个数13第13页，共14页，2022年，5月20日，19点37分，星期三void Exchange ( BiTree &T )BiTree S;if (T) S=T-lchild; T-lc