creazione alberi BST

[maninblack]

ciao..ho 1 problema. Devo creare 1 albero BST ke contenga delle stringhe(tipo dizionario), solo ke nn riesco capire alcuni passi principali x l'inizializzazione e l'inserimento nell'albero. Per esempio,dato ke devo cercare stringhe nell'albero come inizializzo la testa dell'albero stesso?Con che valore? Datemi una mano anke con del codice chiaro!!! )) Grazie

[unomichisiada]

Originariamente inviato da maninblack
ciao..ho 1 problema. Devo creare 1 albero BST ke contenga delle stringhe(tipo dizionario), solo ke nn riesco capire alcuni passi principali x l'inizializzazione e l'inserimento nell'albero. Per esempio,dato ke devo cercare stringhe nell'albero come inizializzo la testa dell'albero stesso?Con che valore? Datemi una mano anke con del codice chiaro!!! )) Grazie

Se BST sta per Binary Search Tree (Albero Binario di Ricerca),un albero vuoto è caratterizzato da un puntatore a NULL come radice dell'albero

[maninblack]

t ringrazio. Allora io inizializzo l'albero con questa funzione:

parola *BSTinit()
{
z=(parola *)malloc(sizeof(parola));
z->left=z;
z->right=z;
strcpy(z->word,"NULL");
head=(parola *)malloc(sizeof(parola));
head->left=z;
head->right=z;
return head;

}//end BSTinit

giusto cosi allora?o devo mettere a NULL anke il puntatore del campo dato della testa cioe' "head"?


se e' corretto poi inserisco le stringhe leggendole dal file una alla volta e creando il proprio nodo(perke' carico una specie di dizionario all'inizio del programma)
con questa inserisco le stringhe e faccio le rotazioni..giusto?


parola *BSTinsert(parola *head ,char *val)
{
if(head==z)
{
parola *p=(parola *)malloc(sizeof(parola));
strcpy(p->word,val);
p->left=z;
p->right=z;
return p;
}
if(strcmp(head->word,val)<0)
{
head->left = BSTinsert(head->left,val);
head = rotR(head);
}
else
{
head->right = BSTinsert(head->right,val);
head = rotL(head);
}
return head;

}// end BSTinsert

[infinitejustice]

se torni indietro di un paio di pagine del forum trovi un altro thread sugli alberi binari di ricerca con codice completo e funzionante.

Semplicemente metti come valore di ogni node un char * (invece dell'int) e sfrutta la libreria string.h per effettuare le operazioni necessarie.


p.s. le rotazioni (se nn ricordo male da algoritmi e struct di dati) nn servono per costruire l'albero, ma per bilanciarlo.

[maninblack]

si ok..ma il mio grande dubbio e' di cosa mettere nel campo testa cioe' in "head->word" qui sotto nell'inizializzazione del mio albero!!! Al primo passaggio x esempio se mi arriva la parola "abaco" con ke cosa la confronto x sistemarla nel mio albero vuoto????

funzione inizializzazione:
parola *BSTinit()
{
z=(parola *)malloc(sizeof(parola));
z->left=z;
z->right=z;
z->word= e anke nel nodo fittizio cosa metto?
strcpy(z->word,"NULL");
head=(parola *)malloc(sizeof(parola));
head->left=z;
head->right=z;
head->word= ???? e' qui il prob,cosa metto??
return head;
}//end BSTinit

[infinitejustice]

Originariamente inviato da maninblack
Al primo passaggio x esempio se mi arriva la parola "abaco" con ke cosa la confronto x sistemarla nel mio albero vuoto????

Indipendentemente da chi arriva al primo passaggio... finisce alla radice. Poi ogni volta che arriva una parola successiva, la funzione apposita cerca la sua posizione corretta nell'albero in modo tale da garantirti log N.

La funzione nn a caso verifica innanzitutto se la testa è NULL... se lo è nn ci pensa su e inserisce li il primo elemento che arriva.

Se poi l'albero risulta un tantino sbilanciato puoi preoccuparti di ribilanciarlo con le rotazioni.




p.s. nn pensare all'albero vuoto come ad una struttura dati gia esistente in memoria con una radice e tutti i suoi figli pronti ad ospitare dei dati...

[MMarzia]

linguaggio anche nel titolo!

[maninblack]

Ok ma ancora ho un dubbione!!! son un po' tarato di mente scusa!!
Devo riusce a farmi capire..allora il prob e' ke inizialmente ho due strutture cioe la testa"head" e la coda "z".La testa e' collegata con i campi left e right al nodo "z". Entrambe nel campo "valore" nn ho inserito niente pero' e questo il mio dubbio.Cioe' quando arriva la prima parola faccio 1 confronto tra essa(esempio "abaco") e il campo valore di testa.Ma il campo valore di testa e' vuoto!!! quindi evo inizializzarlo in un altra maniera? Cosa devo fare? il tempo stringe!!!!! E poi inizialmente il nodo "testa" collegato come detto a "z" ha un valore NULL ???? help me!!!!!!!!

[infinitejustice]

Il fattto che chiami z nodo coda mi fa pensare che confondi le liste con gli alberi... a meno che con z nn intendi un nodo terminale.

Nell'altra discussione con tutto il codice, se controlli, la funzione che aggiunge i vari nodi come prima cosa verifica che la radice è NULL e nel caso ci mette il nodo che è arrivato. Se nn lo è allora cerca il posto corretto dove metterlo.

inizialmente la testa, che è un puntatore, è NULL.

[maninblack]

si "Z" e' il nodo terminale..il fatto e' ke lo inizializzo a Null la testa , ma nn capisco se inizializzandola con la funzione BSTinit(ke appunto crea l'albero vuoto), ke ho gia' postato, al primo passagio e' NULL oppure no!!! Se nn lo fosse creero' un' altro nodo dove inserire la parola ke diventera' la nuova testa e la mia vecchia "testa" diventera' suo figlio..aiuto!!!