[C] albero 4 figli verificare se è un ABR considerando nodi a due a due

[mame83]

Ciao , ho il seguente problema in C: dato un albero definito in questo modo:
typedef struct nodo
{
int info;
struct nodo *left1;
struct nodo *left2;
struct nodo *right1;
struct nodo *right2;
} nod;

devo verificare se l abero è un ABR rispetto alla somma dei nodi left1 e left2 e alla somma dei nodi right1 e right2.

codice:

void visita(nod *radice, int *min, int *risp , int *somma)
{
if (radice != NULL)
{
visita(radice->left1,min,risp,somma);
*somma= *somma+radice->info;
visita(radice->left2,min,risp,somma);
if (radice->info != *somma)
*somma=radice->info+ *somma;
if (*min < *somma)
{
*min = *somma;
printf("\n aggiorniamo min %d \n",*min);

}
else
{
*risp = 1;
printf("aggiorniamo risp %d \n",*risp);
}
somma=0;
visita(radice->right1,min,risp,somma);
visita(radice->right2,min,risp,somma);
}
}

int isBst(nod *root)/*0 se abr 1 NO - FUNZIONE PRINCIPALE- */
{
int min = INT_MIN;
int ok = 0;
int somma = 0;
visita(root,&min,&ok,&somma);
printf("valore di ok e' %d \n",ok);
if (ok == 0)
return 0;
else
return 1;
}



La funzione prinicipale è isBst, all interno richiamo visita inizializzando min al minimo intero, somma e ok a 0.
In output mi restituisce sempre 1 cioe che non è un abr. Ragazzi non so piu come fare :muro:
Spero che qualcuno mi aiuti, grazie in anticipo

[mame83]

Spero di aver spiegato bene qual è il problema
. HELP HELP!!!!!!!!

[demos88]

Ehm... mi sento un po' ignorante nel domandarlo... ma cos'è un ABR tree?
Intendi Albero Rosso-Nero (Red Black Tree)? Tra le varie sigle di alberi che ho studiato, l'ABR non mi dice nulla :confused:

edit: o intendi Albero Binario di Ricerca?
Comunque se il tuo albero è binario, perchè hai quattro puntatori ad altri nodi in ogni nodo (4 nodi figli?)?

[mame83]

per ABR si intende un albero binario di ricerca cioe i nodi che stanno a sinistra sono minori o uguali della radice e quelli di destra maggiore. Nel caso in questione i nodi left1+ left2 devono essere minori o uguali della radice e right1 + right2 maggiori della radice.

[Vincenzo1968]

Prova con le soluzioni di Nick Parlante(esercizi 13 e 14):

http://cslibrary.stanford.edu/110/BinaryTrees.html

Ovviamente devi adattare il codice alla struttura del tuo albero.

[mame83]

ma io con un albero binario lo so fare . Con un albero a 4 figli è piu difficile
ALBERO BINARIO faccio in questo modo:


int isBST2(nod *root, int min, int max)
{

if (root == NULL)
return 0;

if (root->info > min && root->info <= max &&
isBST2(root->sinistro, min, root->info) == 0 &&
isBST2(root->destro, root->info, max) == 0)
return 0;
else
return 1;
}

int isBst(nod *root)/*0 se abr 1 NO*/
{
if (isBST2(root,INT_MIN,INT_MAX) == 0)/*minimo intero e massimo intero gia
assegnati di default*/
{
printf("l albero e' un ABR \n");
return 0;
}
else
{
printf("l albero non e' un ABR \n");
return 1;
}


Come devo modificarlo in un albero a 4 figli???

[Vincenzo1968]

ma io con un albero binario lo so fare . Con un albero a 4 figli è piu difficile
ALBERO BINARIO faccio in questo modo:


int isBST2(nod *root, int min, int max)
{

if (root == NULL)
return 0;

if (root->info > min && root->info <= max &&
isBST2(root->sinistro, min, root->info) == 0 &&
isBST2(root->destro, root->info, max) == 0)
return 0;
else
return 1;
}

int isBst(nod *root)/*0 se abr 1 NO*/
{
if (isBST2(root,INT_MIN,INT_MAX) == 0)/*minimo intero e massimo intero gia
assegnati di default*/
{
printf("l albero e' un ABR \n");
return 0;
}
else
{
printf("l albero non e' un ABR \n");
return 1;
}


Come devo modificarlo in un albero a 4 figli???

Un albero a 4 figli non è un albero binario. Un albero binario è un albero con, al più, due figli. Il tuo è un albero m-ario(leggasi "emme ario" non "Mario") con m = 4.

Dunque la soluzione è semplice:


int isBST (nod *root)
{
return 0;
}


La funzione restituisce sempre false perché l'albero non è binario e, a maggior ragione, non può essere un albero binario(BST o ABR) di ricerca.:D

Scherzo, più tardi vedo come si può adattare il codice per il tuo caso.
;)

[mame83]

il problema è andare a considerare di volta in volta la somma dei nodi left1 e left2 e la somma dei nodi right1 e right2. PS magari fosse cosi facile return 0 :)

Cmq a parte gli scherzi spero che qualcuno mi aiuti

[mame83]

ragazzi vi prego non so piu cosa fare. qualcuno mi aiuti!!!!!!!!

[demos88]

Come ti ha risposto l'utente sopra, il tuo albero non è binario, e io oserei dire nemmeno di ricerca, in quanto non è definito un ordinamento sui nodi, ma su coppie di nodi. Un albero di ricerca con nodi che hanno fino a quattro figli, è per esempio l'albero 2-4, ma è strutturalmente molto diverso dal tuo.
Così su due piedi avrei abbozzato una cosa del genere, non uso C da tempo per cui non garantisco la sintassi :asd:

bool isOk(*nodo){
int left = 0, right = 0;
if (nodo->left1 != NULL){
left += nodo->left1->info;
if (!isOk(nodo->left1))
return false
}
if (nodo->left2 != NULL){
left += nodo->left2->info;
if (!isOk(nodo->left2))
return false
}
if (nodo->right1 != NULL){
right += nodo->right1->info;
if (!isOk(nodo->right1))
return false
}
if (nodo->right2 != NULL){
right += nodo->right2->info;
if (!isOk(nodo->right2))
return false
}
if (right < left)
return false
else
return true
}
Concettualmente dovrebbe fare i calcoli seguendo un attraversamento inorder, per ogni nodo calcola la somma dei sinistri e dei destri e se i sinistri sommano più dei destri, ritorna false che si propaga alla prima chiamata della funzione.
Prova a vedere se funziona, non dovrebbe essere molto distante dalla soluzione, penso :sperem: