Представление и обработка деревьев общего вида

Модуль "Деревья" • урок 9 из 11 • ~7 минут

Что такое дерево общего вида?

До сих пор мы рассматривали двоичные деревья, где каждый узел имеет не более двух потомков (левого и правого). Однако в реальных задачах степени ветвления узлов могут быть произвольными и заранее неизвестными.

Классические примеры деревьев общего вида (сильно ветвящихся деревьев):

• Файловая система: Директория может содержать от 0 до нескольких тысяч файлов и поддиректорий.
• HTML DOM: Тег <body> может содержать десятки <div>, внутри которых произвольное число параграфов.
• Реестр Windows: Иерархическое хранилище параметров, где ключи содержат произвольное количество вложенных папок и значений.

Представление и обработка деревьев общего вида: проблема хранения

Как программно описать структуру узла node для такого дерева?

Вариант 1: Массив указателей.
Можно задать массив указателей на сыновей максимального размера: struct node *children[MAX_DEGREE]. Это приведет к гигантскому перерасходу памяти. Если MAX_DEGREE = 500, то для большинства папок, содержащих 2-3 файла, 497 указателей будут просто хранить NULL.

Вариант 2: Связный список потомков.
Внутри каждого узла хранить динамический список (или вектор): List* children. Это решает проблему памяти, но сильно усложняет структуру: дерево начинает зависеть от другой структуры данных (списка), что замедляет работу и делает обходы запутанными.

Преобразование LCRS (Левый сын - Правый брат)

Существует гениальный и крайне простой метод сведения любого дерева общего вида к двоичному дереву без потери информации. Этот метод называется Left-Child Right-Sibling (LCRS). В отечественной литературе его часто описывают правилом: "левое поддерево - старший сын, правое - следующий брат".

Суть алгоритма привязки указателей:

1. Указатель left указывает на первого (самого старшего/левого) ребенка данного узла.
2. Указатель right указывает на следующего родного брата (соседа справа на том же уровне).

Структура узла на C при этом остается точно такой же, как у обычного двоичного дерева:

struct TreeNode {
    int data;
    struct TreeNode* firstChild; // (left) Указатель на первого ребенка
    struct TreeNode* nextSibling; // (right) Указатель на соседа-брата
};

Пример преобразования

Допустим, у нас есть узел A, у которого три ребенка: B, C, D.

• A->firstChild указывает на B. (Потому что B - первый ребенок).
• У A нет братьев, поэтому A->nextSibling равно NULL.
• Кто следующий брат у B? Это C. Значит B->nextSibling указывает на C.
• Кто брат у C? Это D. C->nextSibling указывает на D.
• У D братьев больше нет, D->nextSibling = NULL.

Подобно теореме Бойма-Джакопини-Миллса в программировании, это преобразование имеет концептуальное значение: оно доказывает эквивалентность двух разновидностей деревьев. Любое N-арное дерево можно обработать стандартными алгоритмами для двоичных деревьев, просто изменив семантику ссылок left и right.

Обход преобразованного дерева

Поскольку физически мы имеем дело с двоичным деревом, мы можем применять стандартную рекурсию. Чтобы распечатать всех детей определенного узла, нам нужно спуститься на одного ребенка вниз, а затем итерироваться по всем "правым братьям":

void printChildren(struct TreeNode* parent) {
    if (parent == NULL || parent->firstChild == NULL) {
        printf("Детей нет\n");
        return;
    }
    
    // Переходим к первому ребенку
    struct TreeNode* current = parent->firstChild;
    
    // Идем по цепочке "братьев"
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->nextSibling;
    }
    printf("\n");
}