考試

binary tree 計算高度 - 考試

Todd Johnson avatarTodd Johnson · 2017-05-20

Table of Contents

演算法的內容是這樣的

int height(Node*T)
{
if(T==null)return 0；
else
{
int hL=height(T->Lchild)；
int hR=height(T->Rchild)；
return max(hL,hR)+1；
}
}
想請問他的遞迴到底是怎麼運作的，
思考了很久還是不知到他遞迴是怎麼跑的…
可以麻煩大家幫小弟解答嗎？
謝謝大家！

--
考試

All Comments

Gilbert avatarGilbert2017-05-20
你要不要先找簡單的遞迴程式先瞭解遞迴(例如n階乘或費氏級
數)
程式的意思是終止條件為指標T==null，
往左右子樹指標追蹤，回傳左右子樹高度;並在每次只回傳max
(左右子樹高度)，
最後一層的遞迴一定有一方是0，則回傳0，倒數第二層max(0
，0)+1，依此方式層層拆解遞迴，最後一個+1是root
Elizabeth avatarElizabeth2017-05-22
費式階層我都明白…只是不知道為什麼變成節點就卡卡的
。謝謝你，講解清楚感恩！！
Barb Cronin avatarBarb Cronin2017-05-26
stack 的觀念弄懂就清楚了，