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

たとえば、15はインデックス3にあり、30はその右の子であるため、インデックス2 * 3 + 2 = 8になります。27は、インデックス8の要素の左の子であるため、インデックス2 * 8+1にあります。 =17。

于 2012-04-16T13:57:31.210 に答える