Сведение 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 названия обходам даны соответственно тому, что в КЛП-порядке корень посещается перед посещением узлов левого поддерева (прямой порядок), а в ЛКП-порядке корень посещается после обхода узлов левого поддерева (обратный порядок). В ЛПК-порядке корень посещается после обхода узлов левого и правого поддеревьев (концевой порядок).
Нерекурсивные процедуры обхода бинарных деревьев
В качестве примера приведем алгоритм для прямого нерекурсивного обхода дерева.
|
|
|
1.В качестве очередной вершины взять корень дерева. Перейти к п.2.
2.Произвести обработку очередной вершины в соответствии с задачей. Перейти к п.3.
3.а) Если очередная вершина имеет обе ветви, то в качестве новой очередной вершины, выбрать ту вершину, на которую ссылается левая ветвь, а вершину на которую ссылается правая ветвь, поставить в очередь. Перейти к п.2.
б) Если очередная вершина является конечной, то в качестве новой очередной вершины выбрать вершину из очереди, если она не пуста, и перейти к п.2.; если очередь пуста, то это означает, что обход всего дерева окончен, перейти к п.4.
в) Если очередная вершина имеет только одну ветвь, то в качестве новой очередной вершины, выбрать ту вершину, на которую эта ветвь указывает, перейти к п.2.
4. Конец алгоритма.
Обходы леса
Следуя естественному соответствию между бинарными деревьями и лесами, можно на основе КЛП-, ЛКП- и ЛПК-обходов бинарного дерева получить три соответствующих порядка прохождения леса (и, следовательно, произвольного дерева).
Прямой порядок:
а) посетить корень первого дерева;
б) пройти поддеревья первого дерева (в прямом порядке);
в) пройти оставшиеся деревья (в прямом порядке).
Обратный порядок:
а) пройти поддеревья первого дерева (в обратном порядке);
б) посетить корень первого дерева;
в) пройти оставшиеся деревья (в обратном порядке).
Концевой порядок:
а) пройти поддеревья первого дерева (в концевом порядке);
б) пройти оставшиеся деревья (в концевом порядке);
в) посетить корень первого дерева.
Дата добавления: 2018-05-02; просмотров: 625; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!