algorithm
Des arbres

Remarques

introduction

Les arbres sont un sous-type de la structure de données de graphique de bord de nœud plus générale.

Pour être un arbre, un graphique doit satisfaire à deux exigences:

• C'est acyclique. Il ne contient aucun cycle (ou "boucles").
• Il est connecté. Pour tout nœud donné du graphe, chaque nœud est accessible. Tous les nœuds sont accessibles via un chemin dans le graphique.

La structure de données arborescente est assez courante en informatique. Les arbres sont utilisés pour modéliser de nombreuses structures de données algorithmiques différentes, telles que les arbres binaires ordinaires, les arbres rouge-noir, les arbres B, les arbres AB, les arbres 23, le tas et les essais.

il est courant de faire référence à un arbre en tant Rooted Tree par:

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)

symbole commun pour les arbres: T

Représentation typique d'un arbre anary

Généralement, nous représentons un arbre anary (un avec des enfants potentiellement illimités par nœud) en tant qu'arbre binaire (un avec exactement deux enfants par nœud). Le "prochain" enfant est considéré comme un frère. Notez que si une arborescence est binaire, cette représentation crée des nœuds supplémentaires.

Nous parcourons ensuite les frères et sœurs et faisons reculer les enfants. Comme la plupart des arbres sont relativement peu profonds - beaucoup d’enfants mais seulement quelques niveaux hiérarchiques, cela donne lieu à un code efficace. Notez que les généalogies humaines sont une exception (beaucoup de niveaux d'ancêtres, seulement quelques enfants par niveau).

Si nécessaire, des pointeurs peuvent être conservés pour permettre l’ascension de l’arbre. Ce sont plus difficiles à maintenir.

Notez qu'il est courant d'avoir une fonction pour appeler la racine et une fonction récursive avec des paramètres supplémentaires, dans ce cas la profondeur de l'arborescence.

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

Pour vérifier si deux arbres binaires sont identiques ou non

1. Par exemple si les entrées sont:

Exemple 1

une)

b)

La sortie devrait être vraie.

Exemple: 2

Si les entrées sont:

une)

b)

La sortie devrait être fausse.

Pseudo-code pour le même:

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;

}