Utilizzare l'albero in ordine traversale per determinare se un BST o un mucchio

Question

Dato questi elenchi di traversalità in ordine:
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

Devo determinare se ognuno di quegli elenchi rappresenta un valido BST / Min o Max Heap o None.
Stavo cercando di capire come avvicinarsi a questo, ma oltre a Brute-costringendo ogni possibile opzione non riuscivo a capire un modo "intelligente" per risolverlo.

Quali indicatori posso usare, se ce ne sono, o il modo per risolvere questo sarebbe letteralmente brutato forzando ogni opzione?

Answer 1

Nessuno di loro può essere un BST.Una traversata in ordine di un BST visita i vertici in ordine non decrescente delle loro chiavi (questo è facile da dimostrare per induzione).

Per determinare se sono cumuli, si noti che dal numero di elementi nell'elenco che già conosci la topologia dell'albero (i cumuli sono alberi completamente binari fino all'unico livello, e tutte le foglie sulL'ultimo livello è imballato sul lato sinistro).Quindi l'esercizio si riduce per scrivere le chiavi fornite nello stesso ordine del traversale e controllando se la proprietà heap tiene.

Nell'esempio specifico La prima sequenza non può essere una traversata in ordine di un mucchio poiché l'albero risultante avrebbe un percorso con tasti $ 23, 1, 53 $ (in un ordine crescente di profondità). Lo stesso argomento si applica alla seconda sequenza per un percorso con chiavi $ 71, 32, 49 $ .