Översikt över trädet, genomförande med mera

Många försökte säkert hitta en allmän trädkonstruktion, men sökmotorn hittade bara binära sådana... Binärt sökträd, binärt trädtraversal och många andra algoritmer.
Ja, faktiskt, det allmänna trädet används inte någonstans, övergången är långsam, användningsfallen är små.

Så jag ställde mig den här frågan och nu ska jag förklara hur trädet är byggt. Så idealiskt bör en allmän trädstruktur lagra tre variabler:

• pekare till äldste sonen
• pekare till bror
• data du ska lagra

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

Låt oss förklara en pekare till vertex:

Node *tree = NULL;

Vi måste komma överens i förväg om hur man anger hörn, detta är inte ett binärt träd, och varje vertex kan ha så många barn som önskas.

• + 2 (eller +ssbb 2) - infogning i ett träd (för ett allmänt träd ges vägen av linjen, där r är skapandet av en rot, s är en övergång till den äldsta sonen, b är en övergång till en bror);

Jag ska ge ett exempel:

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

Resultatet blir ett träd så här:

1
  2
    5
  3
    6
    7
  3

Låt oss först skapa en funktion som lägger till en vertex, nämligen allokerar minne för vertexen och skickar en pekare till denna vertex (till en början inte kopplad till någonting).

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

Du måste också skapa en funktion som hanterar sökvägssträngen (+bs...). Varje gång vi startar traverseringen från roten, om den inte skapas, matar vi ut NULL (vi kan inte göra någonting). Om det inte finns någon vertex måste vi skapa den. Vi går till funktionen skapa träd och får en pekare till roten.

Observera att Node**tree passerar strukturen, inte kopierar den. Detta ger oss möjligheten att ändra saker som vi inte kan göra med Node *tree-deklarationen.

I allmänhet måste vi hitta en pekare till vertexet som vi behöver lägga till sonen till:

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;
    }
}

Det är så vi bygger ett träd.

P.S. min första artikel, så döm inte för hårt

Källa: will.com