Общи изгледи на дървото, реализация и не само

Много хора вероятно са се опитвали да намерят обща структура на дърво, но търсачката намираше само двоични... Двоично дърво за търсене, обход на двоично дърво и много други алгоритми.
Да, наистина, общото дърво не се използва никъде, обходът е бавен, а опциите за употреба са малки.

Е, зададох си този въпрос и сега ще обясня как всъщност се изгражда дървото. И така, идеалната структура на общото дърво трябва да съхранява три променливи:

• указател към старшия син
• указател към брат
• данни, които искате да съхранявате

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

Обявяваме указател за върха:

Node *tree = NULL;

Трябва предварително да се споразумеем как ще осъществим въвеждането на върховете, това не е двоично дърво, и всеки връх може да има неограничен брой синове.

• + 2 (или +ssbb 2) — вмъкване в дървото (за общо дърво пътят се задава със строка, където r е създаване на корен, s — преминаване към старшия син, b — преминаване към брат);

Пример:

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

В резултат ще получим такова дърво:

1
  2
    5
  3
    6
    7
  3

Първо ще създадем функция, която добавя връх, а именно заделя памет за върха и предава указателя за този връх (първоначално несвързана).

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

Също така е необходимо да се създаде функция, която обработва пътя на строката (+bs…). Всяки път започваме обхода от корена, ако той не е създаден, извеждаме NULL (не можем да направим нищо). Ако върха не съществува, трябва да го създадем. Преминаваме към функцията за създаване на дърво и получаваме указател за корена.

Важно е да се отбележи, че Node **tree предава структура, а не я копира. Това ни дава възможност да променяме, което не може да се направи в различие от обявяване на Node *tree.

Общо взето, трябва да намерим указател за върха, към който трябва да добавим син:

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

Така изграждаме дърво.

P.S. моята първа статия, така че моля не бъдете прекалено строг.

Източник: habr.com