C++ alberi binari con vettore.

[pietrol83]

ciao a tutti, sto creando la struttura dati albero binario con vettore (non con cursori). dovrei implementare i seguenti metodi:

alberobin insfigliosx(alberobin, alberobin, nodo);
alberobin insfigliodx(alberobin, alberobin, nodo);

dove il primo alberobin nella lista degli argomenti è this e il secondo è un altro alberobinario.
l'albero binario risultante sarebbe quello ottenito dall'albero passato con this aggiungendo l'albero passato come secondo argomento come figlio sinistro (destro) del nodo passato come argomento (appartenente all'albero this).

come posso fare?? ribadisco che l'albero è implementato con un vettore.
vi prego aiutatemi.

[ramy89]

Non serve passare il riferimento all' oggetto come argomento.
Ma da quello che hai detto non ti si può dire come fare.Primo perchè la domanda è troppo generica, secondo perchè non hai specificato come hai implementato l' albero.
Se tra i parametri ci sono dati di tipo alberobin e nodo, devi far vedere cosa sono alberobin e nodo.

[pietrol83]

allora l'albero binario è implementato con un vettore, cioè i nodi dell'albero binario vanno inseriti in un vettore in questo modo:

se il nodo v è la radice allora v va in posizione 1 (nel vettore sarà posizione 0),
se il nodo v è figlio sinistro del nodo u allora la posizione di v è p(v) = 2*p(u),
se il nodo v è figlio destro del nodo u allora la posizione di v è p(v) = 2*p(u) + 1;

per quanto riguarda i metodi insfigliosx (insfigliodx), questi prendono come argomento due alberi binari (con vettore) e restituiscono un albero binario (con vettore), dove il primo albero binario che prende il metodo è proprio l'oggetto istanziato (this) e il secondo è un altro albero binario da agganciare al primo prendendo la radice (del secondo albero) e inserendola come figlio sinistro del nodo passato come argomento (dell'albero this). l'albero risulatante dovrebbe essere assegnato ad un terzo sottoalbero, ma io avrei fatto il metodo nn come funzione ma come procedura (non restituendo nessun valore e agganciando l'albero passato come argomento all'albero this). la difficoltà che trovo io è: come faccio a determinare le nuove posizioni nel vettore dell'albero this che devono essere occupate dai nodi dell'labero passato come argomento??? so anche che deve essere ridimensionata la dimensione del vettore ell'albero this in quanto se un albero binario ha n nodi allora la dimensione del vettore deve essere 2^n - 1.

[ramy89]

se il nodo v è figlio sinistro del nodo u allora la posizione di v è p(v) = 2*p(u),
se il nodo v è figlio destro del nodo u allora la posizione di v è p(v) = 2*p(u) + 1;

E' sbagliato, se v è il figlio sinistro del nodo in posizione i, v sta in posizione 2*i+1.
Se è figlio destro sta in posizione 2*1+2.

Originariamente inviato da pietrol83
[...]ma io avrei fatto il metodo nn come funzione ma come procedura (non restituendo nessun valore e agganciando l'albero passato come argomento all'albero this).

Su questo sono d' accordo, non serve il tipo di ritorno.Lo puoi togliere.

[...] la difficoltà che trovo io è: come faccio a determinare le nuove posizioni nel vettore dell'albero this che devono essere occupate dai nodi dell' albero passato come argomento???

Prova a dividere il problema in sotto-problemi:
-Fai un metodo per inserire un singolo nodo come figlio destro o sinistro di un nodo;
-Se devi inserire un nodo come figlio sinistro del nodo in posizione i, supponendo che il sotto-albero da aggiungere ha m nodi, userai m volte il metodo appena creato, ma con parametri diversi.

Di certo la tua implementazione non è la migliore se devi fare di continuo inserimenti o cancellazioni.
Fai prima ad avere due campi interni che sono due puntatori a nodo, che sono i due figli (o NULL se il figlio è assente).
Ma ci capiamo molto meglio se fai vedere il codice.

[pietrol83]

va bhe alla fine ho implementato tutto come procedure l'ho fatto un modo che inserisce solo un nodo al posto di un albero intero. non posso fare come hai detto tu perchè la prof con cui dovrò fare l'esame ti massacra se vede che faccio le cose diversamente da come le vuole lei.
in pratica se l'albero è fatto con vettore non posso usare i puntatori (anche perchè devo implementare anche l'albero binario con puntatori e con cursori). cmq ho risolto. grazie 1000