c - BSTの性質を満たす木ですが、BSTではないと思いますか？

Question

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

二分木 :

      7
     /  \
    4    10
   / \
  2   8

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

Answer 1

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

Answer 2

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

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

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

Answer 3

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