Паскаль (I семестр) / K02-172 / 06 / tree

(*
(c) 2005 Dima Zolotukhin aka 'Zlogic' <zlogic@gmail.com>
Redistributable under GNU GPL license
*)
program tree;
uses graph;
type
tdata = integer;
pnode = ^node;
node = record
data:tdata;
pleft,pright:pnode;
end;
tmessage = string[70];
CONST
BOXHEIGHT = 20;
BOXWIDTH = 20;
TEXTHEIGHT = 7;
BOXDISTANCE = 60;

function get_data(msg:tmessage):tdata;
var
tmp:tdata;
begin
write(msg,'> ');
readln(tmp);
get_data:=tmp;
end;

procedure print_menu;
begin
writeln;
writeln('<< Њ…Ќћ Ѓ€ЌЂђЌЋѓЋ „…ђ…‚Ђ >>');
writeln('1 „®Ў ўЁвм н«Ґ¬Ґ­в ў ¤ҐаҐў®');
writeln('2 ђ бЇҐз в вм н«Ґ¬Ґ­вл ў ०Ё¬Ґ Љ‹Џ');
writeln('3 ђ бЇҐз в вм н«Ґ¬Ґ­вл ў ०Ё¬Ґ ‹ЉЏ');
writeln('4 ‚뢥бвЁ Є®«ЁзҐбвў® ўҐаиЁ­ ­ зЁ­ п б § ¤ ­­®©');
writeln('5 ‚뢥бвЁ Ј«гЎЁ­г ¤ҐаҐў ');
writeln('6 Ќ ©вЁ н«Ґ¬Ґ­в');
writeln('7 ‚뢥бвЁ ¤ҐаҐў® ­  нЄа ­ ў Ја дЁзҐбЄ®¬ ўЁ¤Ґ');
writeln('8 “¤ «Ґ­ЁҐ н«Ґ¬Ґ­в ');
writeln('9 ‚›•Ћ„');
end;
procedure add_element(var root:pnode;data_to_add:tdata);
begin
if(root=NIL)then{Ґб«Ё ­®¤  Їгбв п}
begin
new(root);{¤®Ў ў«пҐ¬ н«Ґ¬Ґ­в}
root^.pleft:=NIL;
root^.pright:=NIL;
root^.data:=data_to_add;
end
else{Ё­ зҐ}
begin
if(data_to_add<root^.data)then{Ґб«Ё зЁб«® < ­®¤л}
add_element(root^.pleft,data_to_add);{¤®Ў ў«пҐ¬ ­ «Ґў®}
if(data_to_add>root^.data)then{Ґб«Ё зЁб«® > ­®¤л}
add_element(root^.pright,data_to_add);{¤® ў«пҐ¬ ­ Їа ў®}
end;
end;

procedure print_klp(root:pnode);
begin
if(root<>NIL)then{Ґб«Ё ­®¤  бгйбвўгҐв}
begin
writeln(root^.data:4);{ўлў®¤Ё¬ ҐҐ §­ зҐ­ЁҐ}
print_klp(root^.pleft);{ўлў®¤Ё¬ ४габЁў­® «Ґўго ўҐвЄг}
print_klp(root^.pright);{ўлў®¤Ё¬ ४габЁў­® Їа ўго ўҐвЄг}
end;
end;
procedure print_lkp(root:pnode);
begin
if(root<>NIL)then{Ґб«Ё ­®¤  бгйбвўгҐв}
begin
print_lkp(root^.pleft);{ўлў®¤Ё¬ ४габЁў­® «Ґўго ўҐвЄг}
writeln(root^.data:4);{ўлў®¤Ё¬ ҐҐ §­ зҐ­ЁҐ}
print_lkp(root^.pright);{ўлў®¤Ё¬ ४габЁў­® Їа ўго ўҐвЄг}
end;
end;

function find_node(root:pnode;data_to_find:tdata):pnode;
begin
if(root^.data<>data_to_find) and (root<>NIL)then
begin
if(data_to_find<root^.data)then
find_node:=find_node(root^.pleft,data_to_find)
else
find_node:=find_node(root^.pright,data_to_find);
end
else
find_node:=root;
end;

function count_nodes(root:pnode):byte;
var
found:pnode;
begin
if(root<>NIL)then
count_nodes:=count_nodes(root^.pleft)+count_nodes(root^.pright)+1
else
count_nodes:=0;
end;

function max(x,y:tdata):tdata;
begin
if(x>y)then
max:=x
else
max:=y;
end;

