Двоичное дерево. Физическое представление. Прошивка

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

Двоичное дерево. Физическое представление. Прошивка: зачем она нужна

В любом двоичном дереве, состоящем из N узлов, содержится ровно 2N ссылок (по две в каждом узле). Из них N-1 ссылок указывают на реальных детей, а оставшиеся N+1 ссылок равны NULL (это пустые концы у листьев).

Это означает, что больше половины всей адресной памяти дерева простаивает впустую! Алан Перлис и Джозеф Торнтон придумали идею: а что если использовать эти пустые указатели NULL для хранения ссылок на узлы, к которым алгоритм должен перейти дальше (при симметричном обходе)? Такие ссылки назвали нитями (threads).

Изменение структуры узла

Если мы запишем в правый указатель листа адрес следующего узла, как программа поймет - это настоящий сын или нить обхода? Для этого в структуру узла добавляют два булевых флага (по одному биту):

#include <stdbool.h>

struct ThreadedNode {
    int data;
    struct ThreadedNode *left;
    struct ThreadedNode *right;
    bool lthread; // true, если left - это нить (указывает на предка)
    bool rthread; // true, если right - это нить (указывает на потомка)
};

Примечание: В языке C эти булевы флаги можно упаковать в битовые поля, чтобы структура не занимала лишней памяти.

Как строятся нити (на примере симметричного обхода ЛКП)

Если левый указатель узла равен NULL, мы делаем его нитью и направляем на предыдущий узел (предшественник) при симметричном обходе.

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

На схеме выше симметричный обход дает последовательность: 1 -> 3 -> 4 -> 5 -> 7. Как мы видим, от листа 1 идет правая нить к узлу 3. От листа 4 идет правая нить к корню 5. Самый левый указатель и самый правый указатель остаются NULL (хотя в некоторых реализациях их закольцовывают на фиктивный узел).

Алгоритм обхода без рекурсии

Обход прошитого дерева сводится к простому циклу while:

1. Спускаемся по левым ссылкам до упора (в самый левый узел).
2. Печатаем узел.
3. Если правая ссылка является нитью (rthread == true), просто переходим по ней и сразу печатаем (поднимаемся наверх).
4. Если правая ссылка является настоящим сыном (rthread == false), переходим по ней в правое поддерево и снова спускаемся влево до упора.
5. Повторяем, пока указатель не станет NULL.