Opći pogled na stablo, implementacija i više

Vjerojatno su mnogi ljudi pokušali pronaći konstrukciju općeg stabla, ali je tražilica pronašla samo binarne... Binarno stablo pretraživanja, obilazak binarnog stabla i mnogi drugi algoritmi.
Da, doista, opće stablo se nigdje ne koristi, obilaženje je sporo, slučajevi korištenja su mali.

Dakle, postavio sam si ovo pitanje i sada ću objasniti kako se stablo gradi. Dakle, idealno, opća struktura stabla trebala bi pohraniti tri varijable:

• pokazivač na najstarijeg sina
• pokazivač na brata
• podatke koje ćete pohraniti

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

Deklarirajmo pokazivač na vrh:

Node *tree = NULL;

Moramo se unaprijed dogovoriti kako unositi vrhove; ovo nije binarno stablo i svaki vrh može imati koliko god djece želi.

• + 2 (ili +ssbb 2) - umetanje u stablo (za opće stablo, put je zadan linijom, gdje je r stvaranje korijena, s je prijelaz na najstarijeg sina, b je prijelaz na brat);

Dat ću primjer:

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

Rezultat će biti ovakvo stablo:

1
  2
    5
  3
    6
    7
  3

Prvo, kreirajmo funkciju koja dodaje vrh, naime, dodjeljuje memoriju za vrh i prosljeđuje pokazivač na ovaj vrh (u početku nije povezan ni s čim).

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

Također morate stvoriti funkciju koja rukuje nizom staze (+bs...). Svaki put kad započnemo obilazak iz korijena, ako se ne kreira, ispisujemo NULL (ne možemo ništa učiniti). Ako nema vrha, onda ga moramo stvoriti. Idemo na funkciju create tree i dobivamo pokazivač na korijen.

Imajte na umu da Node**tree prosljeđuje strukturu, a ne kopira je. To nam daje mogućnost mijenjanja stvari koje ne možemo učiniti s deklaracijom Node *tree.

Općenito, moramo pronaći pokazivač na vrh kojem trebamo dodati sina:

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

Ovako gradimo drvo.

p.s. moj prvi članak, pa vas molim da ne sudite prestrogo

Izvor: www.habr.com