Сведение m-арного дерева к бинарному

Неформальный алгоритм:

1.В любом узле дерева отсекаются все ветви, кроме крайней левой, соответствующей старшим сыновьям.

2.Соединяется горизонтальными линиями все сыновья одного родителя.

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

Обходы бинарных деревьев и леса

Многие алгоритмы работы с бинарными деревьями основаны на последовательной (в определенном порядке) обработке узлов дерева. В этом случае говорят об обходе (прохождении) бинарного дерева. Такой обход порождает определенный порядок перечисления узлов бинарного дерева. Выделяют несколько стандартных вариантов обхода. Будем именовать их в зависимости от того порядка, в котором при этом посещаются корень дерева и узлы левого и правого поддеревьев.

Приведем рекурсивные процедуры КЛП-, ЛКП- и ЛПК-обходов, прямо соответствующие их рекурсивным определениям (операция обработки узла обозначена как «посетить (узел)»):

procedure обходКЛП (b: BTree); {прямой}

begin

if not Null (b) then

begin

посетить (Root (b));

обходКЛП (Left (b));

обходКЛП (Right (b));

end

end{обходКЛП};

procedure обходЛКП (b: BTree);{обратный}

begin

if not Null (b) then

begin

обходЛКП (Left (b));

посетить (Root (b));

обходЛКП (Right (b));

end

end{обходЛКП};

procedure обходЛПК (b: BTree);{концевой}

begin

if not Null (b) then

begin

обходЛПК (Left (b));

обходЛПК (Right (b));

посетить ( Root (b));

end

end{обходЛПК}

В литературе используется различная терминология при именовании видов обхода бинарного дерева. Перечислим наиболее популярные варианты терминологии (виды обходов перечислены во всех вариантах в одной и той же последовательности):

1) КЛП, ЛКП, ЛПК;

2) прямой, обратный, концевой;

3) прямой, симметричный, обратный;

4) сверху вниз, слева направо, снизу вверх6];

5) префиксный, инфиксный, постфиксный.

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

Иногда обход КЛП называют обходом в глубину. В варианте 2 названия обходам даны соответственно тому, что в КЛП-порядке корень посещается перед посещением узлов левого поддерева (прямой порядок), а в ЛКП-порядке корень посещается после обхода узлов левого поддерева (обратный порядок). В ЛПК-порядке корень посещается после обхода узлов левого и правого поддеревьев (концевой порядок).