data-structures - 使用数组表示的二叉树

Question

考虑下面的数组，它声称代表了一个二叉树:

[1, 2, 5, 6, -1, 8, 11]

鉴于值为 -1 的索引表示根元素，我有以下问题:

a) 这实际上是如何表示的？

我们是否应该遵循以下公式( source from this link )来计算树？
三个简单的公式允许您从父项的索引到其子项的索引，反之亦然:

* if index(parent) = N, index(left child) = 2*N+1
* if index(parent) = N, index(right child) = 2*N+2
* if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation)

如果我们使用上面的公式，那么index(root) = 3, index(left child) = 7，不存在。

b) 知道它是否是一棵完整的二叉树很重要吗？

Answer 1

N=0 必须是根节点，因为根据列出的规则，它没有父节点。 0 不能从表达式 (2*N + 1) 或 (2*N + 2) 中的任何一个创建，假设没有负 N。

注意，索引不是数组中存储的值，而是数组中的位置。
对于 [1, 2, 5, 6, -1, 8, 11]
索引 0 = 1
索引 1 = 2
索引 2 = 5，以此类推。

如果它是一棵完整的树，那么 -1 是一个有效值，树是

    1  
   /  \  
  2    5  
 / \  / \  
6 -1 8  11  

-1 也可以是“NULL”指针，表示该节点不存在任何值。

所以树看起来像

    1  
   / \  
  2   5  
 /   / \  
6   8  11