Salve, colleghi!
Sto facendo questo esercizio:
Dato un albero binario T, implementare una funzione, struct lista
*visitaInOrder(struct tree *T), che restituisca una lista concatenata di puntatori ai nodi
dell'albero in modo tale che l'ordine della lista concatenata rispetti l'ordine di una visita in ordine simmetrico dell'albero T.
Questo è il mio codice
codice:
#include <stdlib.h>
#include <stdio.h>
struct tree {
int key;
struct tree *left;
struct tree *right;
};
struct lista {
struct tree *punt;
struct lista *next;
};
// PROTOTIPI
struct tree *newNode (int k);
struct tree *Inserisci (struct tree *, int);
struct lista *In_Order (struct tree *);
void stampaAlberoBin (struct tree *);
// MAIN PRINCIPALE
int main ()
{
int N, Intero, i;
struct lista *Lista=NULL;
struct tree *Root=NULL;
system ("COLOR F5");
printf ("Dimmi quanti interi vuoi inserire= ");
scanf ("%d", &N);
for (i=0; i<N; ++i) {
printf ("\n%do intero= ", i+1);
scanf ("%d", &Intero);
Root=Inserisci(Root,Intero); }
printf ("\n\nAlbero creato con successo!!!\n\n");
stampaAlberoBin (Root);
printf ("\n\n");
Lista=In_Order(Root);
while (Lista!=NULL) {
printf ("Lista IN_ORDER --> %d\n", Lista->punt->key);
Lista=Lista->next; }
printf ("\n\n");
system ("PAUSE");
return 0;
}
// CREA UN NUOVO NODO
struct tree *newNode (int k)
{
struct tree *node;
node=(struct tree *)malloc(sizeof(struct tree));
node->key=k;
node->left=NULL;
node->right=NULL;
return node;
}
// INSERISCE ORDINATAMENTE GLI INTERI NELL'ALBERO
struct tree *Inserisci (struct tree *root, int k)
{
if (root==NULL)
return newNode(k);
else
if (k<root->key)
root->left=Inserisci(root->left,k);
else
root->right=Inserisci(root->right,k);
return root;
}
// STAMPA IL BST COSI COME E' STATO INSERITO
void stampaAlberoBin (struct tree *root)
{
if (root==NULL)
printf(" NIHIL ");
else {
printf("(%d ", root->key);
stampaAlberoBin(root->left);
stampaAlberoBin(root->right);
printf(" ) ");
}
}
// VISITA INORDER BST
struct lista *In_Order (struct tree *root)
{
struct lista *Temp=NULL, *tmp1=NULL, *tmp2=NULL;
if (root==NULL)
return NULL;
else {
Temp=(struct lista*) malloc (sizeof(struct lista));
Temp->punt=root;
printf ("%d ", Temp->punt->key);
system ("pause");
tmp1=In_Order(root->left);
tmp2=In_Order(root->right);
}
return Temp;
}
Il problema è che tale funzione visitando ricorsivamente e simmetricamente l'albero crea 3 nodi separati tra loro e si dovrebbero unirli, ma non riesco a capire che approccio adottare per legarle... Qualcuno mi aiuta a chiarire un pò la cosa? Grazie anticipatamente a chi mi risponderà...