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

看板Grad-ProbAsk作者 (阿亮)時間16年前 (2010/03/04 17:05), 編輯推噓1(1推 0噓 6→)
留言7則, 3人參與, 最新討論串1/1
(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
推
03/04 17:08, , 1F
1. log k底 n+1
03/04 17:08, 1F
→
03/04 17:10, , 2F
2.是要搜尋麼? 那你用中序前序後序 應該會很沒有效率
03/04 17:10, 2F
→
03/04 17:11, , 3F
左小右大 沒找到就一直呼叫自己，直到找到
03/04 17:11, 3F
→
03/04 17:11, , 4F
若是NULL 則找不到
03/04 17:11, 4F
→
03/04 18:30, , 5F
比root小就search左子樹 大就右子樹 一樣就output
03/04 18:30, 5F
→
03/04 19:49, , 6F
(a)我的想法是：k-way的最多node數是(k^h-1)/(k-1)
03/04 19:49, 6F
→
03/04 19:51, , 7F
所以(k^h-1)/(k-1)=n去推它的depth是log k底(nk-n+1)
03/04 19:51, 7F
‣ 更多 fj90406 的文章
文章代碼(AID): #1BZtVIZ2 (Grad-ProbAsk)