Celkový pohled na strom, implementace a další

Mnoho lidí se pravděpodobně snažilo najít obecnou konstrukci 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, skutečně, obecný strom se nikde nepoužívá, procházení je pomalé, případy použití jsou malé.

Tak jsem si položil tuto otázku a nyní vysvětlím, jak se strom staví. V ideálním případě by tedy obecná stromová struktura měla ukládat tři proměnné:

• ukazatel na nejstaršího syna
• ukazatel na bratra
• data, která budete ukládat

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

Pojďme deklarovat ukazatel na vrchol:

Node *tree = NULL;

Musíme se předem dohodnout, jak zadávat vrcholy, nejedná se o binární strom a každý vrchol může mít libovolný počet potomků.

• + 2 (nebo +ssbb 2) - vložení do stromu (u obecného stromu je cesta dána úsečkou, kde r je vytvoření kořene, s je přechod k nejstaršímu synovi, b je přechod k bratr);

Uvedu příklad:

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

Výsledkem bude strom jako tento:

1
  2
    5
  3
    6
    7
  3

Nejprve si vytvořme funkci, která přidá vrchol, totiž alokuje paměť pro vrchol a předá tomuto vrcholu (zpočátku s ničím nespojeným) ukazatel.

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

Musíte také vytvořit funkci, která zpracovává řetězec cesty (+bs...). Pokaždé, když spustíme procházení od kořene, pokud není vytvořen, vypíšeme NULL (nemůžeme nic dělat). Pokud žádný vrchol neexistuje, musíme jej vytvořit. Přejdeme k funkci create tree a získáme ukazatel na kořen.

Všimněte si, že strom Node** předává strukturu, nikoli ji kopíruje. To nám dává možnost změnit věci, které nemůžeme udělat pomocí deklarace *stromu Node.

Obecně musíme najít ukazatel na vrchol, ke kterému musíme 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); // создаем корень
            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;
    }
}

Takto stavíme strom.

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

Zdroj: www.habr.com