[c]problema alberi binario di ricerca

[esoni]

ciao ragazzi vi spiego il mio esercizio
ho definito l albero i quali nodi contengono una chiave numerica
il mio esercizio è questo
leggo a riga un intero
finche non inserisco -1
{
mi chiedo se quell intero è gia nell albero
se non è presente lo inserisco nell albero



}


stampo albero

ecco il codice



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

struct Nodo{

int key;
struct Nodo* left;
struct Nodo* right;

};

typedef struct Nodo* Tree;

void insert(Tree *t, int k){

// crea il nodo foglia da inserire contenente la chiave
struct Nodo* e = malloc(sizeof(struct Nodo));
e->key = k;
e->left = e->right = NULL;

struct Nodo* p;
struct Nodo* x = *t;

// se l'albero è vuoto imposta e come radice dell'albero
if (x == NULL) {
*t = e;
return;
}

// altrimenti cerca la posizione della foglia nell'albero
while (x != NULL){

p = x;
if (x->key < k) x = x->right;
else x = x->left;
}

// ora p punta al padre del nuovo elemento da inserire in t
// quindi si procede a linkare p ed e

if (p->key < k) p->right = e;
else p->left = e;

}


// cerca una chiave k nell'albero t e restituisce la profondità alla quale si trova
// oppure 0 se la chiave non è presente in t

int search(Tree t, int k){

struct Nodo* n= t;
int depth = 0;

while (n != NULL){
depth++;
if (n->key < k) n = n->left;
else if (n->key == k) return depth;
else n = n->right;
}

return 0;
}

int stampaa(Tree T) {

struct Nodo* n = T;

if (n == NULL)
return -1;
//caso ricorsivo (albero non vuoto)
else {
// esamina radice
printf("%d\n", n->key);
// visita sottoalbero sinistro
stampaa(n->left);
// visita sottoalbero destro
stampaa(n->right);
}
return 1;

}
int main() {

int a;
int k,i;
Tree t= NULL;
printf("inserisci chiave\n");
scanf("%d", &a);
while(a!=-1)
{

if(search(t,a)==0)
insert(&t, a);

scanf("%d", &a);
}
printf("stampa \n");
stampaa(t);
}


IL MIO BUG è che alcuni interi già presenti nell albero vengono inseriti =..

[oregon]

DEVI inserire il codice che mostri tra i tag CODE (tasto CODE) altrimenti nessuno potrà seguirlo e correggerlo ...

[YuYevon]

Il problema è in search(): a sinistra ci devi andare se la chiave del nodo corrente risulta maggiore di k, non minore

int search(Tree t, int k)
{
    struct Nodo *n = t;
    int depth = 0;

    while (n != NULL) {
        depth++;
        if (n->key > k)
            n = n->left;
        else    if (n->key == k)
                    return depth;
                else
                    n = n->right;
    }

    return 0;
}

la prossima volta comunque riporta il codice con i tag code come previsto anche dal regolamento, altrimenti il codice diventa illeggibile.