Come molti attraversamenti devono essere conosciuti per costruire un BST

Question

Sono molto confuso da un certo numero di articoli in siti diversi per quanto riguarda la costruzione di un Binary Search Tree da qualsiasi attraversamento (pre, post o in-order), o una combinazione di due di loro . Ad esempio, alla pagina this, si dice che dato l'attraversamento dell'ordine pre,o level, insieme con l'attraversamento in-order, si può costruire lo BST. Ma here e there, ci mostrano di costruire un BST da pre-order da solo. Inoltre, here ci mostrano come costruire il BST dagli attraversamenti dati pre e post-order. In qualche altro sito, ho trovato una soluzione per la costruzione di un BST solo dal traversal post-order.

Ora so che dati gli attraversamenti inorder e pre-order, è possibile formare univocamente uno BST. Per quanto riguarda il primo link ho fornito, anche se dicono che non possiamo costruire il BST da pre-order e post-order, non posso semplicemente ordinare l'array post-order per ottenere il suo inorder attraversamento, e quindi utilizzare tale e la matrice pre-order per formare la BST? Sarà uguale alla soluzione nel 4 ° link o differente? E dato solo pre-order, posso ordinarlo per ottenere lo in-order, quindi usare quello e lo pre-order per ottenere lo BST. Ancora una volta, deve essere diverso dalla soluzione ai link 2 e 3?

In particolare, cosa è sufficiente per generare in modo univoco il BST? Se uniquement non è richiesto, posso semplicemente ordinarlo per ottenere l'attraversamento in-order e creare uno degli N possibili BST da esso in modo ricorsivo.

Answer 1

Per costruire un BST è necessario solo un traversamento (non in corso).

In generale, per costruire un albero binario saranno necessari due attraversamenti, in ordine e pre-ordine per esempio. Tuttavia, per il caso speciale di BST, l'attraversamento in-order è sempre la matrice ordinata contenente gli elementi, in modo da poter sempre ricostruirla e utilizzare un algoritmo per ricostruire un albero generico dagli attraversamenti in preordine e in ordine.

Quindi, l'informazione che l'albero è un BST, insieme agli elementi in esso contenuti (anche non ordinati) sono equivalenti a un traversamento in ordine.

Bonus: perché un attraversamento non è sufficiente per un albero generale, (senza le informazioni è un BST)?
Risposta: Supponiamo di avere n elementi distinti. Ci sono n! liste possibili per questi elementi n, tuttavia - il numero possibile di alberi è molto più grande (2 * n! Possibili alberi per gli n elementi sono tutti alberi decaduti, tale che node.right = null in ogni nodo, quindi l'albero è in realtà un elenco a destra, ci sono gli alberi n! e un altro n! alberi dove sempre node.left = null) Quindi, dal principio del piccione - c'è almeno una lista che genera 2 alberi, quindi non possiamo ricostruire l'albero da una singola traversata. (QED)

Answer 2

Se vengono forniti i valori per i nodi del BST, è sufficiente un solo attraversamento perché il resto dei dati è fornito dai valori dei nodi.Ma se i valori sono sconosciuti, non è possibile, come per la mia comprensione, costruire un BST unico da una singola traversata. Tuttavia, sono aperto a suggerimenti.