使用数组表示的二叉树

Question

考虑以下数组,声称代表了二叉树:

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

鉴于值为-1的索引表示根元素,我在下面的问题:

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

我们应该遵循以下公式(来自此链接的来源)来找出树吗？三个简单的公式允许您从父项的索引转到其子项的索引,反之亦然:

* 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必须是根节点,因为根据列出的规则,它没有父节点.假设没有负N,则不能从表达式(2*N + 1)或(2*N + 2)中的任何一个创建0.

注意,index不是存储在数组中的值,而是数组中的位置.对于[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  

Answer 2

给定一个数组,您可以想出该数组如何表示二叉树的任何方式.所以没有办法知道,你必须去那个数组的源(无论是什么).

其中一种方法是二进制堆通常表示的方式,根据您的链接.如果这是使用的表示,则-1将不是根元素.并且位置3处的节点将没有子节点,即它将是叶子.

并且,是的,知道它是否应该是完整的树可能很重要.

一般来说,你不应该试图弄清楚一些数据是什么意思.您应该获得文档或使用数据的源代码.如果您没有,并且您确实需要对其进行逆向工程,那么您很可能需要了解有关数据的更多信息.观察使用它的代码的行为应该对您有所帮助.或者反编译代码.