3

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

这可以做到吗？如何？

编辑：

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

我的问题：您能否将其概括为更通用的树，如上所述。

4

1 回答 1

2

如果我明白你想说的话（第 i 层的每个节点都有 n(i) 个子节点），那么很简单：第一个数字是根节点的 n(0) 个元素所占据的根节点，那么你把所有那些 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 件事：父索引和第一个子索引. 因为孩子是一个接一个，你总是可以接触到所有的孩子，你总是有父亲。（我会为根的父亲加上-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 是节点的索引。
你将有很多可用空间，但它是一个堆状结构
，希望对您有所帮助。

于 2012-06-24T18:46:19.567 回答