algorithm
Alberi

Osservazioni

introduzione

Gli alberi sono un sottotipo della struttura dei dati del grafico del bordo del nodo più generale.

Per essere un albero, un grafico deve soddisfare due requisiti:

• È aciclico. Non contiene cicli (o "cicli").
• È connesso Per ogni dato nodo nel grafico, ogni nodo è raggiungibile. Tutti i nodi sono raggiungibili attraverso un percorso nel grafico.

La struttura dei dati dell'albero è abbastanza comune nell'ambito dell'informatica. Gli alberi vengono utilizzati per modellare molte strutture di dati algoritmici diversi, come alberi binari ordinari, alberi rosso-neri, alberi B, alberi AB, 23 alberi, heap e tentativi.

è comune riferirsi a un albero come Rooted Tree di:

choosing 1 cell to be called `Root`
painting the `Root` at the top
creating lower layer for each cell in the graph depending on their distance from the root -the bigger the distance, the lower the cells (example above)

simbolo comune per gli alberi: T

Rappresentazione tipica dell'albero anare

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);
  }

Per verificare se due alberi binari sono uguali o meno

1. Ad esempio se gli input sono:

Esempio 1

un)

b)

L'output dovrebbe essere vero.

Esempio: 2

Se gli input sono:

un)

b)

L'output dovrebbe essere falso.

Pseudo codice per lo stesso:

boolean sameTree(node root1, node root2){

if(root1 == NULL && root2 == NULL)
return true;

if(root1 == NULL || root2 == NULL)
return false;

if(root1->data == root2->data 
     && sameTree(root1->left,root2->left)
        && sameTree(root1->right, root2->right))
return true;

}