04.06.2015, 02:57
|
Прохожий
|
|
Регистрация: 30.04.2015
Сообщения: 8
Версия Delphi: Delphi 7
Репутация: 10
|
|
Выполнить симметричную прошивку бинарного дерева поиска
Выполнить симметричную прошивку бинарного дерева поиска. Обойти его согласно симметричному порядку следования элементов.
У меня есть часть кода для этого,но не знаю как это все сделать в работающем виде. Надеюсь вы поможете
Код:
Узел прошитого бинарного дерева имеет иную структуру
Type ptr = ^node;
node = record
info : integer; {Информационное поле}
ltag, rtag : boolean; {Тэги прошивочных нитей}
left, right : pt; {Указатели на левое и правое поддеревья}
end;
Логические поля в прошитом дереве могут принимать следующие значения.
1. ltag=true, следовательно, left представляет собой обычную связь.
2. ltag=false, следовательно, left указывает на узел-предшественник.
3. rtag=true, следовательно, right представляет собой обычную связь.
4. rtag=false, следовательно, right указывает на узел-преемник.
Программный код процедур симметричного обхода sim_print и прошивки правых связей rightsew будет выглядеть так:
procedure sim_print(var x:pt);
procedure rightsew( var p:pt);
begin
if y <> nil then
begin
if y^.right=nil then
begin
y^.rtag := false;
y^.right := p;
end
else y^.rtag := true;
end;
y:=p;
end;
begin
if x<> nil then
begin
sim_print(x^.left);
rightsew(x);
sim_print(x^.right);
end;
1. Переход к корню дерева ( p := HEAD^.left ).
2. До тех пор, пока p^.left<>nil, повторять: p := p^.left, то есть идти по левой ветви до самого левого узла.
3. Обработка узла p, например, печать p^.info.
4. Если p^.rtag равен false, то p := p^.right и переход к шагу 3 ( к преемнику). Иначе p:= p^.right и переход к шагу 2.
Алгоритм заканчивает работу, когда p станет равным HEAD.
|