如果我在数组中存储二叉树,我该如何避免浪费空间？

Question

通常我们需要算法中的树,然后我会得到一个有很多指针和递归的树.
有时我需要更高的速度,我将树放入2D数组,如下所示:

Example of a binary tree stored in an array
+-----------------+
|0eeeeeeeeeeeeeeee| //no pointers needed, parent/child, is y dimension,
|11       dddddddd| //sibbling is x dimension of the array.
|2222         cccc|  //The 123 tree is stored root up.
|33333333       bb|  //Notice how the abc-tree is stored upside down 
|4444444444444444a|  //The wasted space in the middle, is offset by the fact 
+-----------------+  //that you do not need up, down, and sibbling pointers.

我喜欢这个结构,因为它允许我加速使用指针和递归时我没有的选项.

但请注意中间浪费的空间....

如何摆脱/重用浪费的空间？

要求
我只使用这种结构,如果我需要最后一点速度,那么有大量翻译和地址计算的解决方案到达那个空间将没有用.

Answer 1

二进制树可以更高效地存储在数组中,如下所述:http://en.wikipedia.org/wiki/Binary_tree#Arrays:

来自维基百科:

在这种紧凑的安排中,如果一个节点有一个索引i,它的子节点在索引(2i + 1)(对于左子节点)和(2i + 2)(对于右边)中找到,而它的父节点(如果有的话)在索引处找到floor((i-1)/2)(假设根有索引为零) .

该方法受益于更紧凑的存储和更好的参考局部性,特别是在预订序遍历期间.然而,增长是昂贵的并且浪费空间与具有节点(2H - n)的高度树成比例.Hn

换句话说,如果您的树不是完整的二叉树,它将浪费空间,但它仍然比普通的2D阵列更紧凑.