今日、私は二分木で問題をやっています。その間に、プロパティを満たすBSTreeの構造を見つけました:「すべてのノードは、左の子の値が小さく、右の子の値が大きい」. しかし、ルートはその孫の値よりも小さい値であるため、(私の意見では) BST ではありません。これをすべて説明してください。
二分木 :
7
/ \
4 10
/ \
2 8
これが BST かどうか教えてください。説明 。
8 > 7 ではありませんが、8 は 7 の左側にあります。
BST のより正確な定義は、次の場所にあります。
- ノードの左側のサブツリーには、ノードのキーより小さいキーを持つノードのみが含まれます。
- ノードの右側のサブツリーには、ノードのキー以上のキーを持つノードのみが含まれます。
- 左と右の部分木は両方とも二分探索木でなければなりません。
したがって、ツリーは、すべてのノードが左側に小さい値を持ち、右側に大きい値を持つという特定のケースを満たしますが、左と右のサブツリーを含むより一般的なケースを満たさないため、BST ではありません。
ツリーを順番にトラバースしてもソートされた出力が提供されないため、これはBSTではありません。主な原因は、値が8のノードです。ルートノードの左側のサブツリーにありますが、ルートノードである4よりも大きくなっています。