[理工] [資結]-關於k-way tree

[fj90406 (阿亮)]

(a)What is the depth of a complete k-way tree with n nodes?

(b)Develop an algorithm to implement the recursive search
   of a binary search tree.

第一題 完全不知道如何下筆
第二題 是不是寫出 前序 中序 後序 其中一樣的演算法即可?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.127.186.2
推 abc73021:1.  log k底 n+1
→ abc73021:2.是要搜尋麼?   那你用中序前序後序  應該會很沒有效率
→ abc73021:左小右大  沒找到就一直呼叫自己，直到找到
→ abc73021:若是NULL 則找不到
→ hahaha86888:比root小就search左子樹 大就右子樹 一樣就output
→ xrodneylee:(a)我的想法是：k-way的最多node數是(k^h-1)/(k-1)
→ xrodneylee:所以(k^h-1)/(k-1)=n去推它的depth是log k底(nk-n+1)