Общий вид дерева, реализация и не только

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

Так вот, я задался этим вопросом и теперь поясню как все-таки дерево строится. Итак, в идеале структура дерева общего вида должна хранить три переменные:

• указатель на старшего сына
• указатель на брата
• данные, которые вы собираетесь хранить

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;
  Tree->max_value = 0;
  Tree->max_value_depth = 0;
  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. моя первая статья, так что прошу не судите строго

Автор: Валера

Источник