Vue d'ensemble de l'arbre, implémentation et plus encore

Beaucoup ont probablement essayé de trouver la construction d'un arbre de type général, mais le moteur de recherche ne trouvait que des arbres binaires... Arbre binaire de recherche, parcours d'arbre binaire et de nombreux autres algorithmes.
Oui, en effet, l'arbre de type général n'est utilisé nulle part, le parcours est lent, et les cas d'utilisation sont limités.

Ainsi, je me suis posé cette question et je vais maintenant expliquer comment construire un arbre de ce type. Idéalement, la structure d'un arbre de type général devrait contenir trois variables :

• un pointeur vers le fils aîné
• un pointeur vers le frère
• les données que vous souhaitez stocker

struct Tnode {
    int key;
    struct Tnode *son;
    struct Tnode *brother;
};
typedef struct Tnode Node;

Déclarons un pointeur vers la racine :

Node *tree = NULL;

Nous devons convenir à l'avance de la manière d'insérer des nœuds, car ce n'est pas un arbre binaire, et chaque nœud peut avoir un nombre illimité de fils.

• + 2 (ou +ssbb 2) — insertion dans l'arbre (pour un arbre de type général, le chemin est spécifié par une chaîne où r crée la racine, s — passe au fils aîné, b — passe au frère);

Prenons un exemple :

+r 1
+ 2
+ 3
+ 3
+s 5
+sb 6
+sb 7

Le résultat sera un arbre comme celui-ci :

1
  2
    5
  3
    6
    7
  3

Commençons par créer une fonction qui ajoute un nœud, c'est-à-dire qui alloue de la mémoire pour le nœud et renvoie un pointeur vers ce nœud (initialement non lié à quoi que ce soit).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // nous remettons à zéro les pointeurs vers les frères et les fils, un nœud indépendant qui stocke la valeur
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Nous devons également créer une fonction qui traite la chaîne de chemin (+bs…). À chaque fois, nous commençons le parcours à partir de la racine, si elle n'est pas créée, nous affichons NULL (nous ne pouvons rien faire). S'il n'y a pas de nœud, nous devons le créer. Nous appelons la fonction de création d'arbre et obtenons un pointeur vers la racine.

À noter, Node ** tree passe la structure et ne la copie pas. Cela nous donne la possibilité de modifier, ce qui n'est pas possible avec la déclaration Node *tree.

En résumé, nous devons trouver un pointeur vers le nœud auquel nous devons ajouter un fils :

Node* add_node(Node **tree, const char *a) {
  Node* t = *tree;
  int value;
  scanf("%d", &value);
  int i = 0;
      while (a[++i] != ' ') {
        if (a[i] == 'r') {
            *tree = create_tree(value); // création de la racine
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // fonction qui renvoie un pointeur sur le fils
            continue;
          return NULL; // sinon NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // renvoie un pointeur sur le frère t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // nous avons atteint le sommet que nous voulions 
   // et maintenant allons au dernier de ses fils,
   // pour ajouter à la fin de la liste
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// s'il n'y a pas de fils, nous allons le créer
      t->son = create_tree(value);
      return t->son;
    }
}

Ainsi, nous construisons l'arbre.

P.S. C'est mon premier article, donc je vous prie de ne pas être trop sévères.

Source : habr.com