Verwenden Sie Treer-Travers-Traversal, um zu bestimmen, ob ein BST oder ein Haufen

Question

Angesichts dieser Reißverschlusslisten:
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

Ich muss feststellen, ob jede dieser Listen einen gültigen BST / MIN- oder MAX-Haufen oder keiner darstellt.
Ich versuchte herauszufinden, wie man sich an diesen annähern, aber neben der brutischen Erzwinge der möglichen Option konnte ich nicht einen "intelligenten" Weg finden, um dies zu lösen.

Welche Indikatoren kann ich verwenden, wenn es irgendeine gibt, oder der Weg zur Lösung würde buchstäblich brutal sein, wenn er jede Option zwingt?

Answer 1

In keiner von ihnen kann ein BST sein.Ein Traversal in der Reihenfolge eines BST besucht die Scheitelpunkte in nicht abnehmender Reihenfolge ihrer Schlüssel (dies ist leicht nach Induktion zu beweisen).

, um festzustellen, ob sie in Haufen sind, beachten Sie, dass durch die Anzahl der Elemente in der Liste, die Sie bereits kennen, die Topologie des Baums (Haufen völlig binäre Bäume befinden, bis zur einmaligen Ebene, und alle Blätter auf derDie letzte Ebene sind auf der linken Seite verpackt).Dann läuft die Übung nach unten, um die angegebenen Tasten in derselben Reihenfolge des Durchlaufs zu schreiben und zu überprüfen, ob die HEAP-Eigenschaft gilt.

Im speziellen Beispiel kann die erste Sequenz nicht ein Traversal in der Reihenfolge eines Heaps sein, da der resultierende Baum einen Pfad mit Tasten 23, 1, 53 $ hat(in zunehmender Reihenfolge der Tiefe). Das gleiche Argument gilt für die zweite Reihenfolge für einen Pfad mit den Tasten $ 71, 32, 49 $ .