Ogólny widok drzewa, realizacja i nie tylko

Wielu zapewne próbowało znaleźć strukturę drzewa ogólnego, ale wyszukiwarka znajdowała tylko drzewa binarne... Drzewo binarne wyszukiwania, przejście drzewa binarnego i wiele innych algorytmów.
Tak, rzeczywiście, drzewo ogólnego typu nigdzie nie jest wykorzystywane, przechodzenie jest wolne, a możliwości zastosowania są niewielkie.

Zadałem sobie to pytanie i teraz wyjaśnię, jak właściwie buduje się drzewo. Zatem w idealnym przypadku struktura drzewa ogólnego powinna przechowywać trzy zmienne:

• wskaźnik na najstarszego syna
• wskaźnik na brata
• dane, które zamierzasz przechowywać

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

Ogłosimy wskaźnik na wierzchołek:

Node *tree = NULL;

Musimy wcześniej uzgodnić, jak przeprowadzać wprowadzenie wierzchołków, to przecież nie jest drzewo binarne, a każdy wierzchołek może mieć dowolną liczbę synów.

• + 2 (lub +ssbb 2) — wstawienie do drzewa (dla drzewa ogólnego ścieżka jest określona przez ciąg, w którym r oznacza utworzenie korzenia, s — przejście do najstarszego syna, b — przejście do brata);

Podam przykład:

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

W wyniku powstanie takie drzewo:

1
  2
    5
  3
    6
    7
  3

Na początek stwórzmy funkcję, która dodaje wierzchołek, a konkretnie przydziela pamięć dla wierzchołka i przekazuje wskaźnik na ten wierzchołek (początkowo niepowiązany z niczym).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // zerujemy wskaźniki do braci i synów, niezależny wierzchołek, który przechowuje wartość
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Należy także stworzyć funkcję, która przetwarza ciąg ścieżki (+bs…). Za każdym razem zaczynamy przejście od korzenia, jeśli nie jest stworzony, wyświetlamy NULL (nie możemy nic zrobić). Jeśli wierzchołka nie ma, musimy go stworzyć. Przechodzimy do funkcji utwórz drzewo i otrzymujemy wskaźnik na korzeń.

Dla uwagi, Node ** tree przekazuje strukturę, a nie kopiuje. To daje nam możliwość modyfikacji, czego nie można zrobić w przeciwieństwie do deklaracji Node *tree.

Generalnie musimy znaleźć wskaźnik na wierzchołek, do którego należy 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); // tworzymy korzeń
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funkcja, która zwraca wskaźnik na syna
            continue;
          return NULL; // w przeciwnym razie NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // zwraca wskaźnik na brata t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // przeszliśmy do wierzchołka, do którego chcieliśmy 
   // a teraz idziemy do jego ostatniego syna,
   // aby dodać na koniec listy
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// jeśli nie ma syna, to go stworzymy
      t->son = create_tree(value);
      return t->son;
    }
}

W ten sposób budujemy drzewo.

P.S. to mój pierwszy artykuł, więc proszę nie oceniajcie surowo

Źródło: habr.com