Definisci un BST come: tutti i discendenti di sinistra < = n < tutti i discendenti giusti.
Quindi è possibile costruire due alberi di ricerca binari con strutture diverse ma con gli stessi valori esatti? I valori duplicati sono consentiti.
Definisci un BST come: tutti i discendenti di sinistra < = n < tutti i discendenti giusti.
Quindi è possibile costruire due alberi di ricerca binari con strutture diverse ma con gli stessi valori esatti? I valori duplicati sono consentiti.
Sì, ci possono essere vari BST composti dagli stessi numeri. Prendiamo i numeri 1, 2, 3.
Se l'ordine in cui li aggiungi all'albero è 1, 2, 3 l'albero avrà 1 come radice, 2 come nodo destro e 3 come nodo destro 2.
Se l'ordine è 2, 1, 3 l'albero avrà 2 come radice, 1 come nodo sinistro e 3 come nodo destro.
Se l'ordine è 3, 1, 2 allora l'albero avrà 3 come radice, 1 come nodo sinistro e 2 come nodo destro di 1. ecc.
Sì. La struttura del BST si basa sull'ordine jn al quale vengono aggiunti gli elementi. Quindi, se si usano gli stessi elementi, ma si popola in un ordine diverso, si otterrà un albero diverso.
Leggi altre domande sui tag data-structures binary-tree