algorithm Rappresentazione tipica dell'albero anare


Esempio

In genere rappresentiamo un albero anulare (uno con figli potenzialmente illimitati per nodo) come un albero binario, (uno con esattamente due bambini per nodo). Il "prossimo" bambino è considerato un fratello. Nota che se un albero è binario, questa rappresentazione crea nodi aggiuntivi.

Quindi, iteriamo sui fratelli e ricacciamo i bambini. Poiché la maggior parte degli alberi sono relativamente poco profondi - molti bambini ma solo pochi livelli di gerarchia, questo dà origine a un codice efficiente. Nota le genealogie umane sono un'eccezione (molti livelli di antenati, solo pochi bambini per livello).

Se necessario, i puntatori possono essere mantenuti per consentire l'ascensione dell'albero. Questi sono più difficili da mantenere.

Si noti che è tipico che una funzione richiami alla radice e una funzione ricorsiva con parametri aggiuntivi, in questo caso la profondità dell'albero.

  struct node
  {
     struct node *next;
     struct node *child;
     std::string data;
  }

  void printtree_r(struct node *node, int depth)
  {
     int i;

     while(node)
     {
         if(node->child)
         {
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
            printtree_r(node->child, depth +1);
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
    
            for(i=0;i<depth*3;i++)
               printf(" ");
             printf("%s\n", node->data.c_str());

             node = node->next;
          }
      }
  }

  void printtree(node *root)
  {
     printree_r(root, 0);
  }