在数组中存储二叉树

Question

假设有一个像下面那个需要存储在数组中的二叉树.

    7
   / \
  1  10
     /\
    9  11

我发现在数组中存储节点的公式从将根节点存储在位置0开始,然后对于索引处的每个节点i,其子节点都放在索引处(i*2)+1 and (i*2)+2.如果任一子array.length - 1节点的索引大于,那么该节点没有子节点.

所以我首先将7放在0位置,然后将其子1和10放在位置i2 + 1和i2 + 2位置为1和2:

|7|1|10| | | |      
 0 1 2  3 4 5

现在,我坚持使用没有任何孩子的节点1.我应该把它作为孩子们怎么样？

可以设置一些表示缺少节点的默认值,例如-1,如下所示:

|7|1|10|-1|-1|9|11|
 0 1 2  3 4 5 6  7

Answer 1

这种在数组中存储二叉树的算法是为树而设计的，使得从根节点开始的树的每个分支都具有相同的长度：数组大小基于树内的最大深度，然后分配一个等于或小于深度的每个树位置的数组位置。如果您有许多不同的分支长度，这可能不是适合您的正确算法。如果您的分支长度大部分是相同的深度，但有时在树的末端附近是空的，则放置“空”值（例如-1或 ）Integer.MIN_VALUE可能是一个合适的解决方案，只要您知道通常不需要放置任何 - 1 个值放入树中。

如果您碰巧知道您只会丢失树的最大深度级别的元素（如您提供的示例中所示），并且树的左/右顺序并不重要，您可以简单地对树进行重新排序，例如空值始终位于最底部、最右侧的位置，这也是数组末尾的位置集，从而使您的树成为完整的二叉树。然后，您只需要记住树中元素的数量，该数量比最后一个非空值的索引大一。图示：

    7
   / \
  10  1
  /\
 9  11
-->
|7|10|1|9|11|0|0|
 0 1  2 3 4  5 6 
length = 5 or lastIndex = 4