04.01.2020 09:08
MacKenlly 4 935 Источник
Многие, наверное, пытались найти построение дерева общего вида, но поисковик находил только бинарные… Двоичное дерево поиска, обход двоичного дерева и многие другие алгоритмы.
Да, действительно, дерево общего вида нигде не используется, обход медленный, варианты использования небольшие.

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

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

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] != '\0') {
        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. моя первая статья, так что прошу не судите строго

Комментарии (4)


  1. Fregl
    04.01.2020 12:47
    #21090026
    +1

    Не совсем понятно зачем хранить указатель на брата и сына… Не проще ли хранить указатели на родителя и список детей?


    1. S-e-n
      04.01.2020 15:46
      #21090508

      Указатель на брата и есть реализация односвязного списка детей, если я правильно понял. А указатель на старшего сына — указатель на первый элемент этого списка.

      Как в этой реализации искать родителей — вот что мне не понятно, потому что вообще-то много когда надо.


  1. Wyrd
    04.01.2020 20:05
    #21091112
    +1

    Мне кажется вы плохо искали
    1) https://developer.gnome.org/g lib/stable/glib-N-ary-Trees.html
    2) http://xmlsoft.org/html/libxml-tree.html
    3) https://github.com/search?l=C&q=n-ary+tree&type=Repositories
    4) https://github.com/search?l=C&q=graph+structure&type=Repositories
    5) ht
    tps://www.boost.org/doc/libs/1_65_1/doc/html/property_tree.html
    6) https://www.boost.org/doc/libs/1_66_0/libs/graph/doc/index.html


  1. mwambanatanga
    06.01.2020 10:20
    #21094994

    Поворчу:

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

    Node* это указатель на структуру, а Node** это указатель на указатель на структуру. В обоих случаях структура не копируется. В обоих случаях функция может изменять саму структуру. Разница в том, что в первом случае мы не можем изменить указатель на структуру. Вернее, в вызываемой функции изменить-то мы его можем, но вызвавший функцию код это изменение не увидит. Например, при удалении узла мы можем удалить структуру (освободить память), но не можем обнулить указатель на неё. А при передаче аргумента Node** мы можем изменять и структуру, и указатель на неё.