[請益] binary tree 計算高度

作者: lyc811123 (L.Y.C)   2017-05-20 13:27:24
演算法的內容是這樣的
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;
}
}
想請問他的遞迴到底是怎麼運作的,
思考了很久還是不知到他遞迴是怎麼跑的…
可以麻煩大家幫小弟解答嗎?
謝謝大家!
作者: jachin (火腿哥)   2017-05-20 14:18:00
你要不要先找簡單的遞迴程式先瞭解遞迴(例如n階乘或費氏級數)程式的意思是終止條件為指標T==null,往左右子樹指標追蹤,回傳左右子樹高度;並在每次只回傳max(左右子樹高度),最後一層的遞迴一定有一方是0,則回傳0,倒數第二層max(0,0)+1,依此方式層層拆解遞迴,最後一個+1是root
作者: lyc811123 (L.Y.C)   2017-05-20 15:15:00
費式階層我都明白…只是不知道為什麼變成節點就卡卡的。謝謝你,講解清楚感恩!!
作者: wave1et (百分百殖利率)   2017-05-20 18:11:00
stack 的觀念弄懂就清楚了,

Links booklink

Contact Us: admin [ a t ] ucptt.com