Vue générale de l'arbre, mise en œuvre et plus

Beaucoup de gens ont probablement essayé de trouver une construction générale d'arbre, mais le moteur de recherche n'a trouvé que des binaires... Arbre de recherche binaire, parcours d'arbre binaire et bien d'autres algorithmes.
Oui, en effet, l'arborescence générale n'est utilisée nulle part, le parcours est lent, les cas d'utilisation sont petits.

Alors, je me suis posé cette question et maintenant je vais vous expliquer comment est construit l'arbre. Ainsi, idéalement, une arborescence générale devrait stocker trois variables :

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

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

Déclarons un pointeur vers le sommet :

Node *tree = NULL;

Nous devons nous mettre d'accord à l'avance sur la façon de saisir les sommets ; ce n'est pas un arbre binaire, et chaque sommet peut avoir autant d'enfants que l'on souhaite.

• + 2 (ou +ssbb 2) - insertion dans un arbre (pour un arbre général, le chemin est donné par la ligne, où r est la création d'une racine, s est une transition vers le fils aîné, b est une transition vers un frère);

Je vais donner 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

Tout d'abord, créons une fonction qui ajoute un sommet, c'est-à-dire alloue de la mémoire pour le sommet et passe un pointeur vers ce sommet (initialement connecté à quoi que ce soit).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //обнуляем указатели к братьям и сыновьям, независимая вершина, которая хранит value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Vous devez également créer une fonction qui gère la chaîne de chemin (+bs...). Chaque fois que nous démarrons le parcours depuis la racine, s'il n'est pas créé, alors nous sortons NULL (nous ne pouvons rien faire). S’il n’y a pas de sommet, alors nous devons le créer. Nous allons à la fonction de création d'arbre et obtenons un pointeur vers la racine.

Notez que Node**tree transmet la structure et ne la copie pas. Cela nous donne la possibilité de modifier des choses que nous ne pouvons pas faire avec la déclaration Node *tree.

En général, il faut trouver un pointeur vers le sommet auquel on doit ajouter les 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); // создаем корень
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // функция, которая возвращает указатель на сына
            continue;
          return NULL; //иначе NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) //возвращает указатель на брата t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // мы перешли к вершине, к которой хотели 
   //и теперь идем к последнему ее сыну,
   //чтобы добавить в конец списка
    t->brother = create_tree(value);
    return t->brother;
    }
    else {//если сына нет, то создадим его
      t->son = create_tree(value);
      return t->son;
    }
}

C'est ainsi que nous construisons un arbre.

P.S. mon premier article, alors s'il vous plaît, ne jugez pas trop durement

Source: habr.com