遞歸及其在二叉樹中的應用1第一頁，共十四頁，編輯于2023年，星期五二階費波納奇數(shù)列具體實現(xiàn)如下：longFib(intn){ if(n==0)return0; if(n==1)return1; returnFib(n-1)+Fib(n-2);}2第二頁，共十四頁，編輯于2023年，星期五二、遞歸函數(shù)適用的場合在解決現(xiàn)實問題中，對于求解一個復雜的或者問題規(guī)模較大的問題，可以將其劃分為一些簡單的或者規(guī)模較小的問題進行解決，如果這種劃分滿足：所劃分成的子問題性質(zhì)與原來的大問題相同。當問題規(guī)模小到一定程度的時候直接有解。對于滿足以上條件的問題我們就可以考慮使用遞歸的方法求解。遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。

3第三頁，共十四頁，編輯于2023年，星期五hanoi塔問題問題描述：假設(shè)有三個分別命名為X、Y、Z的塔座，在X塔座上疊放著n個小盤壓大盤的圓盤堆，要求將塔座X上的n個圓盤移至塔座Z上，并按同樣順序疊放。要求：1、每次只能移動一個圓盤；2、圓盤可以放在X、Y、Z中的任意塔座上；3、任何時刻都不能將大盤壓在小盤上；XYZXYZ4第四頁，共十四頁，編輯于2023年，星期五如果有一個盤子，直接從X移到Z即可。如果有n個盤子要從X移到Z，Y作為輔助。問題可以轉(zhuǎn)化為，先將上面n-1個從X移動到Y(jié)，Z作為輔助，然后將第n個從X移動到Z，最后將剩余的n-1個從Y移動到Z，X作為輔助。

hanoi塔問題5第五頁，共十四頁，編輯于2023年，星期五Voidhanoi(intn,charx,chary,charz){//將塔座X上按直徑由小到大且自上而下編號為1至n的n個圓盤按規(guī)則搬到塔座Z上，Y作為輔助塔座。//搬動操作move(x,n,z)if(n==1)move(x,1,z);//將編號為1的圓盤從X搬到Zelse{hanoi(n-1,x,z,y);//將X上編號為1至n-1的圓盤移到Y(jié)，Z作輔助塔座move(x,n,z);//將編號為n的圓盤從X搬到Zhanoi(n-1,y,x,z);//將Y上編號為1至n-1的圓盤移到Z，Y作輔助塔座}}

hanoi塔問題6第六頁，共十四頁，編輯于2023年，星期五voidPreOrderTraverse(BiTreeT){//采用二叉鏈表存儲結(jié)構(gòu)先序遍歷二叉樹T的遞歸算法if(T){Visit(T->data)；PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}先序遍歷遞歸算法三、二叉樹相關(guān)算法的遞歸實現(xiàn)7第七頁，共十四頁，編輯于2023年，星期五中序遍歷遞歸算法voidInOrderTraverse(BiTreeT){if(T){ InOrderTraverse(T->lchild); Visit(T->data)； InOrderTraverse(T->rchild); }}三、二叉樹相關(guān)算法的遞歸實現(xiàn)8第八頁，共十四頁，編輯于2023年，星期五后序遍歷遞歸算法voidPostOrderTraverse(BiTreeT){if(T){ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); Visit(T->data)； }}三、二叉樹相關(guān)算法的遞歸實現(xiàn)9第九頁，共十四頁，編輯于2023年，星期五intLeaf_Count1(BitreeT){if(!T)return0;//空樹沒有葉子結(jié)點elseif((!T->lchild)&&(!T->rchild))return1;//只有一個根結(jié)點elsereturnLeaf_Count1(T-lchild)+Leaf_Count1(T-rchild);//左子樹中的葉子結(jié)點數(shù)加上右子樹中的葉子結(jié)點數(shù)

}三、二叉樹相關(guān)算法的遞歸實現(xiàn)1.求二叉樹中葉子結(jié)點個數(shù)10第十頁，共十四頁，編輯于2023年，星期五voidnodes(BiTreeT){//計算以二叉鏈表為存儲結(jié)構(gòu)的二叉樹的所有結(jié)點數(shù)if(!T)return0;elseif((!T->lchild)&&(!T->rchild))return1;elsereturn(nodes(T->lchild)+nodes(T->rchild)+1)；}三、二叉樹相關(guān)算法的遞歸實現(xiàn)2.求二叉樹中所有結(jié)點數(shù)11第十一頁，共十四頁，編輯于2023年，星期五intf1(BiTreeT){if(T){if(T->lchild&&(!T->rchild))n++;if((!T->lchild)&&T->rchild)n++;f1(T->lchild)；f1(T->rchild);}}三、二叉樹相關(guān)算法的遞歸實現(xiàn)3.求二叉樹中度為1的結(jié)點個數(shù)12第十二頁，共十四頁，編輯于2023年，星期五intf2(BiTreeT){if(T){if(T->lchild&&T->rchild)n++;f2(T->lchild)；f2(T->rchild);}}三、二叉樹相關(guān)算法的遞歸實現(xiàn)4.編寫求二叉樹中度為2的結(jié)點個數(shù)13第十三頁，共十四頁，編輯于2023年，星期五voidExchange(BiTree&T){ BiTreeS; if(T){ S=T->lchild; T->lc