function count_depth(root:pnode):integer;
var
left_depth,right_depth:integer;
begin
if(root<>NIL)then
count_depth:=max(count_depth(root^.pleft),count_depth(root^.pright))+1
else
count_depth:=0;
end;

function count_nmiddle(root:pnode;leftmargin,rightmargin:integer):integer;
var
nodes_left,nodes_right:integer;
begin
nodes_left:=count_nodes(root^.pleft);{бзЁв Ґ¬ ўҐиЁ­л}
nodes_right:=count_nodes(root^.pright);
if(nodes_left<>0)and(nodes_right<>0)then{бзЁв Ґ¬ бҐаҐ¤Ё­г}
count_nmiddle:=leftmargin+round((rightmargin-leftmargin)*
(nodes_left/(nodes_right+nodes_left)))
else
begin
if(nodes_left=0)then
count_nmiddle:=leftmargin+round((rightmargin-leftmargin)*
(1/(1+nodes_right)));
if(nodes_right=0)then
count_nmiddle:=leftmargin+round((rightmargin-leftmargin)*
(nodes_left/(1+nodes_left)));
if(nodes_left=0)and(nodes_right=0)then
count_nmiddle:=(leftmargin+rightmargin) div 2;
end;
end;

procedure render_node(root:pnode;topmargin,leftmargin,rightmargin,nodeheight:integer);
var
middle,nmiddle:integer;
rmiddle,lmiddle:integer;
node_data:string[6];
begin
nmiddle:=count_nmiddle(root,leftmargin,rightmargin);

rectangle(nmiddle-BOXWIDTH,topmargin,nmiddle+BOXWIDTH,topmargin+BOXHEIGHT);{аЁб㥬 Є®а®ЎЄг}
str(root^.data:5,node_data);
outtextxy(nmiddle-BOXWIDTH,topmargin+TEXTHEIGHT,node_data);{аЁб㥬 ⥪бв}

if(root^.pleft<>NIL)then{аЁб㥬 «Ґўго ўҐвЄг}
begin
lmiddle:=count_nmiddle(root^.pleft,leftmargin,nmiddle);
line(nmiddle,topmargin+BOXHEIGHT,lmiddle,topmargin+nodeheight);
render_node(root^.pleft,topmargin+nodeheight,leftmargin,nmiddle,nodeheight);
end;
if(root^.pright<>NIL)then{аЁб㥬 Їа ўго ўҐвЄг}
begin
rmiddle:=count_nmiddle(root^.pright,nmiddle,rightmargin);
line(nmiddle,topmargin+BOXHEIGHT,rmiddle,topmargin+nodeheight);
render_node(root^.pright,topmargin+nodeheight,nmiddle,rightmargin,nodeheight);
end;
end;
procedure render_tree(root:pnode);
var
grdriver:integer;
grmode:integer;
errcode:integer;
depth:integer;
begin
grdriver:=detect;
initgraph(grdriver, grmode,'');
errcode := graphresult;
if errcode = grok then
begin
outtextxy(0,0,'Ќ ¦¬ЁвҐ ENTER ¤«п ўл室 ');
depth:=count_depth(root)-1;
if(depth=0)then
depth:=1;
render_node(root,15,0,getmaxx,((getmaxy-BOXDISTANCE) div depth));{аЁб㥬 ¤ҐаҐў®}
readln;
closegraph;
end
else
writeln('Graphics error:', grapherrormsg(errcode));
end;

procedure special_del(var root,next:pnode);
begin
if(next^.pright<>NIL)then
special_del(root,next^.pright)
else
begin
root^.data:=next^.data;
root:=next;
next:=next^.pleft;
end;
end;

function delete_element(var root:pnode;data_to_delete:tdata):boolean;
var
temp_node:pnode;
temp_data:tdata;
begin
delete_element:=true;
if(root<>NIL)then{Ґб«Ё н«-в ­ ©¤Ґ­}
begin
if(data_to_delete<root^.data)then{Ё¤Ґ¬ ­ «Ґў®}
delete_element:=delete_element(root^.pleft,data_to_delete);
if(data_to_delete>root^.data)then{Ё¤Ґ¬ ­ Їа ў®}
delete_element:=delete_element(root^.pright,data_to_delete);
if(data_to_delete=root^.data)then{Ґб«Ё ¬л ­  г¤ «пҐ¬®¬ н«Ґ¬Ґ­вҐ}
begin
temp_node:=root;
if(temp_node^.pright=NIL)then{Ґб«Ё Єа ©­Ё© Їа ўл©}
root:=temp_node^.pleft;
if(temp_node^.pleft=NIL)then{Ґб«Ё Єа ©­Ё© «Ґўл©}
root:=temp_node^.pright;
if(temp_node^.pright<>NIL)and(temp_node^.pleft<>NIL)then{Ґб«Ё ­Ґ Єа ©­Ё©}
special_del(temp_node,temp_node^.pleft);{४габЁў­® ¤Ґ« Ґ¬ бЇҐж-г¤ «Ґ­ЁҐ}
dispose(temp_node);{§ Ўлў Ґ¬}
end;
end
else{Ё­ зҐ}
delete_element:=false;{®иЁЎЄ }
end;

