Confronto Fra Due Alberi Binari In C

[miki miki]

ho provato anche a scrivere un programma che confronta due alberi e restituisce 1 se sono uguali...vorrei sapere un vostro parere siccome sono alle prime armi. grazie

int confronta (tree T1;T2)  {   
                                        if ((T1==NULL & T2!=NULL) || (T2==NULL & T1!=NULL) || (T1->dato!=T2->dato))
return 0;
    confronta(T1->right, T2->right);
    confronta (T1->left, T2->left);

    return1;}

[Ippo343]

Questa funzione controlla i dati dei due nodi root, e se sono uguali ritorna 1, altrimenti 0, ignorando il resto dell'albero.

Due alberi sono uguali se i dati del nodo radice sono uguali E il sottoalbero sinistro è uguale E il sotto albero destro è uguale. In questo caso ritorni 1.

[Alex'87]

L'algoritmo non l'ho controllato ma quel che vedo è sintatticamente sbagliato:

1. int confronta(tree T1, tree T2) e non int confronta (tree T1;T2)

edit
1.1 non so come hai definito tree ma penso che debba essere un puntatore visot che poi usi la freccia...
/edit

2. L'and logico è && e non &
3. E ovviamente tra return e 1 ci vuole uno spazio

Hai provato a compilarlo? Si direbbe di no...

[miki miki]

ok....gli errori di sintassi sono dovuti alla fretta....

il mio problema è capire se il programma ha senso e potrebbe funzionare...e se c'è un errore, cosa piu' che probabile capire dove e perchè......faccio veramente molta fatica con la ricorsione....e se c'è qualcuno con piu' esperienza di me gli son veramente grato

[miki miki]

si', ho tralasciato le dichiarazioni di albero e dei puntatori...

[miki miki]

ho provato a fare una modifica:

int confronta (tree T1;tree T2) 
{ 
   if ((T1==NULL & T2!=NULL) || (T2==NULL & T1!=NULL) || (T1->dato!=T2->dato)) 
   return 0;
   else return confronta(T1->right, T2->right) + return confronta (T1->left, T2->left); 
   return1
}

[YuYevon]

A parte il fatto che non hai tenuto conto di tutte le correzioni che ti sono state segnalate

int confronta (tree T1, tree T2) 
{ 
   if ((T1==NULL && T2!=NULL) || (T2==NULL && T1!=NULL) || (T1->dato!=T2->dato)) 
   return 0;
   else return confronta(T1->right, T2->right) + return confronta (T1->left, T2->left); 
   return 1; 
}

in un qualsiasi algoritmo ricorsivo devi stabilire un caso base; nel caso in questione, visto che tu ricorri lungo l'albero fino a quando i puntatori non sono NULL, il caso base potrebbe proprio essere "se sia T1 che T2 sono NULL, allora restituisci 1", cioè "gli alberi sono uguali".

Io lo farei così:

int same_tree(Node *first, Node *second)
{
        /* caso base */
	if (first == NULL && second == NULL) {
		return 1;
	}

	if ((first == NULL && second != NULL) ||
	    (first != NULL && second == NULL) ||
	    (first -> data != second -> data) {
		return 0;
	}

	/* se si arriva qui, entrambi i puntatori sono != NULL e i dati sono uguali */
	return same_tree(first -> l_child, second -> l_child) && same_tree(first -> r_child, second -> r_child);

        /* il valore da restituire è quindi la AND logica tra i valori della funzione sui sottoalberi di sinistra e di destra */
}

con

typedef struct node {
	int data;
	struct node * l_child;
	struct node * r_child;
} Node;

Non ho avuto modo di testarla molto, ma dovrebbe funzionare.

[miki miki]

grazie per il suggerimento e l'aiuto!!!
ora ho capito e sembra proprio che il tuo codice sia valido

e se invece volessi confrontare due liste, sempre in modo ricorsivo??

int confronta(lista L1, lista L2) 
                                         { 
                                          if (L1==NULL && L2== NULL ) 
                                          return 1;
                                          if ( (L1->dato!=L2->dato) || 
                                               (L1==NULL && L2!=NULL) || 
                                               (L2==NULL && L1!=NULL) ) 
                                           return 0; 
                                           return confronta (L1->next, L2->next) 
                                          }

dovrebbe essere giusta...?

[YuYevon]

Sì è corretta, il principio è lo stesso. Tieni conto solo di un fatto che non riguarda l'algoritmo ma un aspetto "tecnico": questa condizione

                                          if ( (L1->dato!=L2->dato) || 
                                               (L1==NULL && L2!=NULL) || 
                                               (L2==NULL && L1!=NULL) )

può generare errori di accesso alla memoria per dereferenziazione di puntatori NULL. Infatti, la prima condizione della funzione, cioè

if (L1==NULL && L2== NULL )

esclude l'eventualità che L1 e L2 siano *entrambi* NULL, ma non è detto che almeno uno di loro non lo sia. Per questo, quando dopo vai ad accedere al campo "dato" di L1 e L2 nella prima condizione dell'if, se uno di questi due fosse effettivamente NULL il programma crasherebbe. Devi quindi posticipare la prima condizione del secondo if

                                          if ( (L1==NULL && L2!=NULL) || 
                                               (L2==NULL && L1!=NULL) ||
                                               (L1->dato!=L2->dato))

così se le prime due condizioni risultano false, avrai la garanzia che sia L1 che L2 siano diversi da NULL, quindi poi puoi dereferenziarli. Se invece una delle prime due condizioni risultasse vera, la terza non verrebbe proprio valutata perché sono in OR tra di loro, quindi in ogni caso non hai il problema del puntatore NULL.

[miki miki]

grazie mille per la "sottile" ma importante correzione....

volevo"approfittare" della tua competenza e gentilezza per chiederti un parere a riguardo del seguente programma:
mi si chiede di codificare una funzione che prenda in ingresso una lista e dica quanti picchi sono presenti. Picchi: il valore del dato precedente e seguente a quello corrente è minore della metà del dato corrente.il primo e l'ultimo nodo non sono picchi.

int picchi ( lista L) { 
                          int x=0; /*contatore dei picchi*/ 
                          Lista prec; /*dichiaro tre variabili di tipo lista che mi serviranno ad indicare i 3 nodi da considerare: quello prima e quello dopo a quello che valuto*/ 
                          Lista curr; 
                          Lista succ; 
                          if (L==NULL || L->next==NULL || L->next->next==NULL) /*controllo che ci siano almeno 3 nodi */ 
                        return 0; 
                        prec=L; 
                        curr=prec->next; /*vado avanti con la scansione*/ 
                        succ=curr->next; 
                        while( succ!=NULL) /*finchè arrivo in fondo alla lista*/ 
                                 {
                                  if(prec->dato < curr->dato/2 && curr->dato /2 > succ->dato) /*controllo la condizione*/ 
                                  x++ ;/*incremento il contatore*/ 
                                  succ=succ->next; 
                                  curr=curr->next;
                                  prec=prec->next;
                                } 
                    return x; 
                          }