data-structures - 如何在数组中存储树状树？

Question

我想在数组中存储一棵树，同时能够从当前索引轻松计算父索引和子索引，就像在二叉堆中一样。树有一个根节点，位于第 0 层。树有 N 层，第 i 层的每个节点都有 n(i) 个子节点。

这能做到吗？如何？

编辑:

说明:您可以在单个数组中存储(完整的)二叉树，即存储堆，而无需显式存储索引。根在 0 处，位置 i 的节点的子节点在 2i+1 和 2i+2 中。因此，您可以根据父节点的索引计算子节点，而无需实际存储索引。数据结构隐含在数据中，见http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

我的问题:您能否将其概括为更一般的树，如上所述。

Answer 1

如果我明白你想说的话(第 i 层的每个节点都有 n(i) 个 child )那么很简单:第一个数字是被 n(0) 个元素所允许的根，这些元素是根的 child ，那么你把所有的那些 n(0) 点点头所有的 n(1) 节点。
如果你有 n(0) = 3，那么对于第一个你放 n(1) 个点头，在它们之后你把所有的 n(1) 个点头，如果第二个点头，然后在那些之后 n(1) 个点头，第三个点头

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 样东西:父索引和第一个子索引。
因为 child 是一个又一个，所以你总是可以接触到所有的 child
你将永远拥有父亲。 (我会为根的父亲放 -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)

如果你想要一个“堆”结构，你必须找到最大数量的 child Mx = ( max(n(i)), 1<=i<=N 并用步骤 MX 做一个堆，每个元素都会有他们的 child 在pos*MX, pos*MX + 1, ..pos*MX + n(k)，以及 pos/MX 处的父节点，其中 pos 是节点的索引。
你会有很多空闲空间但是是一个堆状结构
我希望它能帮助你。