二叉樹遞歸演算法

A. 二叉樹的遞歸演算法到底該怎麼理解

這不就是在二叉排序樹上的遞歸查找，看程序
tree&
find(const
T&
d,
tree&
t){
if(t==NULL)
return
t;如果二叉樹為空則返回空，查找失敗
if(t->data==d)
return
t;否則，如果當前根結點關鍵碼為d，則查找成功，當前根結點為待查找結點
if(d>t->data)
return
find(d,
t->right);如果比根的關鍵碼大就遞歸查找右子樹
return
find(d,
t->left);如果比根的關鍵碼小就遞歸查找左子樹
}
二叉樹的遞歸定義的含義就是非空二叉樹，除了根以外，左右子樹都是二叉樹（可以為空）

B. Java數據結構二叉樹深度遞歸調用演算法求內部演算法過程詳解

二叉樹
1
2 3
4 5 6 7
這個二叉樹的深度是3，樹的深度是最大結點所在的層，這里是3.

應該計算所有結點層數，選擇最大的那個。

根據上面的二叉樹代碼，遞歸過程是：

f(1)=f(2)+1 > f(3) +1 ? f(2) + 1 : f(3) +1

f(2) 跟f(3)計算類似上面，要計算左右結點，然後取大者

所以計算順序是f(4.left) = 0, f(4.right) = 0

f(4) = f(4.right) + 1 = 1

然後計算f(5.left) = 0,f(5.right) = 0

f(5) = f(5.right) + 1 =1

f(2) = f(5) + 1 =2

f(1.left) 計算完畢，計算f(1.right) f(3) 跟計算f(2)的過程一樣。

得到f(3) = f(7) +1 = 2

f(1) = f(3) + 1 =3

if(depleft>depright){
returndepleft+1;
}else{
returndepright+1;
}

只有left大於right的時候採取left +1，相等是取right

C. 用遞歸演算法先序中序後序遍歷二叉樹

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

棗蘆 printf(「%d 」, BT->Data); //對節點做些訪問比如列印

PreOrderTraversal(BT->Left); //訪問左兒子

PreOrderTraversal(BT->Right); //訪問右兒子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、後序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(3)二叉樹遞歸演算法擴展閱讀：

注意事項

1、前序遍歷

從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。

2、中序遍歷

從整棵凳滑帶二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若讓襲LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。

3、後序遍歷

將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。

D. 編寫遞歸演算法，求二叉樹的結點個數和葉子數

00DLR(liuyu *root) /*中序遍歷 遞歸函數*/
{if(root!=NULL)
{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);}
DLR(root->lchild);
DLR(root->rchild); }
return(0);
}
法二：
int LeafCount_BiTree(Bitree T)//求二叉樹中葉子結點的數目
{
if(!T) return 0; //空樹沒有葉子
else if(!T->lchild&&!T->rchild) return 1; //葉子結點
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子樹的葉子數加
上右子樹的葉子數
}//LeafCount_BiTree

註：上機時要先建樹！例如實驗二的方案一。
① 列印葉子結點值（並求總數）
思路：先建樹，再從遍歷過程中列印結點值並統計。

E. 先序遍歷二叉樹的遞歸演算法怎樣理解

二叉樹的結點結構是:
1、根結點（存放結點數據）
2、左子樹指針
3、右子樹指計
對二叉樹的遍歷就是訪問各個結點中根結點里存放的數據。例如：
如果結點A有左結點B，右結點C，記作A(B,C)，不同結點我用"\"隔開。那麼有這樣一個(BitTree)二叉樹表A(B,C) \B（D,E)\E(F.G)\C(空,H)\H(I.空)， 自己畫出來，不然我後面白講了。
要想把所有的數據都訪問到則必需按照一定的原則，即當前結點的下一個結點是哪個結點。
無論是先、中還是後序演算法都是先將左結點視為下一個結點，當左結點不存在（即為空時）才將右結點視作下一個結點，如果右結點也不存在就返回當前結點的上層結點再向右訪問，如此類推。
於是對二叉樹的遍歷問題就被抽象成三個基本步驟:
1、訪問根結點。
2、訪問該點的所有左子樹。
3、訪問該點的所有右子樹。
先序遍歷的策略是按123的步驟執行，中序是按213來，後序則是231,它們之間的不同只是「訪問根結點」在這三個步驟中的位置。
看著你剛畫好的那個BitTree跟著我的思路走。在先序遍歷演算法PriorOrder中,先將BitTree的頭結點A傳進來，按步驟123的處理。123是抽象實現，記住所表達的思想，下面是具體實現。為了避免混亂用中文數字記錄步驟。
一、即是讀取結點A的數據內容A（此時A為當前函數處理結點)，將A的右結點C放入棧S中，S中的內容為S（C）[注意這一步是演算法的一個輔助，並不是先向右訪問,下同]，將左結點B傳給PriorOrder處理。此時讀取了A
二、讀取B的內容B（此時B為當前結點），將B的右結點E放入S中，S中的內容為S(C,E),將B的左結點D傳給PriorOrder處理。此時讀取了AB
三、D為當前結點，D的右為空沒有東西放入S，S中的內容仍為S(C,E)，D的左也為空，沒有訪問可訪問的。此時就從S中取出E(因為棧是先進後出的所以取的就是E，此時S中的內容為S(C),正好是上一層沒訪問過的右子樹)，將E傳給PriorOrder處理。此時讀取了AB D
四、E為當前結點，對於結點E類似的有S(C,G),讀取了ABDE,將F傳入PriorOrder
五、F為當前結點，右為空，左也為空，讀取了ABDEF,從棧中取出G傳給PriorOrder處理,S的內容為S(C);
六、類似的讀取了ABDEFG,從S中取出了C，傳給PriorOrder處理。此時S（）。
七、當前結點為C，從將C的右結點放入S，S中內容為S(H),C的左為空，從S取出H，將H傳給PriorOrder處理。此時S為S().於是就讀取了ABDEFGC
八，類似的讀取了ABDEFGCH
九，最後ABDEFGCHF
你再對照的書上的演算法想想，畫畫就應該能明白點。特別要理角的一點是為什麼用遞歸演算法時計算機能按這樣的方式是因為函數調用是「先調用，後執行完」，或者說「後調用，先執行完」。注意我加一個「完」字

F. 求統計二叉樹葉子結點數的遞歸演算法

···cpp

由於不知道你的存儲方式，假設你是指針存，用孩子兄弟表示法。

（偽）代碼：

structnode{
data{
...
}val;
node*fchild,*brother;
}
voidgetnum(nodex){
if(x.fchild==nu)ans++;
else{
getnum(*x.fchild);
getnum(*x.brother);
}
}

就這樣