遞歸及其在二叉樹中的應用

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

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

hanoi塔問題5第五頁，共十四頁，2022年，8月28日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，Z作輔助塔座move(x,n,z);//將編號為n的圓盤從X搬到Zhanoi(n-1,y,x,z);//將Y上編號為1至n-1的圓盤移到Z，Y作輔助塔座}}

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

}三、二叉樹相關算法的遞歸實現1.求二叉樹中葉子結點個數10第十頁，共十四頁，2022年，8月28日voidnodes(BiTreeT){//計算以二叉鏈表為存儲結構的二叉樹的所有結點數if(!T)return0;elseif((!T->lchild)&&(!T->rchild))return1;elsereturn(nodes(T->lchild)+nodes(T->rchild)+1)；}三、二叉樹相關算法的遞歸實現2.求二叉樹中所有結點數11第十一頁，共十四頁，2022年，8月28日intf1(BiTreeT){if(T){if(T->lchild&&(!T->rchild))n++;if((!T->lchild)&&T->rchild)n++;f1(T->lchild)；f1(T->rchild);}}三、二叉樹相關算法的遞歸實現3.求二叉樹中度為1的結點個數12第十二頁，共十四頁，2022年，8月28日intf2(BiTreeT){if(T){if(T->lchild&&T->rchild)n++;f2(T->lchild)；f2(T->rchild);}}三、二叉樹相關算法的遞歸實現4.編寫求二叉樹中度為2的結點個數13第十三頁，共十四頁，2022年，8月28日voidExchange(BiTree&T){ BiTreeS; if(T){ S=T->lchild; T->l