2015-02-27
509
0: (level:pList);
1: (atom:char);
end;
pTree=^Tree;
Tree=record
root:char;
left:pTree;
right:pTree;
end;
var p:pList; q:pTree;
procedure Input_to_List(var p:pList);
var c:char;
begin
if not eoln then
begin
read(c);
case c of
'(': begin
new(p); p^.R:=0;
Input_to_List(p^.level);
Input_to_List(p^.next);
end;
'a'..'z','+','-','*','/': begin
new(p); p^.R:=1;
p^.atom:=c;
Input_to_List(p^.next);
end;
')': p:=nil
end
end else p:=nil
end;
procedure Print_of_List(p:pList);
var q:pList;
begin
if p<>nil then
begin
if p^.R=1 then write(p^.atom)
else
begin
write('(');
q:=p^.level;
while q<>nil do
begin
Print_of_List(q);
q:=q^.next
end;
write(')');
end
end
end;
function CutHead(var p:pList):pList;
var q:pList;
begin
q:=p^.level;
p^.level:=q^.next;
q^.next:=nil;
CutHead:=q
end;
function List_to_Tree(p:pList):pTree;
var q:pTree;
begin
new(q);
if p^.R=1 then
begin
q^.root:=p^.atom;
q^.left:=nil;
q^.right:=nil
end else
begin
q^.left:=List_to_Tree(CutHead(p));
q^.root:=CutHead(p)^.atom;
q^.right:=List_to_Tree(CutHead(p));
end;
List_to_Tree:=q
end;
procedure Print_of_Tree(p:pTree);
begin
if p<>nil then
begin
if (p^.left<>nil)and(p^.right<>nil)then write('(');
Print_of_Tree(p^.left);
write(p^.root);
Print_of_Tree(p^.right);
if (p^.left<>nil)and(p^.right<>nil)then write(')');
end;
end;
Procedure AddHead(var p:pList; q:pList);
begin
q^.next:=p^.level;
p^.level:=q
end;
function Tree_to_List(p:pTree):pList;
var ps:pList; pright,pleft,proot:pTree;
begin
new(ps);
ps^.next:=nil;
if (p^.left=nil) and (p^.right=nil) then
begin
ps^.R:=1;
ps^.atom:=p^.root;
dispose(p)
end else
begin
ps^.R:=0;
ps^.level:=nil;
{Расчленение p на pleft, pright, proot}
pright:=p^.right;
pleft:=p^.left;
p^.right:=nil;
p^.left:=nil;
proot:=p;
AddHead(ps,Tree_to_List(pright));
AddHead(ps,Tree_to_List(proot));
AddHead(ps,Tree_to_List(pleft));
end;
Tree_to_List:=ps
end;
Begin
ClrScr;
Input_to_List(p);
Print_of_List(p);
writeln;
q:=List_to_Tree(p);
print_of_Tree(q);
writeln;
p:=Tree_to_List(q);
Print_of_List(p);
writeln;
repeat until keypressed
End.
Дерево двоичного поиска
Пусть тип данных Inf допускает порядок (то есть данные этого типа можно сравнивать на «больше» и «меньше»).
Дерево двоичного поиска – это двоичное дерево, каждое поддерево которого обладает следующим свойством: информационные части всех узлов, находящихся в левом поддереве, меньше информационной части корня, а информационные части всех узлов, находящихся в правом поддереве больше информационной части корня.
Операции: Создать, Добавить, Найти, Обход.
Пример: 22,10,3,5,13,26,18,19,17,2,4,7,...
Реализация операций
Добавить (р:^Эл,i:Inf)
Если p=NIL то NEW(p);p^.кор=i;p^.лев=NIL;p^.прав=NIL
иначе
если i<p^.кор > то Добавить (p^.лев,i),
иначе Добавить (p^.прав,i)
Задачи
1. Заполнить дерево двоичного поиска из файла?
2. Найти элемент с заданной информационной частью в дереве двоичного поиска?
3. Что дает ЛКП обход дерева двоичного поиска?
