Обход прошитого дерева

Элемент бинарного дерева содержит две ссылки: на левое и правое поддерево. Чтобы обойти обычное бинарное дерево требуется алгоритм, использующий стек, т.к. нижележащие деревья не содержат информации о своих предках. Поэтому, чтобы вернуться в узел, в котором возможно ветвление, мы помещаем его в стек. Если же процедура обхода не находит следующего элемента, то мы берем его из стека и повторяем её.
Учитывая то, что многие узлы могут иметь одну из ссылок незанятыми, можно прийти к выводу, что дерево можно представить более эффективно в памяти и сделать обход его более быстрым.
А. Дж. Перлис и Ч. Торнтон предложили использовать эти незанятые ссылки в качестве "нитей", которые связаны с остальными частями дерева. Дерево с такими связями называют "прошитым бинарным деревом".

Прошитое дерево. Из книги Кнут Д. "Искусство программирования."

Чтобы отличать нити от обычных ссылок используются два бита, характеризующие тип связи. Для определенности, если бит RS = 0, то правая связь обычная, если RS = 1, то это связь типа "нить". Аналогично для бита LS. В памяти оба бита естественно представимы в виде одного слова.
Для удобных реализаций алгоритма обхода прошитого дерева вводится ограничение на дерево:

1. корневой элемент имеет правую ссылку на само себя, 
2. построение дерево начинается только влево от корня. 

Корень в таком случае называют "заголовком списка". Для ясности можно делать его значение равным None или Null или любым другим значением, таким которое явно не встречается в элементах дерева, чтобы точно отличать его от остальных элементов дерева и избавить себя от этого искусственного ограничения на построение дерева.

Пример организации прошитого дерева с учетом всех ограничений.

Реализация на Питоне (в виде пакета) включает в себя

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

Скачивайте.