1

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

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？）。

4

1 回答 1

2

这似乎是一棵没有平衡的普通二叉树。我想它是这样的：

根 -> 索引 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

For example, 15 is located at index 3. 30 is its right child and hence will be at index 2*3 + 2 = 8. 27 is the left child of the element at index 8 and hence located at index 2 * 8 + 1 = 17.

于 2012-04-16T13:57:31.210 回答