5

今日、私は二分木で問題をやっています。その間に、プロパティを満たすBSTreeの構造を見つけました:「すべてのノードは、左の子の値が小さく、右の子の値が大きい」. しかし、ルートはその孫の値よりも小さい値であるため、(私の意見では) BST ではありません。これをすべて説明してください。

二分木 :

      7
     /  \
    4    10
   / \
  2   8

これが BST かどうか教えてください。説明 。

4

3 に答える 3

4

8 > 7 ではありませんが、8 は 7 の左側にあります。

于 2012-09-07T04:33:19.110 に答える
4

BST のより正確な定義は、次の場所にあります。

  • ノードの左側のサブツリーには、ノードのキーより小さいキーを持つノードのみが含まれます。
  • ノードの右側のサブツリーには、ノードのキー以上のキーを持つノードのみが含まれます。
  • 左と右の部分木は両方とも二分探索木でなければなりません。

したがって、ツリーは、すべてのノードが左側に小さい値を持ち、右側に大きい値を持つという特定のケースを満たしますが、左と右のサブツリーを含むより一般的なケースを満たさないため、BST ではありません。

于 2012-09-07T04:49:50.393 に答える
0

ツリーを順番にトラバースしてもソートされた出力が提供されないため、これはBSTではありません。主な原因は、値が8のノードです。ルートノードの左側のサブツリーにありますが、ルートノードである4よりも大きくなっています。

于 2012-09-07T08:53:33.100 に答える