Ogólny widok drzewa, implementacja i nie tylko

Wiele osób zapewne próbowało znaleźć ogólną konstrukcję drzewa, ale wyszukiwarka znalazła tylko binarne... Drzewo wyszukiwania binarnego, przechodzenie przez drzewo binarne i wiele innych algorytmów.
Tak, rzeczywiście, ogólne drzewo nie jest nigdzie używane, przechodzenie jest powolne, przypadki użycia są niewielkie.

Zadałem sobie więc to pytanie i teraz wyjaśnię, jak zbudowane jest drzewo. W idealnym przypadku ogólna struktura drzewa powinna przechowywać trzy zmienne:

• wskazówka na najstarszego syna
• wskazówka na brata
• dane, które będziesz przechowywać

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

Zadeklarujmy wskaźnik do wierzchołka:

Node *tree = NULL;

Musimy z góry uzgodnić sposób wprowadzania wierzchołków; to nie jest drzewo binarne i każdy wierzchołek może mieć dowolną liczbę dzieci.

• + 2 (lub +ssbb 2) - wstawienie do drzewa (w przypadku drzewa ogólnego ścieżkę wyznacza linia, gdzie r jest utworzeniem korzenia, s jest przejściem do najstarszego syna, b jest przejściem do brat);

Podam przykład:

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

Rezultatem będzie takie drzewo:

1
  2
    5
  3
    6
    7
  3

Najpierw utwórzmy funkcję dodającą wierzchołek, a mianowicie przydzielającą pamięć dla wierzchołka i przekazującą wskaźnik do tego wierzchołka (początkowo nie połączonego z niczym).

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

Musisz także utworzyć funkcję obsługującą ciąg ścieżki (+bs...). Za każdym razem, gdy rozpoczynamy przechodzenie od korzenia, jeśli nie został on utworzony, wypisujemy NULL (nie możemy nic zrobić). Jeśli nie ma wierzchołka, musimy go utworzyć. Przechodzimy do funkcji tworzenia drzewa i otrzymujemy wskaźnik do korzenia.

Zauważ, że drzewo Node** przekazuje strukturę, a nie ją kopiuje. Daje nam to możliwość zmiany rzeczy, których nie możemy zrobić za pomocą deklaracji Node *tree.

Ogólnie rzecz biorąc, musimy znaleźć wskaźnik do wierzchołka, do którego musimy dodać syna:

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

W ten sposób budujemy drzewo.

P.S. mój pierwszy artykuł, więc proszę nie oceniać zbyt surowo

Źródło: www.habr.com