java - 二叉树数组迭代

Question

我有这个输出，我只需要理解，他们如何使用这些索引来表示二叉树？

How many numbers?: 6

Enter 1st number: 50
Enter 2nd number: 60
Enter 3rd number: 40
Enter 4th number: 15
Enter 5th number: 30
Enter 6th number: 27

BST Array:
[0]     50
[1]     40
[2]     60
[3]     15
[8]     30
[17]    27

它从0,1,2,3开始，然后突然转向索引8，然后17(我猜所有其他索引都是空的，但为什么索引8然后17？)。

Answer 1

这似乎是一个没有平衡的普通二叉树。我猜大概是这样的:

根 -> 索引 0

根/索引 0 的左侧 -> 索引 1

根/索引 0 的右侧 -> 索引 2

索引 1 左侧 -> 索引 3

索引 1 右侧 -> 索引 4

索引 2 左侧 -> 索引 5

索引 2 右侧 -> 索引 6

索引 3 左侧 -> 索引 7

索引 3 右侧 -> 索引 8

索引 4 左侧 -> 索引 9

索引 4 右侧 -> 索引 10

...

索引 i 的左侧 -> 2*i + 1

索引 i 的右侧 -> 2*i + 2

示例:

       50
      /  \
    40    60
  /
15
  \ 
  30
  /
 27

例如，15 位于索引 3 处。30 是其右子元素，因此位于索引 2*3 + 2 = 8 处。27 是索引 8 处元素的左子元素，因此位于索引 2 * 8 + 1 = 17。