使用数组表示的二叉树-Java 学习之路

考虑以下数组，声称代表了二叉树：

[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）知道它是否是完整的二叉树是否重要？

3 回答

14

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

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

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

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

回复于 2024-04-27T08:59:59+08:00
0
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
```
回复于 2024-04-27T08:59:59+08:00
8
它可能不是一个完整的二叉树，但它也可能不是任意的 . 你可以代表一棵树，其中最多只有一些最右边的叶子缺失（或者，如果你为左右儿童交换约定，最多只剩下最左边的一些叶子） .

你不能在你的数组中表示这个：
```
A
   / \
  B   C
 /   / 
D   E
```
但你可以代表这一点
```
A
   / \
  B   C
 / \  
D   E
```
或这个：
```
A
   / \
  B   C
     / \  
    D   E
```
（最后，有2k 1是正确的孩子，2k 2是左孩子）

您只需知道三者中的节点数 .
回复于 2024-04-27T08:59:59+08:00

使用数组表示的二叉树

3 回答

相关问题