urgente C alberi ternari!!!

[TorpedoBlu]

devo mettere dei percorsi di nodi della mia struttura in un albero ternario, questo albero rappresenta i possibili cammini dal nodo start al nodo end.


typedef int polline;

typedef int prato;

/*key : indice della posizione del fiore sul piano*/
struct key{
int X;
int Y;
};

typedef struct key key;


/*albero binario: rappresenta i punti del piano*/
struct searchtree {
prato id_prato;
polline raccolto;
key chiave;
struct searchtree *left, *right, *up;
};

typedef struct searchtree searchtree;

/*campo : rappresenta un insieme di prati che hanno punti in comune*/
struct field{
int id_campo;
int id_prato;
struct field *next;
};

typedef struct field field;

/*lista di campi*/
field *PRATO_FIORITO;

struct routetree{
polline totale;
key chiave;
struct routetree *left, *right, *center, *up;
};

typedef struct routetree routetree;

routetree *CAMMINI;
routetree *createroutetree(searchtree *start){
routetree *q = malloc(sizeof(routetree));
q->left=q->right=q->center=NULL;
q->totale=start->raccolto;
q->chiave=start->chiave;
return q;
}

int checkstep(key *step, searchtree *end){
int deltax=(abs)(end->chiave.X - step->X);
int deltay=(end->chiave.Y - step->Y);
if(deltay>=deltax)
return 1;
return 0;
}

routetree *buildroutetree(searchtree *piano, routetree *cammini, searchtree *end){
searchtree *searchtree_tmp;
key *key_tmp;
if(isMin(cammini->chiave,end->chiave)>0){
key_tmp->X=cammini->chiave.X-1;
key_tmp->Y=cammini->chiave.Y+1;
if(searchtree_tmp=itsearch(piano, *key_tmp)){
if(checkstep(key_tmp, end)){
cammini->left=malloc(sizeof(routetree));
cammini->left->up=cammini;
cammini->left->chiave=searchtree_tmp->chiave;
cammini->left->totale=searchtree_tmp->raccolto+cammini->totale;
cammini->left->left=buildroutetree(piano, cammini->left, end);
cammini->left->center=buildroutetree(piano, cammini->left, end);
cammini->left->right=buildroutetree(piano, cammini->left, end);
}
else
cammini->left=NULL;
}
else
cammini->left=NULL;

key_tmp->X=cammini->chiave.X;
key_tmp->Y=cammini->chiave.Y+1;
if(searchtree_tmp=itsearch(piano, *key_tmp)){
if(checkstep(key_tmp, end)){
cammini->center=malloc(sizeof(routetree));
cammini->center->up=cammini;
cammini->center->chiave=searchtree_tmp->chiave;
cammini->center->totale=searchtree_tmp->raccolto+cammini->totale;
cammini->center->left=buildroutetree(piano, cammini->center, end);
cammini->center->center=buildroutetree(piano, cammini->center, end);
cammini->center->right=buildroutetree(piano, cammini->center, end);
}
else
cammini->center=NULL;
}
else
cammini->center=NULL;

key_tmp->X=cammini->chiave.X+1;
key_tmp->Y=cammini->chiave.Y+1;
if(searchtree_tmp=itsearch(piano, *key_tmp)){
if(checkstep(key_tmp, end)){
cammini->right=malloc(sizeof(routetree));
cammini->right->up=cammini;
cammini->right->chiave=searchtree_tmp->chiave;
cammini->right->totale=searchtree_tmp->raccolto+cammini->totale;
cammini->right->left=buildroutetree(piano, cammini->right, end);
cammini->right->center=buildroutetree(piano, cammini->right, end);
cammini->right->right=buildroutetree(piano, cammini->right, end);
}
else
cammini->right=NULL;
}
else
cammini->right=NULL;
}
return cammini;
}


questi li spezzoni di codice, ho cercato di creare il primo nodo con il metodo createroutetree() e poi riempirlo ricorsivamente con build routetree()

lo so fa schifo, se qualcuno mi posta il codice per costruire un albero ternario gli offro una birra a Milano (anche 2)

[TorpedoBlu]

panico panico, probabilmente gli alberi ternari sono una cazzata....

Dijkstra, per usare questo algoritmo come faccio? nel senso io mio albero binario è ordinato in base alla chiave (X,Y)

ma ad esempio per andare da 0,0 a 2,2 se il cammino esiste esso è per forza 0,0-1,1-2,2

la mia ape si può muovere solo in alto ed in diagonale alta (chiaramente se esistono tutti i nodi che compongono il cammino)

se ci sono + cammini prendo il cammino con il quantitativo di polline maggiore.

ma come si applica Dijkstra ad un albero binario? e che modifiche devo fare??? i valori di polline eventualmente negativi danno problemi???