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

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

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

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

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;
  //нулеви указатели към братя и деца, независима върха, която съхранява стойност
  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