使用数组表示二叉树

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)

如果我们使用上述公式，则根的索引为3，左子节点的索引为7，但该节点不存在。

b）是否重要知道它是完全二叉树还是不完全二叉树？

- Sanjeev Kulkarni N

Answer 1

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

注意，索引并不是数组中存储的值，而是数组中的位置。 对于[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  

- J Yu

---

值得注意的是，可以通过查看索引（i-1）/2的位置来访问索引为i的节点的父节点。 - Saraph

即使i是偶数，它也必须满足floor((i-1)/2)的条件。 - Tilak Madichetti

Answer 2

给定一个数组，你可以想到很多种方式来表示它如何成为一棵二叉树。因此没有办法知道它代表什么，你必须去查找该数组的源代码（无论那是什么）。

其中一种方法通常用于表示二叉堆，就像您提供的链接一样。如果使用的是这种表示方法，则-1不会是根元素。在位置3的节点将没有任何子节点，即它将是一片叶子。

是完整二叉树还是非完整二叉树可能很重要。

通常情况下，您不应该像这样尝试弄清楚某些数据的含义。您应该获得使用数据的文档或源代码。如果您没有这个，但确实需要反向工程，那么您很可能需要更多了解这些数据的信息。观察使用它的代码行为应该会有所帮助。或者反编译代码。

- svick

Answer 3

它可能不是完全二叉树，但也不是任意的二叉树。你可以表示一棵树，其中最多有几个右侧的叶子节点缺失（或者，如果你交换左右子节点的约定，最多有几个左侧的叶子节点缺失）。

你无法在数组中表示这个：

    A
   / \
  B   C
 /   / 
D   E

但是您可以表示这个

    A
   / \
  B   C
 / \  
D   E

或者这样：

    A
   / \
  B   C
     / \  
    D   E

（对于最后一个节点，将2k+1作为右子节点，将2k+2作为左子节点）

你只需要知道这三个节点的数量。

- chill