ELEMENTI COMUNI TRA DUE ALBERI BINARI DI RICERCA

di il
3 risposte

ELEMENTI COMUNI TRA DUE ALBERI BINARI DI RICERCA

Salve a tutti.
Avrei bisogno di un aiuto con un esercizio.
sapete dirmi se la funzione che ho definito va bene per l'esercizio seguente?!
testo: dati due alberi binari di ricerca a numeri interi, scrivere una funzione che genera un nuovo albero binario di ricerca che contenga
gli elementi a comune tra i due alberi.

struct btree *elemComuni(btree *A, btree*B) {
struct btree*C;
init(&C);
int tmp=0;
if(A!=NULL){
A=A-> left_ptr;
tmp= A->value;
if(B!=NULL){
B=B->left_ptr;
if((tmp= B->value)){
ord_insert(&C,tmp);
}
B=B->right_ptr;
}
A=A-> right_ptr;
}
return C;
}

questo è ciò che ho pensato io fatemi sapere.
sotto vi posto il programma intero.
#include <stdio.h>
#include <stdlib.h>
typedef struct btree {
int value;
struct btree *left_ptr;
struct btree *right_ptr;
} btree;
void init(btree ** ptrptr);

void ord_insert(btree ** ptrptr, int value);


struct btree *elemComuni(btree *A, btree*B);
btree* newBtree(void);
btree* addLeaf(btree* ptr, int v);
void printBtree(btree* ptr);

int main() {

btree *J=NULL;
ord_insert(&J, 1);
ord_insert(&J, 13);
ord_insert(&J, 22);
ord_insert(&J, 19);


btree *K=NULL;
ord_insert(&K, 2);
ord_insert(&K, 13);
ord_insert(&K, 21);
ord_insert(&K, 19);

// printBtree(*(&J));
// elemComuni( &elem2, &elem1 );
btree *R=elemComuni(*(&J),*(&K));
printBtree(*(&R));
}

btree* addLeaf(btree* ptr, int v) {
if (ptr == NULL) {
ptr = newBtree();
ptr->value = v;
ptr->left_ptr = NULL;
ptr->right_ptr = NULL;
} else {
if (v < ptr->value) {
ptr->left_ptr = addLeaf(ptr->left_ptr, v);
} else if (v > ptr->value) {
ptr->right_ptr = addLeaf(ptr->right_ptr, v);
} else {
printf("Dato duplicato (%d)\n", ptr->value);
}
}
return (ptr);
}

void printBtree(btree* ptr) {
if (ptr != NULL) {
printBtree(ptr->left_ptr);
printf("%3d", ptr->value);
printBtree(ptr->right_ptr);
}
}

btree* newBtree(void) {
btree* p;
p = (btree*)malloc(sizeof(btree));
if (p == NULL) {
printf("Errore allocazione!\n");
system("pause");
exit(1);
}
return (p);
}
void ord_insert(struct btree ** ptrptr, int value) {
if (*ptrptr != NULL) { // NON è una foglia
if (value <= (*ptrptr)->value) //si discende l’albero
ord_insert(&((*ptrptr)->left_ptr), value);
else
ord_insert(&((*ptrptr)->right_ptr), value);
}
else { // foglia raggiunta… aggiungi elemento
(*ptrptr) = (struct btree *)malloc(sizeof(struct btree));
(*ptrptr)->value = value; // metti valore
(*ptrptr)->left_ptr = NULL; // inizializza figli…
(*ptrptr)->right_ptr = NULL; // a NULL.
}

}
struct btree *elemComuni(btree *A, btree*B) {
struct btree*C;
init(&C);
int tmp=0;
if(A!=NULL){
A=A-> left_ptr;
tmp= A->value;
if(B!=NULL){
B=B->left_ptr;
if((tmp= B->value)){
ord_insert(&C,tmp);
}
B=B->right_ptr;
}
A=A-> right_ptr;
}
return C;
}


void init(struct btree ** ptrptr) {
*ptrptr = NULL;

}

3 Risposte

  • Re: ELEMENTI COMUNI TRA DUE ALBERI BINARI DI RICERCA

    1) leggi il regolamento del forum sulla formattazione del codice
    2) il tuo codice funziona o non funziona? l'hai testato? l'albero con gli elementi in comune è quello corretto? Se non lo è, qual è il punto del codice che non ti torna?
  • Re: ELEMENTI COMUNI TRA DUE ALBERI BINARI DI RICERCA

    Io provo a eseguire il programma ma a livello (della funzione) di " A=A-> left_ptr;"
    mi da il seguente errore: Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)
    non riesco a capire ccosa c'è che non va.
  • Re: ELEMENTI COMUNI TRA DUE ALBERI BINARI DI RICERCA

    Perché è una chiamata senza senso. Studia un po' meglio i puntatori prima. Usa una variabile temporanea puntatore e cerca di capire come navigare tra i diversi nodi di un albero già creato. Quando hai capito, riprova con l'esercizio
Devi accedere o registrarti per scrivere nel forum
3 risposte