Problema con esercizio su alberi

di Anonimizzato13311 il
9 risposte
/
Anonimizzato13311
Utente anonimizzato
Ciao a tutti, sono nuovo del forum. E' da un pò di tempo che sto perdendo la testa su un esercizio uscito all'ultimo appello di Algoritmi e strutture dati. Spero che qualcuno possa aiutarmi, il testo dell'esercizio è questo:
Sia dato un albero binario T, scrivere un algoritmo ricorsivo efficiente che elimini da T tutti i nodi che contengano una chiave con valore pari e, contemporaneamente, costruisca un albero binario di ricerca T' contenente tutti i nodi eliminati da T. L'algoritmo richiesto deve restituire l'albero T' e non può avere T' tra i suoi parametri d'ingresso.
Grazie anticipate a chi mi dara una mano.

9 Risposte

  • Super Famoso
    Iscritto da
    nov, 2011
    Messaggi
    21917
    Aiutare come? Non si può fare tutto l'esercizio ...
  • /
    Anonimizzato13311
    Utente anonimizzato
    Il mio problema sta in come costruire l'albero dei nodi cancellati, che a detta del prof. deve essere fatto mentre si risale dalla ricorsione, ed io non ho la più pallida idea di come bisogna fare.
  • /
    Anonimizzato13311
    Utente anonimizzato
    A me non serve avere il listato che risolve l'esercizio, ma solo una spiegazione su come potrei risolvere la cosa.
  • /
    Anonimizzato13311
    Utente anonimizzato
    Secondo voi questa soluzione può andare bene?
    nodo* Algo(T){
    nodo*app;
    if T!=Nill
    If T.sx!=Nill
    app=Algo(T.sx);
    If T.dx!=Nill
    app=Algo(T.dx);
    If T.key%2==0
    nuovo=Alloca nuovo nodo;
    nuovo.key=T.key;
    return inserisciabr(app,nuovo);
    return app;
    }
  • /
    Anonimizzato10779
    Utente anonimizzato
    Non credo vada bene (comunque usa i tag [ code]).

    Se ho capito quello che hai scritto, tu elimini i nodi pari partendo dalle foglie dell'albero (perché richiami ricorsivamente la funzione sui rami sx e dx e solo dopo fai la verifica su pari o dispari), quindi poi ti risulta ovviamente difficile costruire l'albero T'.

    Secondo me dovresti intanto iniziare a invertire le parti e togliere il return prima di inserisciabr(), in questo modo: 
    
nodo* Algo(T){
    nodo*app;
    If T.key%2==0
        nuovo=Alloca nuovo nodo;
        nuovo.key=T.key;
        inserisciabr(app,nuovo);
    if T!=Nill
        If T.sx!=Nill
            app=Algo(T.sx);
        If T.dx!=Nill
            app=Algo(T.dx);
    return app;
}
    In questo modo prima controlla se il nodo corrente è pari, e nel caso lo inserisce nell'altro albero, dopodiché procede sul ramo sx e poi sul dx.
    Ovviamente neanche questa è la soluzione corretta, perché le specifiche ti chiedono anche di eliminare i nodi dal primo albero, ma quello prova a farlo tu.

    ciao
  • /
    Anonimizzato13311
    Utente anonimizzato
    Il professore ci disse che quando bisogna cancellare dall'albero c'è bisogno di esplorare l'albero in post-order, per questo ho atto così.
  • /
    Anonimizzato10779
    Utente anonimizzato
    Per CANCELLARE dall'albero, non per inserire nell'altro.

    Abbiamo ragione sia io che il tuo prof, nel senso che quando devi trovare gli elementi da mettere nel secondo albero conviene una visita pre-order, in modo che trovi già gli elementi nell'ordine giusto, mentre quando vuoi cancellare gli elementi dall'albero di partenza conviene la post-order perché risulta più facile reindirizzare i puntatori dopo la cancellazione di un nodo.

    Quindi in pratica, partendo dal mio codice, dovresti inserire appena prima della fine la funzione che cancella il nodo.

    ciao
  • /
    Anonimizzato13311
    Utente anonimizzato
    Ah ok ho capito, grazie mille.
  • /
    Anonimizzato10779
    Utente anonimizzato
    Di nulla.
Devi accedere o registrarti per scrivere nel forum
9 risposte