如何在陣列中存儲樹狀樹？

Question

我想在一個數組中存儲一棵樹，同時能夠很容易地從當前索引計算父子索引，就像在二進制堆中一樣。該樹有一個單根節點，該節點處於0級。該樹有N個級別，級別i上的每個節點都有n（i）個子節點。

可以這樣做嗎？怎麼樣？

編輯：

澄清：可以存儲（完整的）二叉樹，即以存儲堆，在單個陣列中而不顯式存儲的索引。根在0處，位置i處的節點的子節點在2i + 1和2i + 2中。所以你可以從計算這個孩子從父節點的索引，而實際上不需要存儲這個索引。數據結構是數據隱含，看到http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

我的問題：你能概括這更一般的樹，如上文詳述。

Answer 1

如果我明白你想說什麼（每個節點在第一級有n（i）個孩子），那麼很簡單：第一個數字是根作爲根子的n（0）元素休耕的根，然後你把所有n（0）點都放在n（1）個節點上。 如果你有n（0）= 3，那麼第一次你把n（1）點頭，然後你把所有的n（1）點頭，如果第二個點頭，並且之後n（1）點頭爲3點頭

1 -> 2, 5, 3 (1 is the root, and has 2, 5, 3 as children) 
2 -> 4, 10 
3 -> 45, 35 
5-> 12, 31 
n(0) = 3, n(1) = 2 , n(2) = 0 
Then You should have: {1, 2, 5, 3, 4, 10, 45, 35, 12, 31} 

對於你應該保持與父親位置的另一個陣列和另一個與第一個孩子索引，如果你真的想只有一個數組，你應該做一個很好的指標：
對於每個元素保持3件事：父親索引和第一個孩子索引。 因爲孩子是一個接一個的，你將總是有機會獲得所有的孩子 ，你就會擁有父親。 （我會把-1根的父親） 那麼你應該有：

{1,-1, 3, 2, 0,12, 5, 0, x, 3, 0, x,  4, 3, x, ... } 
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ... } 
-1 is the father of 1 and 3 is the start of his child 
0 is the father of 1 and 12 is the start of his child (4 in this case) 

如果你想要一個「堆」結構，你必須要找到孩子的最大號MX =（MAX（N（I） ），1 < = i < = N並且做一個步驟爲MX的堆，每個元素將有他們的孩子在pos * MX，pos * MX + 1，..pos * MX + n（k），並且父親在pos/MX，其中pos是該節點的索引。
你將有很多自由空間的，但是是一個堆狀stuture
我希望它可以幫助你。