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

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

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

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

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