Vue générale de l'arborescence, mise en œuvre et pas seulement

Beaucoup ont probablement essayé de trouver la construction d'un arbre général, mais le moteur de recherche n'a trouvé que des arbres binaires ... L'arbre de recherche binaire, la traversée de l'arbre binaire et bien d'autres algorithmes.
Oui, en effet, l'arbre général n'est utilisé nulle part, le bypass est lent, les cas d'utilisation sont petits.

J'ai donc posé cette question et maintenant je vais vous expliquer comment l'arbre est construit. Donc, idéalement, la structure d'un arbre de forme générale devrait stocker trois variables:

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

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

Déclarez un pointeur vers le haut:

 Node *tree = NULL; 

Nous devons convenir à l'avance de la façon d'entrer les sommets, ce n'est pas un arbre binaire, et chaque sommet peut avoir des fils.

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

Je vais donner un exemple:

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

En conséquence, cet arbre sera publié:

 1 2 5 3 6 7 3 

Tout d'abord, créez une fonction qui ajoute un sommet, à savoir, alloue de la mémoire au sommet et transmet un pointeur à ce sommet (initialement sans rapport avec 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 traite la chaîne de chemin (+ bs ...). Chaque fois que nous commençons la traversée depuis la racine, si elle n'est pas créée, nous imprimons NULL (nous ne pouvons rien faire). S'il n'y a pas de pic, nous devons le créer. Accédez à la fonction de création d'arbre et obtenez un pointeur sur la racine.

Remarque: L'arbre Node ** passe la structure, pas la copie. Cela nous donne la possibilité de changer ce qui ne peut pas être fait, contrairement à la déclaration d'arborescence Node *.

En général, nous devrions trouver un pointeur vers le haut, 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] != '\0') { 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; } } 

De cette façon, nous construisons un arbre.

PS est mon premier article, alors ne jugez pas strictement