推 Achen2211:求父節點不是應該用floor嗎??? 06/03 15:53
※ 引述《Achen2211 (阿辰)》之銘言：
: 如何陣列表示出分支度為d的完整樹上(d>1),位置i的節點,他的父和子位置公式是怎導
: 出啊?
: 我是畫圖出來root為1開始編號,然後第二層2~d+1,第三層d+2~2d+1,這樣下去....
: 請問公式要怎導出= =??
哦哦哦,看到一棵完整樹,意思應該是指樹裡面的節點盡量塞得緊緊的,
除了在最後一株非葉節點子樹中填不滿之外,其他的非葉節點子樹都是滿滿的.
這時就可以用前一題的知識,要先會算任何一層的最多節點數.
一棵完整樹分支度 d, 問位置 i, 可以先算位置 i 是高度多少.
假設高度 h, 則可以再算出一個序列代表每一層最多的節點數:
c[h] = {1, d, d^2, d^3, ... , d^(h-2), d^(h-1)}
先要看所指定位置 i 的節點,位於第 h 層,可以對應到 h-1 層的哪個節點.
先算出 k_h = i - sigma_{j=1..h-1}(d^(j-1)) 是指定節點在第 h 層的第 k_h 節點.
照理說是對應在 k_{h-1} = ceiling(k_h / d), 表示指定節點的父節點在第 h-1 層
的第 k_{h-1} 節點. 接著可以算出 k_{h-2} = ceiling(k_{h-1} / d) ... 等等.
條理大概是這樣. 數值上可能有估不準,請見諒.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.214.133