PDA

Visualizza la versione completa : [C] Dubbio alberi binari


meme1006
12-09-2015, 17:02
Salve,mi scuso se la domanda risulterà molto banale ma non riesco assolutamente a risolvere il problema...
Allora io devo creare una funzione che ritorni 1 se i due alberi binari(assegnati alla funzione nel main) sono uguali.

Io ho proceduto così:

int uguali(tree t1, tree t2) {
tree l = t1, s = t2;
/* caso base: entrambi gli alberi vuoti */
if ((emptyt(l)) && (emptyt(s))) {
printf("\n\nEntrambi vuoti\n");
return 0;
}
/* caso base: un albero vuoto, un albero no */
if ((emptyt(l)) || (emptyt(s))) {
printf("\n Uno dei due alberi e' vuoto");
return 0;
}
/* i due nodi in esame devono contenere lo
stesso valore e i due sottoalberi sx e dx
devono essere uguali (ricorsivamente) */
return (l->value == s->value && uguali(l->left, s->left) && uguali(l->right, s->right));
}

E questo è il mio main:

int main(){
tree t = emptytree(), r = emptytree();
element el;
FILE *f;
int ugualiInt = 0;
f = fopen("valori.txt", "rt"); if (f == NULL) {
printf("Errore Apertura file");
exit(1);
}
while (fscanf(f, "%d", &el)>0) {
t = insertBinOrd(el, t);
//Creo i due alberi esattamente identici(ho controllato li riempisse correttamente)
r = insertBinOrd(el, r);
}

ugualiInt = uguali(t, r); printf("\n\n\tSe esce 1 va bene: %d", ugualiInt);
getchar();
}



Il problema è che mi continua a restituire 0 poiché non riesce a leggere i due alberi,o meglio li vede come vuoti. Sto sbagliando ad assegnare gli alberi alla funzione? Gli alberi sono stati creati e stampati correttamente,siccome ho provato con una funzione che li stampasse uno dietro l'altro e sono assolutamente identici.
Spero rispondiate,e mi scuso se ho sbagliato sezione o commesso qualche infrazione nel forum
Grazie.

Scara95
12-09-2015, 20:29
Due vuoti sono uguali

meme1006
12-09-2015, 20:43
Due vuoti sono uguali

Sì ma in teoria non dovrebbero essere vuoti! Cioè siccome ho creato due alberi non vuoti,come faccio a passarli alla funzione in maniera che li legga bene e svolga la funzione?

oregon
12-09-2015, 21:09
Sì ma in teoria non dovrebbero essere vuoti! Cioè siccome ho creato due alberi non vuoti,come faccio a passarli alla funzione in maniera che li legga bene e svolga la funzione?


Posta tutto il codice in modo che possa essere compilato senza errori. Quello che hai mostrato non è completo.

Scara95
12-09-2015, 21:09
Quella funzione ritornerà sempre 0.
Analizzando ricorsivamente arriverai sempre a dei vuoti, in quel caso viene ritornato 0. 0 && qualsiasi cosa fa 0.

meme1006
12-09-2015, 21:33
Quella funzione ritornerà sempre 0.
Analizzando ricorsivamente arriverai sempre a dei vuoti, in quel caso viene ritornato 0. 0 && qualsiasi cosa fa 0.


Ok ho capito cosa vuoi dire,ti ringrazio! Come potrei fare per sistemare? Non credo mi basti solo togliere l'if iniziale..

meme1006
12-09-2015, 21:34
Posta tutto il codice in modo che possa essere compilato senza errori. Quello che hai mostrato non è completo.

Appena posso posto tutto il codice! Grazie

Scara95
12-09-2015, 21:41
La risposta non cambia

Due vuoti sono uguali

meme1006
13-09-2015, 12:39
Questo è il codice completo:



#include <stdio.h>
#include <stdlib.h>


typedef int element;
typedef struct tree_element{
element value;
struct tree_element *left, *right;
}node;
typedef node *tree;
typedef int boolean;

boolean emptyt(tree t){
return (t == NULL);
}

tree emptytree(){
return NULL;
}

element root(tree t){
if (emptyt(t))
abort();
else
return t->value;
}



tree left(tree t){
if (emptyt(t))
return NULL;
else
return t->left;
}


tree right(tree t){
if (emptyt(t))
return NULL;
else
return t->right;
}

tree consTree(element e, tree l, tree r){
tree t;
t = (node *)malloc(sizeof(node));
t->value = e;
t->left = l;
t->right = r;
return t;
}

tree insertBinOrd(element e, tree t){
tree l = t;
if (emptyt(t))
return consTree(e, emptytree(), emptytree());
while (!emptyt(t)) {
if (e <= root(t)){
if (emptyt(left(t))){
t->left = consTree(e, emptytree(), emptytree());
t = left(t);
}
t = left(t);
}
else {
if (emptyt(right(t))){
t->right = consTree(e, emptytree(), emptytree());
t = right(t);
}
t = right(t);
}
}
return l;
}

int uguali(tree t1, tree t2) {
tree l = t1, s = t2;
/* caso base: entrambi gli alberi vuoti */
if ((emptyt(l)) && (emptyt(s))) {
printf("\n\nEntrambi vuoti\n");
return 0;
}
/* caso base: un albero vuoto, un albero no */
if ((emptyt(l)) || (emptyt(s))) {
printf("\n Uno dei due alberi e' vuoto");
return 0;
}
/* i due nodi in esame devono contenere lo
stesso valore e i due sottoalberi sx e dx
devono essere uguali (ricorsivamente) */
return (l->value == s->value && uguali(l->left, s->left) && uguali(l->right, s->right));
}





int main(){
tree t = emptytree(), r = emptytree();
element el;
FILE *f;
int ugualiInt = 0;
f = fopen("valori.txt", "rt"); if (f == NULL) {
printf("Errore Apertura file");
exit(1);
}
while (fscanf(f, "%d", &el)>0) {
t = insertBinOrd(el, t);
//Creo i due alberi esattamente identici(ho controllato li riempisse correttamente)
r = insertBinOrd(el, r);
}

ugualiInt = uguali(t, r); printf("\n\n\tSe esce 1 va bene: %d", ugualiInt);
getchar();
}

meme1006
13-09-2015, 12:46
Quindi come creeresti tu una funzione per vedere se due alberi sono uguali? Perché io non riesco a saltarci fuori..

Loading