Предлагается использовать итерационный алгоритм прохождения по дереву. В качестве вспомогательного элемента используется стек. Дан код программы для начала. Так вот никак не разберусь с вводом дерева. (чюдом ввести получается, но что вел не понятно). А задание "Включение элемента в упорядоченное дерево на уровне листа." Как я понимаю дерево надо упорядочить, но как? С добавлением элемента вроде понятно. Помогите разобраться как вводить дерево и как упорядочить. | Код |
program ds_04;
uses ds_unit;
var t: ptree;
cnt: integer;
procedure cnt_node(t:ptree; var cnt:integer);
{ Входы: t - бинарное дерево;
Выходы: cnt - кол. элементов в дереве;
Гл. имена: ptree - тип указателя на дерево;
llink,rlink - поля связи элемента дерева;
Функция: Определение кол. эл-тов cnt в дереве t.}
const m=32; { Размер стека }
var st: array[1..m] of ptree; { Стек }
sp: integer; { Указатель стека }
p: ptree; { Указатель текущего эл-та }
empty: Boolean; { Индикатор "Стек пуст" }
begin
cnt:=0; sp:=0; p:=t;
repeat
while p<>nil do
begin
inc(sp); st[sp]:=p;
p:=p^.llink;
end;
empty:=sp=0;
if empty then exit;
p:=st[sp]; dec(sp);
inc(cnt);
p:=p^.rlink;
until false;
end; {cnt_node}
begin
gentree(t);
puttree(t);
cnt_node(t,cnt);
writeln('Количество элементов в дереве: ',cnt);
escwait;
end.
|
Модуль DS_UNIT | Код |
UNIT DS_UNIT;
interface
uses crt;
const m=7; { Размер блока памяти выделенного
для представления списков }
var info: array[1..m] of integer;{ Массив полей информации }
link: array[1..m] of integer;{ Массив полей связи для представления списков }
avail: integer; { Список свободного пр-ва }
type plist = ^list; { Тип указателя на список }
list = record { Тип элемента списка }
info: integer; { Поле информации }
link: plist; { поле связи элеменета списка}
end;
type ptree = ^tree; { Тип указателя на дерево }
tree = record { Тип элемента дерева }
llink,rlink: ptree; { Левое и правое поля связи элемента дерева }
info: char; {Поле информации элемента}
end; { дерева }
procedure escwait; { Приостановка выполнения программы }
procedure rdblock; { Ввод и }
procedure wrblock; { вывод состояния блока памяти }
{ для представления списков }
procedure rdlist(var lst: plist); { Ввод и }
procedure wrlist(lst: plist); { вывод списка lst }
procedure gentree(var t:ptree); { Ввод и }
procedure puttree(t:ptree); { вывод дерева t }
implementation
procedure escwait;
var fin: Boolean;
begin
writeln;
writeln('Нажмите Esc для продолжения программы.');
repeat
repeat until keypressed;
fin:=ord(readkey)=27;
until fin;
end; {escwait}
procedure rdblock;
var i: integer;
begin
writeln;
writeln('Ввод состояния блока памяти...');
writeln(' В строках Info и Link вводите по ',m:2,' чисел,');
writeln(' разделяя их пробелами...');
write(' ');
for i:=1 to m do write(i:3);
writeln; write('Info: ');
for i:=1 to m do read(info[i]);
write('Link: ');
for i:=1 to m do read(link[i]);
write('Avail: '); readln(avail); writeln;
end; {rdblock}
procedure wrblock;
var i: integer;
begin
writeln; writeln('Состояние блока памяти...');
write(' ');
for i:=1 to m do write(i:3);
writeln; write('Info: ');
for i:=1 to m do write(info[i]:3);
writeln;
write('Link: ');
for i:=1 to m do write(link[i]:3);
writeln; writeln('Avail: ',avail);
end; {wrblock}
procedure rdlist(var lst: plist);
var p,q,s: plist;
buf: integer;
function rdint(var buf:integer):Boolean;
begin
{$i-}
read(buf);
rdint:=IOResult=0;
{$i+}
end; {rdint}
begin
writeln;
writeln('Ввод списка... ');
writeln(' Вводите элементы списка (целые числа),');
writeln(' разделяя их пробелами. За последним');
writeln(' числом списка введите пробел, точку и Enter!');
q:=nil;
while rdint(buf) do
begin
new(s);
s^.info:=buf;
s^.link:=q;
q:=s;
end;
p:=nil;
while q<>nil do
begin
s:=q; q:=q^.link;
s^.link:=p; p:=s;
end;
lst:=p;
end; {rdlist}
procedure wrlist(lst: plist);
var p: plist;
begin
write('Список: [');
p:=lst;
while p<>nil do
begin
if p<>lst then write(',');
write(p^.info);
p:=p^.link;
end;
writeln(']');
end; {wrlist}
procedure gentree(var t:ptree);
procedure gent(var t:ptree);
var ch: char;
begin
read(ch);
if ch='.' then begin t:=nil; exit end;
new(t); t^.info:=ch;
gent(t^.llink);
gent(t^.rlink);
end; {gent}
begin
writeln;
writeln('Ввод дерева в точечной форме');
writeln(' ( например, AB..C.. )...');
gent(t);
readln;
writeln;
end; {gentree}
procedure puttree(t:ptree);
procedure putt(t:ptree);
begin
if t=nil then begin write('.'); exit end;
write(t^.info);
putt(t^.llink);
putt(t^.rlink);
end; {putt}
begin
writeln;
writeln('Дерево:');
putt(t);
writeln;
end; {puttree}
end.
|
|
[Pascal] Бинарные деревья 
Загрузка ...
