Alberi n-ari

[petronella]

Salve a tutti,
non riesco ad implementare l'operatore insprimosottoalbero di una struttura dati albero realizzata tramite liste di figli. Qualcuno può darmi una mano?
Il linguaggio usato è il C.
Grazie a tutti,
Domenico.

[cionci]

Che intendi per insPrimoSottoalbero ? Spiegati meglio...comè la struttura dati ? Sono liste concatenate di nodi o liste di alberi ?

[petronella]

in un array sono memorizzati tutti i nodi dell'albero ed ogni elemento dell'array è un puntatore ad una lista i cui elementi sono i figli di tale nodo .
Quindi ho un array di liste. Le informaioni relative ad ogni singolo nodo (etichetta) sono memorizzate in un altro array in corrispondenza dello stesso indice. Faccio un esempio dove l'etichetta del nodo è di tipo tipoelem (char, int, ecc ):

struct tipocella
{
indice elemento;
struct tipocella * successivo;
};
typedef struct tipocella cella;
typedef cella * lista ; // ho definito la lista

struct tipoalbero
{
lista testa[max_num_nodi]; // array di liste
tipoelem info[max_num_nodi]; // info associate ad ogni nodo
};
typedef tipoalbero albero;

la funzione :

void insprimosottoalbero(albero, albero *, nodo);

permette di fondere due alberi ed in particolare di inserire l'albero B (secondo parametro) come primo figlio del nodo (terzo parametro) dell'albero A (primo parametro).

Se vuoi ti allego il sorgente .

Ciao e grazie,
Domenico.

[/\/\@®¢Ø]

Spero di aver ben capito la struttura del tuo albero
allora la funzione che cerchi potrebbe essere la seguente

Per comodita suppongo che i due albero abbiano un campo in cui memorizzano il numero di nodi

void insprimosottoalbero(albero* A, albero * B, nodo)
{
// c'e' spazio ?
if ( A->size + B->size > max_num_nodi ) return;
// copiamo le liste del secondo albero nel primo
for ( int i=0 ; i< B->size ; i++ )
{
A->testa[i+A->size]=B->testa[i];
}
// gli elementi di B, che avevano indice 0 a B->size , ora hanno indice da A->size ad A->size+B->size, devo aggiornare le liste
for( int = 0 ;i< B->size ; i++ )
{
lista* l = A->testa[i+A->size];
while( l != NULL )
{
l->elemento+= A->size;
l=l->next;
}
}
// ora non ci resta che mettere la radice di B ( che ora ha indice A->size )
// come figlio del nodo indicato
lista* n = new lista;
n->elemento= A->size;
n->next=A->testa[nodo];
A->testa[nodo]=n;
// aggiorniamo la dimensione
A->size += B->size;
}



NB- Come avrai notato questo è C++, quindi dovrai fare alcune modifiche (minime)

[/\/\@®¢Ø]

Dimenticavo....
per pigrizia non mi sono preoccupato di copiare le liste.
Quindi l'albero inserito non e' piu' utilizzabile da se'.
Se vuoi poterlo utilizzare ancora devi crearti delle nuove liste invece che copiare e modificare le vecchie.
L'idea di base comunque rimane quella ( copia i nodi, aggiorna gli indici, collega la radice al nodo desiderato ), e non dovrebbe esserti difficile effettuare i dovuti cambiamenti.
ciao
marco

[/\/\@®¢Ø]

Post post scriptum
non ho provato a compilare il codice,
puo' darsi ( anzi, probabile :D ) che contenga errori.
Mi interessava piu' che altro spiegarti il procedimento.

[petronella]

Ok ci provo.
Grazie,
Domenico.