var
exit:boolean;
response:integer;
root:pnode;
found_node:pnode;
data_to_add:tdata;
begin
exit:=false;
root:=NIL;
while not exit do{Ї®Є  ­Ґ ­г¦­® ўл©вЁ}
begin
print_menu;{ўлў®¤Ё¬ ¬Ґ­о}
writeln;
response:=get_data('‚лЎҐаЁвҐ Їг­Єв ¬Ґ­о');{Ї®«гз Ґ¬ ўлЎ®а Ї®«м§®ў вҐ«п}
case response of{®Ўа Ў влў Ґ¬ ўлЎ®а}
1:begin
data_to_add:=get_data('‚ўҐ¤ЁвҐ, зв® ­г¦­® ¤®Ў ўЁвм');
if(find_node(root,data_to_add)=NIL)then{Ґб«Ё в Є®Ј® н«Ґ¬Ґ­в  ­Ґвг}
add_element(root,data_to_add){¤®Ў ў«Ґ­ЁҐ н«Ґ¬Ґ­в }
else{Ё­ зҐ}
writeln('<< ’ЂЉЋ‰ ќ‹…Њ…Ќ’ “†… …‘’њ >>');{®иЁЎЄ }
end;
2:if(root<>NIL)then
print_klp(root){а бЇҐз вЄ  Є«Ї}
else
writeln('<< „…ђ…‚Ћ Џ“‘’Ћ… >>');
3:if(root<>NIL)then
print_lkp(root){а бЇҐз «Є  «ЄЇ}
else
writeln('<< „…ђ…‚Ћ Џ“‘’Ћ… >>');
4:begin
found_node:=find_node(root,get_data('‚ўҐ¤ЁвҐ, Ї®б«Ґ Є Є®Ј® н«Ґ¬Ґ­в  бзЁв вм ўҐаиЁ­л'));{ЁйҐ¬ н«-в}
if(found_node<>NIL)then{Ґб«Ё ­ ©¤Ґ­}
writeln('‚ ¤ҐаҐўҐ § ¤ ­­®Ј® н«Ґ¬Ґ­в  ',count_nodes(found_node),' ўҐаиЁ­'){бзЁв Ґ¬ ўҐаиЁ­л}
else{Ё­ зҐ}
writeln('<< ќ‹…Њ…Ќ’ Ќ… ЌЂ‰„…Ќ >>');{®иЁЎЄ }
end;
5:writeln('ѓ«гЎЁ­  ¤ҐаҐў  ',count_depth(root));{а бзҐв Ј«гЎЁ­л ¤ҐаҐў }
6:if(find_node(root,get_data('‚ўҐ¤ЁвҐ, зв® ­г¦­® ­ ©вЁ'))<>NIL)then{Ї®ЁбЄ н«Ґ¬Ґ­в }
writeln('<<ќ‹…Њ…Ќ’ ЌЂ‰„…Ќ>>')
else
writeln('<<ќ‹…Њ…Ќ’ Ќ… ЌЂ‰„…Ќ>>');
7:if(root<>NIL)then
render_tree(root){Ја дЁзҐбЄЁ© ўлў®¤ ¤ҐаҐў  ­  нЄа ­}
else
writeln('<< „…ђ…‚Ћ Џ“‘’Ћ… >>');
8:if not(delete_element(root,get_data('‚ўҐ¤ЁвҐ, Є Є®© н«Ґ¬Ґ­в г¤ «Ёвм')))then{Ґб«Ё ­Ґ г¤ «Ґ­}
writeln('<< ќ‹…Њ…Ќ’ Ќ… ЌЂ‰„…Ќ >>');{®иЁЎЄ }
9:exit:=true;{ўл室}
end;
end;
end.