#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N (1000)
/* Definisco il tipo Nodo*/
struct Nodo
{
char val[N+1];
struct Nodo* left;
struct Nodo* right;
};
/*Definisco l'albero binario di ricerca*/
typedef struct Nodo* Albero;
/*
DEFINIZIONE DELLE PROCEDURE E DELLE FUNZIONI
*/
/*Definizione della procedura di inserimento chiavi*/
void inserisci (Albero *t, char valore[]);
/*Definizione della funzione del calcolo dell'altezza*/
int altezza(Albero t);
/*Definizione della funzione di ricerca iterativa*/
Albero RicercaIterativa(Albero t, char valore[]);
/*Definizione della funzione che restituisce i primi N caratteri uguali*/
int sstringlen (const char * a, const char * b);
/*Definizione della funzione che restituisce la sottostringa piu lunga radicata
* nel sottoalbero*/
int soluzione (Albero t);
/*
* FUNZIONE MAIN
*/
int main ()
{
int numchiavi,i;
char str[N+1];
char cercare[N+1];
Albero t = NULL;
/*Leggo da input il numero di chiavi*/
scanf("%d",&numchiavi);
for (i=0; i<numchiavi;i++)
{
scanf("%s", str);
inserisci(&t, str);
}
/*Routine di test --- la stampa č in fondo*/
printf("\n");
printf("Chiave da cercare: ");
scanf("%s",cercare);
RicercaIterativa(t,cercare);
return 0;
}
/*
FUNZIONI ALBERO BINARIO DI RICERCA
*/
/*Procedura Inserimento*/
void inserisci (Albero *t, char valore[])
{
struct Nodo* p;
struct Nodo* x;
struct Nodo* e;
x = *t;
/*Creo il nodo da inserire contenente il valore*/
e = malloc(sizeof(struct Nodo));
strcpy(e->val,valore);
e->left = e->right = NULL;
/*Se l'albero č vuoto imposto '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 (strcmp(x->val, valore) < 0)
{
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 (strcmp(p->val, valore) < 0)
{
p->right = e;
}
else
{
p->left = e;
}
}
/*Funzione di ricerca iterativa
*Restituisce il puntatore al nodo con chiave k, se esiste, altrimenti NULL*/
Albero RicercaIterativa(Albero t, char valore[])
{
int sol = 0;
while ( (t != NULL) && (strcmp(valore, t->val) != 0))
{
if (strcmp(valore, t->val) < 0)
t = t->left;
else
t = t->right;
}
sol = soluzione(t);
printf("Risultato: %d",sol);
return t;
}
int sstringlen (const char * a, const char * b)
{
int i = 0;
if (a == NULL || b == NULL)
{
return 0;
}
while (a[i]!= '\0' && b[i]!= '\0' && a[i] == b[i])
{
i++;
}
return i;
}
/*Funzione che restituisce la sottostringa piu lunga radicata nel sottoalbero*/
int soluzione (Albero t)
{
int max = 0, maxs, maxd, max2;
if (t->left == NULL && t->right == NULL)
return 0;
if (t->right == NULL)
max = sstringlen(t->left->val, t->right->val);
maxs = soluzione(t->left);
if (max>maxs) return max;
else return maxs;
if (t->left == NULL)
max = sstringlen(t->right->val, t->left->val);
maxd = soluzione(t->right);
if (max>maxd) return max;
else return maxd;
maxs = soluzione(t->left);
maxd = soluzione(t->right);
max = sstringlen(t->right->val, t->left->val);
max2 = sstringlen(t->left->val, t->right->val);
if (maxs>maxd) maxd=maxs;
if (max2>max) max=max2;
if (maxd>max) return maxd;
else return max;
}
