[C] Lista di puntatori agli elementi di un albero binario

[Tidus84]

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

#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à...

[ntd]

Non ho voglia di sciropparmi tutto il programma (porongo, posta solo il codice rilevante), però m'è caduto l'occhio sulla funzione In_Order() che, a parte occupare improduttivamente la memoria, non fa altro.

Se con questa funzione devi generare una lista lineare dall'albero binario devi visitare prima il ramo di sinistra, poi accodare l'elemento corrente alla lista e poi visitare il ramo di destra. Poiché usi una lista singola (non doppia) è molto più conveniente visitare prima il ramo di destra, poi inserire in testa il nodo corrente e visitare quindi il ramo di sinistra.

/* Funzione di supporto che potrebbe venir usata direttamente */
static void
slist_prepend_btree (struct tree   *tree,
                     struct lista **head)
{
  struct lista *element;

  /* Condizione di fine ricorsione: non c'è albero da visitare */
  if (tree == NULL)
    return;

  /* Visita il ramo di destra */
  slist_prepend_btree (tree->right, head);

  /* Inserisce in testa l'elemento corrente */
  element = (struct lista *) malloc (sizeof (struct lista));
  element->punt = tree;
  element->next = *head;
  head = &element;

  /* Visita il ramo di sinistra */
  slist_prepend_btree (tree->left, head);
}


/* Mi rifiuto di chiamare questa funzione In_Order: che nome è? */
struct lista *
slist_from_btree (struct tree *tree)
{
  struct lista *head;

  head = NULL;
  slist_prepend_btree (tree, &head);
  return head;
}

Il codice non l'ho provato, ma il concetto è quello.