在数组中存储二叉树

Question

假设有一棵二叉树需要存储在数组中，如下所示。

    7
   / \
  1  10
     /\
    9  11

我发现在将节点存储到数组中时，公式从将根节点存储在位置0开始，然后对于索引为i的每个节点，它的子节点放置在索引(i*2)+1和(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

- VCODE

---

我不确定为什么你需要担心孩子们。如果你计划将其某个时候放回树中，那么你的树构建器将负责平衡，数组中应该只有树中的数字而没有任何占位符。 - David Coler

好问题。如果我是你，我会把-999999放在那里以显示 null。 - Kick Buttowski

为什么一个是，另一个是+？(i2)+1和(i+2)+2。 - Kick Buttowski

@KickButtowski，-999999是一个不好的空值常量选择；当事情恰好加起来等于-999999时，它只会鼓励出现奇怪的错误。更好的常量选择是-1（如果你从零开始加）或Integer.MIN_VALUE（如果你期望数字接近零并且可能会遇到int溢出问题）。 - Vitruvie

如果你想在数组中存储任意树形结构，很难做到优雅。你需要使用一维数据结构来表示二维结构，这就像是用一条一维线来表示一个平面。你需要进行簿记才能实现这一点。 - Jason Hu

Answer 1

这个用于将二叉树存储在数组中的算法是为了适用于每个从根节点开始的树枝具有相同长度的树：数组大小基于树中最大深度，然后为等于或小于该深度的每个树位置分配一个数组位置。如果您有许多不同的树枝长度，则可能不是正确的算法。如果您的树枝长度大多相同但有时在树的末端为空，则放置“null”值（例如-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

- Vitruvie

---

我认为这是有道理的。实际上，我正在学习堆，并看到一些例子，最右边的节点没有子节点，例如：http://en.wikipedia.org/wiki/Heap_%28data_structure%29#mediaviewer/File:Max-Heap.svg，我认为这只是一个巧合，并且很好奇如果左侧的节点没有子节点会怎样。所以，我可以假设有效的堆树在树的开始时不应为空吗？ - VCODE

@VCODE 为当你的树是完全的，比如表示堆时，添加了另一种解决方案。 - Vitruvie

Answer 2

我在考虑使用一些值来打破二叉树的属性。在一般的二叉树中，左边的节点总是比当前节点小，右边的节点总是比当前节点大。如果在左边遇到更高的节点或者在右边遇到更低的节点，则表示到达了末尾节点。

- ModProbe