Загальний вигляд дерева, реалізація і не лише

Багато хто, напевно, намагався знайти побудову дерева загального вигляду, але пошуковик знаходив тільки бінарні… Двійкове дерево пошуку, обхід двійкового дерева та багато інших алгоритмів.
Так, дійсно, дерево загального вигляду ніде не використовується, повільний обхід, варіанти використання невеликі.

Так ось, я поставив це питання і тепер поясню як все-таки дерево будується. Отже, в ідеалі структура дерева загального вигляду повинна зберігати три змінні:

• вказівник на старшого сина
• вказівник на брата
• дані, які ви збираєтесь зберігати

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

Джерело: habr.com