Построение полного двоичного дерева

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

Построение полного двоичного дерева состоит из нескольких этапов. Проходя к какой-либо вершине, мы должны запоминать указатель пути. Для этой цели удобно использовать стек. Остановка алгоритма – создание самого правого пути.

П р и м е р. Написать программу построения полного двоичного дерева в динамической памяти из 4-х уровней (рис. 14.4 и 14.5).

1 а б

Рис. 14.4. Полное бинарное дерево (а) и неполное бинарное дерево из 4-х уровней (б)

Рис. 14.5. Дерево из четырех уровней

{Построение полного двоичного дерева}

const n=4; {сколько уровней}

type ptree=^ttree;

ttree=record {опишем запись для создания дерева}

dat: integer;

l, r: ptree

End;

Var

kor,v,t:ptree; {kor -корень, v,t - вспомогательные,

i,j:I nteger; i - значение инф. поля очередной

вершины, j - № уровня}

Type

pstack=^element; {Опишем запись для стека. Информац.

element=record поля имеют тип ptree - дерева}

m:ptree;

next:pstack

End;

var p,h:pstack;

procedure putstack(n:ptree);

Begin

new(p);

p^.m:=n;

p^.next:=h;

h:=p

End;

procedure getstack(var n:ptree);

Begin

p:=h;

n:=p^.m;

h:=p^. next;