Algemene structuur van een boom, implementatie en meer

Veel mensen hebben waarschijnlijk geprobeerd een algemeen boomstructuur te vinden, maar zoekmachines vonden alleen binaire... Binaire zoekbomen, traverseren van binaire bomen en vele andere algoritmen.
Ja, een algemeen boomstructuur wordt nergens gebruikt, de traversering is traag, de gebruiksmogelijkheden zijn beperkt.

Ik heb me deze vraag gesteld en zal nu uitleggen hoe een boom wordt gebouwd. Idealiter zou de structuur van een algemeen boom drie variabelen moeten opslaan:

• een verwijzing naar de oudste zoon
• een verwijzing naar de broer
• de gegevens die je wilt opslaan

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

Laten we een verwijzing naar de top verklaren:

Node *tree = NULL;

We moeten vooraf afspraken maken over hoe we de knopen invoeren, het is immers geen binaire boom, en elke knoop kan een onbeperkt aantal zonen hebben.

• + 2 (of +ssbb 2) — toevoegen aan de boom (voor een algemeen boomstructuur wordt het pad aangegeven met een string, waar r de wortel aanmaakt, s — naar de oudste zoon gaat, b — naar de broer gaat);

Ik geef een voorbeeld:

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

Het resultaat is een dergelijke boom:

1
  2
    5
  3
    6
    7
  3

Laten we beginnen met het creëren van een functie die een knoop toevoegt, dat wil zeggen, geheugen toewijst voor een knoop en de verwijzing naar deze knoop doorgeeft (aanvankelijk niet verbonden met iets).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //initialiseer de verwijzingen naar broers en zonen, een onafhankelijke knoop die value opslaat
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

We moeten ook een functie maken die de padstring (+bs…) verwerkt. We beginnen elke keer vanaf de wortel, als deze niet bestaat, geven we NULL weer (we kunnen niets doen). Als de knoop er niet is, moeten we deze maken. Ga naar de functie om de boom te creëren en ontvang de verwijzing naar de wortel.

Opmerking, Node ** tree geeft de structuur door, in plaats van deze te kopiëren. Dit geeft ons de mogelijkheid om te wijzigen, wat niet mogelijk is bij het verklaren van Node *tree.

In feite moeten we de verwijzing naar de knoop vinden waaraan we een zoon moeten toevoegen:

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); // we create the root
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // function that returns a pointer to the son
            continue;
          return NULL; // otherwise NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // returns a pointer to brother t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // we reached the vertex we wanted 
   // and now go to its last son,
   // to add to the end of the list
    t->brother = create_tree(value);
    return t->brother;
    }
    else { // if there is no son, we will create it
      t->son = create_tree(value);
      return t->son;
    }
}

Zo bouwen we de boom.

P.S. mijn eerste artikel, dus ik vraag je niet te hard te oordelen

Bron: habr.com