Многие, наверное, пытались найти построение дерева общего вида, но поисковик находил только бинарные… Двоичное дерево поиска, обход двоичного дерева и многие другие алгоритмы.
Да, действительно, дерево общего вида нигде не используется, обход медленный, варианты использования небольшие.
Так вот, я задался этим вопросом и теперь поясню как все-таки дерево строится. Итак, в идеале структура дерева общего вида должна хранить три переменные:
struct Tnode {
int key;
struct Tnode *son;
struct Tnode *brother;
};
typedef struct Tnode Node;
Node *tree = NULL;
+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;
}
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;
}
}
К сожалению, не доступен сервер mySQL