Общ изглед на дървото, изпълнение и др

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

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

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

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. първата ми статия, така че, моля, не съдете твърде строго

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