h1

Операции создания, изменения, обхода двумя способами двоичного дерева

Декабрь 28, 2009

Программа на языке Pascal, работающая с деревьями. Реализовано: создание и изменение двоичного дерева,  нахождение длины дерева, обход дерева во внутреннем порядке и обход дерева в прямом порядке. Деревья представлены с помощью указателей.

Исходный код:

uses crt;
type node=record
name: string;
left, right: pointer;
end;
var
n,l,r,dl,max:integer;
pnt_s,current_s,root: pointer;
pnt,current:^node;
s: string;
procedure node_search (pnt_s:pointer; var current_s:pointer);
{Poisk uzla po soderzhimomu}
var
pnt_n:^node;
begin
pnt_n:=pnt_s; writeln(pnt_n^.name);
if not (pnt_n^.name=s) then
begin
if pnt_n^.left <> nil then
node_search (pnt_n^.left,current_s);
if pnt_n^.right <> nil then
node_search (pnt_n^.right,current_s);
end
else current_s:=pnt_n;
end;

procedure node_list (pnt_s:pointer);
{Vyvod spiska vseh uzlov dereva}
var
pnt_n:^node;
begin
pnt_n:=pnt_s; writeln(pnt_n^.name);
if pnt_n^.left <> nil then node_list (pnt_n^.left);
if pnt_n^.right <> nil then node_list (pnt_n^.right);
end;

procedure node_list1 (pnt_s:pointer);
{Vyvod spiska vseh uzlov dereva}
var
pnt_n:^node;
begin
pnt_n:=pnt_s;
if pnt_n<>nil then
begin
node_list1(pnt_n^.left);
write(‘ ‘,pnt_n^.name);
node_list1(pnt_n^.right);
end;
end;

procedure node_list2 (pnt_s:pointer);
{Vyvod spiska vseh uzlov dereva v pryamom poryadke}
var
pnt_n:^node;
begin
pnt_n:=pnt_s; write(‘ ‘,pnt_n^.name);
if pnt_n^.left <> nil then node_list2 (pnt_n^.left);
if pnt_n^.right <> nil then node_list2 (pnt_n^.right);
end;

procedure node_length (pnt_s:pointer);
var pnt_n,l,r:^node;
begin
pnt_n:=pnt_s;
if (pnt_n^.left<>nil) and (pnt_n^.right<>nil) then
begin
l:=pnt_n^.left;
r:=pnt_n^.right;
node_length(l);
node_length(r);
max:=max+1;
end;
if (pnt_n^.left<>nil) and (pnt_n^.right<>nil) then max:=max-1;
if (pnt_n^.left<>nil) or (pnt_n^.right<>nil) then max:=max+1;

end;

procedure node_dispose (pnt_s:pointer);
{Udalenie uzla i vseh ego potomkov v dereve}
var
pnt_n:^node;
begin
if pnt_s <> nil then
begin
pnt_n:=pnt_s; writeln(pnt_n^.name);
if pnt_n^.left <> nil then
node_dispose (pnt_n^.left);
if pnt_n^.right <> nil then
node_dispose (pnt_n^.right);
dispose(pnt_n);
end
end;

begin
clrscr;
new(current);root:=current;
current^.name:=’root’;
current^.left:=nil;
current^.right:=nil;
repeat
writeln(‘tekuwij uzel -‘,current^.name);
writeln(‘1-prisvoit imja levomu potomoku’);
writeln(‘2-prisvoit imja pravomu potomku’);
writeln(‘3-sdelat uzel tekuwim’);
writeln(‘4-vyvesti spisok vseh uzlov’);
writeln(‘5-udalit potomkov tekuwego uzla’);
writeln(‘6-vivesti dliny dereva’);
writeln(‘7-obhod dereva v vnytrennem poryadke’);
writeln(‘8-vyvesti spisok vseh uzlov v pryamom poryadke’);
writeln(‘0-vihod’);
read(n);
if n=1 then
begin {Sozdanie levogo potomka}
if current^.left= nil then new(pnt)
else pnt:= current^.left;
writeln(‘left ?’);
readln;
read(s);
pnt^.name:=s;
pnt^.left:=nil;
pnt^.right:=nil;
current^.left:= pnt;
end;
if n=2 then
begin {Sozdanie pravogo potomka}
if current^.right= nil then new(pnt)
else pnt:= current^.right;
writeln(‘right ?’);
readln;
read(s);
pnt^.name:=s;
pnt^.left:=nil;
pnt^.right:=nil;
current^.right:= pnt;
end;
if n=3 then
begin {Poisk uzla}
writeln(‘name ?’);
readln;
read(s);
current_s:=nil; pnt_s:=root;
node_search (pnt_s, current_s);
if current_s <> nil then current:=current_s;
end;
if n=4 then
begin {Vyvod spiska uzlov}
pnt_s:=root;
node_list(pnt_s);
end;
if n=5 then
begin {Udalenie poddereva}
writeln(‘l,r ?’);
readln;
read(s);
if (s=’l’) then
begin {Udalenie levogo poddereva}
pnt_s:=current^.left;
current^.left:=nil;
node_dispose(pnt_s);
end
else
begin {Udalenie pravogo poddereva}
pnt_s:=current^.right;
current^.right:=nil;
node_dispose(pnt_s);
end;
end;
writeln(current^.name);
if n=6 then
begin {poisk dlini}
max:=1;
pnt_s:=current;
node_length(pnt_s);
writeln(‘dlina dereva ‘,max);
end;
if n=7 then
begin {Vyvod spiska uzlov}
writeln(‘obhod dereva v vnytrennem poryadke:’);
pnt_s:=root;
node_list1(pnt_s);
writeln; writeln;
end;
if n=8 then
begin {Vyvod spiska uzlov v pryamom poryadke}
writeln(‘vivod uzlov v pryamom poryadke’);
pnt_s:=root;
node_list2(pnt_s);
writeln;
writeln;
end;
until n=0;
end.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: