🥇Algemeen beeld van de boom, implementatie en meer

Veel mensen hebben waarschijnlijk geprobeerd een algemene boomstructuur te vinden, maar de zoekmachine vond alleen binaire bomen... Binaire zoekboom, binaire boomtraversal en vele andere algoritmen.
Ja, inderdaad, de algemene boom wordt nergens gebruikt, de traversal is traag, de use cases zijn klein.

Dus ik stelde mezelf deze vraag en nu zal ik uitleggen hoe de boom is gebouwd. Dus idealiter zou een algemene boomstructuur drie variabelen moeten opslaan:

verwijzing naar oudste zoon
verwijzing naar broer
de gegevens die u gaat opslaan

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

Laten we een verwijzing naar het hoekpunt declareren:

Node *tree = NULL;

We moeten van tevoren afspreken hoe we hoekpunten moeten invoeren; dit is geen binaire boom en elk hoekpunt kan zoveel kinderen hebben als gewenst.

+ 2 (of +ssbb 2) - invoeging in een boom (voor een algemene boom wordt het pad gegeven door de lijn, waarbij r de creatie van een wortel is, s een overgang is naar de oudste zoon, b een overgang is naar een broer);

Ik zal een voorbeeld geven:

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

Het resultaat is een boom zoals deze:

Laten we eerst een functie maken die een hoekpunt toevoegt, namelijk geheugen toewijst aan het hoekpunt en een verwijzing doorgeeft naar dit hoekpunt (aanvankelijk nergens mee verbonden).

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

U moet ook een functie maken die de padtekenreeks (+bs...) verwerkt. Elke keer dat we de traversal vanaf de root starten en deze niet is gemaakt, geven we NULL weer (we kunnen niets doen). Als er geen hoekpunt is, moeten we het creëren. We gaan naar de functie boom maken en krijgen een verwijzing naar de root.

Merk op dat Node**tree de structuur doorgeeft en niet kopieert. Dit geeft ons de mogelijkheid om dingen te veranderen die we niet kunnen doen met de Node *tree-declaratie.

Over het algemeen moeten we een verwijzing vinden naar het hoekpunt waaraan we de 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); // создаем корень
            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;
    }
}

Zo bouwen we een boom.

P.S. mijn eerste artikel, dus oordeel alsjeblieft niet te hard

Bron: www.habr.com

Algemeen beeld van de boom, implementatie en meer

Voeg een reactie Reactie annuleren