Alberi binari di ricerca

Dichiarazioni

typedef struct nodo 
{
    int info; struct nodo *sx,
                          *dx;
} NODO;

typedef NODO *ptree;

Operazioni

Aggiungere un nodo
Se l’informazione è già contenuta nell’albero non sarà inserita

void add_nodo(ptree *p, int N)
{
    if((*p) == NULL)
    {
        (*p)=(ptree)malloc(sizeof(NODO));
        (*p)->info=N;
        (*p)->sx=NULL;
        (*p)->dx=NULL;
    }
    else if(N < (*p)->info)
        add_nodo(&((*p)->sx), N);
    else if(N > (*p)->info)
        add_nodo(&((*p)->dx), N);
}

Ricerca di un nodo
Restituisce il puntatore al nodo con l’informazione data

pnodo ric_nodo(ptree p, int N)
{
    if(p == NULL)
        return NULL;
    else if(N < p->info)
        return ric_nodo(p->sx, N);
    else if(N == p->info)
        return p;
    else
        return ric_nodo(p->dx, N);
}

Visita
L’output sarà ordinato…

void inorder(ptree p)
{
    if(p != NULL)
    {
         inorder(p->sx);
         printf("%d ", p->info);
         inorder(p->dx);
    }
}

---

Se sono ammessi valori ripetuti è utile aggiungere un contatore in ogni nodo

Dichiarazioni

typedef struct nodo 
{
    int         info;
    int         conta;
    struct nodo *sx,
                *dx;
} NODO;

typedef NODO *ptree;

Operazioni

Aggiungere un nodo
Se l’informazione è già contenuta nell’albero si incrementa il contatore

void add_nodo(ptree *p, int N)
{
    if((*p) == NULL)
    {
        (*p)=(ptree)malloc(sizeof(NODO));
        (*p)->info=N;
        (*p)->conta=1;
        (*p)->sx=NULL;
        (*p)->dx=NULL;
    }
    else if(N < (*p)->info)
        add_nodo(&((*p)->sx), N);
    else if(N == (*p)->info)
        (*p)->conta +=1;
    else
        add_nodo(&((*p)->dx), N);
}

Ricerca di un nodo
Restituisce il contatore

int ric_nodo(ptree p, int N)
{
    if(p == NULL)
        return 0;
    else if(N < p->info)
        return ric_nodo(p->sx, N);
    else if(N == p->info)
        return p->conta;
    else
        return ric_nodo(p->dx, N);
}

Visita

void inorder(ptree p)
{
    if(p != NULL)
    {
        inorder(p->sx);
        printf("%d %d\n", p->info, p->conta);
        inorder(p->dx);
    }
}