Esame di algoritmi e strutture dati - risoluzione esercizio abr

di il
1 risposte

Esame di algoritmi e strutture dati - risoluzione esercizio abr

Salve non riesco a risolvere questo esercizio in maniera efficiente:

Sia dato un albero binario di ricerca T ed un array ordinato A contenente m chiavi. Scrivere un algoritmo ricorsivo efficiente che inserisca nell'albero T tutte le chiavi di A che non siano già presenti in T. Non è ammesso l'uso della funzione di inserimento di ABR.

Ecco quello che vorrei sapere non è tanto il codice ma come ragionereste voi? Vi ringrazio anticipatamente

1 Risposte

  • Re: Esame di algoritmi e strutture dati - risoluzione esercizio abr

    Ragionandoci velocemente io la risolvere in questo modo... Ti scrivo un po' di pseudocodice "da affinare"....

    funzione inserisci_elem_array_in_tree(Tree T, Array A, index start){
    esegui una serie di controlli di terminazione per le chiamate ricorsive
    if(start >= A.length) esci in quanto abbiamo scansionato tutti gli elementi dell'array e sono finiti

    if(a[start] == T.elem.value) chiama inserisci_elem_array_in_tree(T,A,start+1) in quanto l'elemento dell'albero e' uguale a quello nell'array e la traccia non prevedeva doppioni

    else if(a[start)>T.elem.value && T.elem.right == NULL) se il nodo non ha foglie a destra esegui l'inserimento a destra (nuovo nodo figlio) del valore e chiama inserisci_elem_array_in_tree(T.right,A,start+1) (I successivi inserimenti dovrebbero avvenire tutti a cascata essendo l'array ordinato)

    else if(a[start)<T.elem.value && T.elem.left == NULL) se il nodo non ha foglie a sinistra esegui l'inserimento a sinistra (nuovo nodo figlio) del valore e chiama inserisci_elem_array_in_tree(T.left,A,start+1) (I successivi inserimenti dovrebbero avvenire tutti a cascata essendo l'array ordinato)

    else if(a[start)>T.elem.value && a[start]<T.elem.right.value) esegui l'inserimento a destra (nuovo nodo figlio) del valore e chiama inserisci_elem_array_in_tree(T.right,A,start+1)

    else if(a[start)<T.elem.value && a[start]>T.elem.left.value) esegui l'inserimento a sinistra (nuovo nodo figlio) del valore e chiama inserisci_elem_array_in_tree(T.left,A,start+1)

    else if(a[start)>T.elem.value && a[start]>T.elem.right.value) non possiamo ancora inserire l'elemento e riesegui una chiamata ricorsiva utilizzando come radice il nodo destro inserisci_elem_array_in_tree(T.right,A,start) (in questo caso quindi l'indice dell'array non avanza)

    else if(a[start)<T.elem.value && a[start]<T.elem.left.value) non possiamo ancora inserire l'elemento e riesegui una chiamata ricorsiva utilizzando come radice il nodo sinistro inserisci_elem_array_in_tree(T.left,A,start) (in questo caso quindi l'indice dell'array non avanza)

    }


    Il tutto va perfezionato e migliorato anche a livello di pseudocodice ma io cosi' lo affronterei in linea generale....
Devi accedere o registrarti per scrivere nel forum
1 risposte