Celkový vzhled stromu, realizace a nejen to

Mnozí se pravděpodobně snažili najít strukturu obecného stromu, ale vyhledávač našel pouze binární... Binární vyhledávací strom, procházení binárního stromu a mnoho dalších algoritmů.
Ano, obecně vzato, strom obecného typu se nikde nepoužívá, procházení je pomalé, možnosti použití jsou malé.

Takže jsem se touto otázkou zabýval a nyní vysvětlím, jak se vlastně strom staví. Ideálně by struktura obecného stromu měla uchovávat tři proměnné:

• ukazatel na nejstaršího syna
• ukazatel na bratra
• data, která chcete uchovávat

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

Vyhlásíme ukazatel na vrchol:

Node *tree = NULL;

Musíme se předem dohodnout, jak provádět vkládání vrcholů, protože to není binární strom a každý vrchol může mít neomezený počet synů.

• + 2 (nebo +ssbb 2) — vložení do stromu (pro strom obecného typu je cesta určena řetězcem, kde r vytváří kořen, s — přechod k nejstaršímu synovi, b — přechod k bratru);

Uvedu příklad:

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

V důsledku toho vznikne takový strom:

1
  2
    5
  3
    6
    7
  3

Nejprve vytvoříme funkci, která provádí přidání vrcholu, a to tak, že alokuje paměť pro vrchol a předává ukazatel na tento vrchol (původně nespojený s ničím).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // nulujeme ukazatele na bratry a syny, nezávislý vrchol, který uchovává value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Je také nutné vytvořit funkci, která zpracovává řetězec cesty (+bs…). Každýkrát začínáme procházení od kořene, pokud není vytvořen, zobrazíme NULL (nemůžeme nic dělat). Pokud vrchol neexistuje, musíme ho vytvořit. Přecházíme do funkce vytvořit strom a získáme ukazatel na kořen.

Na pamětihodnost, Node ** tree předává strukturu a nekopíruje ji. To nám dává možnosti měnit, což nelze udělat ve srovnání s deklarací Node *tree.

Celkově musíme najít ukazatel na vrchol, ke kterému je třeba přidat 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); // vytváříme kořen
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funkce, která vrací ukazatel na syna
            continue;
          return NULL; // jinak NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // vrací ukazatel na bratra t
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // dostali jsme se k vrcholu, ke kterému jsme chtěli
   // a teď jdeme k poslednímu jejímu synovi,
   // abychom přidali na konec seznamu
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// pokud syn neexistuje, vytvoříme ho
      t->son = create_tree(value);
      return t->son;
    }
}

Takto stavíme strom.

P.S. můj první článek, prosím, nehodnoťte příliš přísně

Zdroj: habr.com