BSTまたはヒープがあるかどうかを判断するには、ツリーインオーダートラバーサルを使用します。

Question

これらの注文のトラバーサルリストを考える：
1. 53,1,64,23,3,29,17,2,9,19
2. 49,32,51,71,32,10,21,8,13,11,11,17

これらのリストのそれぞれが有効なBST / MINまたはMAXヒープを表すかどうかを判断する必要があります。
私はこれに近づく方法を理解しようとしていましたが、あらゆる可能性のあるオプションを強制的に強制するだけでなく、これを解決するための「スマート」方法を理解できませんでした。

これを解決する方法、またはこれを解決する方法は、文字通りすべてのオプションを強制する方法を使用することができますか？

Answer 1

それらのどれもBSTでもありえない。BSTの順番の横断面は、それらのキーの順に頂点を訪問します（これは誘導によって証明するのは簡単です）。

ヒープであるかどうかを判断するには、リスト内の要素数でツリーのトポロジを既に知っていることに注意してください（ヒープは完全にバイナリツリー、最後のレベルまで、最後のレベルは左側にパックされます）。それから、運動はトラバースの同じ順序で与えられたキーを書き留め、ヒーププロパティが保持されているかどうかを確認します。

具体例では、最初のシーケンスは、結果のツリーがキーを持つパスがあるため、ヒープの順序で順番に実行できません。 $ 23,1,53 $ （深さの順序が増えている）。 同じ引数は、キー $ 71,32,49 $ を持つパスの2番目のシーケンスに適用されます。