POISK_W_SPISKE(F,EL,N); writeln(' N = ',N);
writeln;
write(' Отсортирорванный дек 1: ');
SORTSPISOK (F); VIVOD_SPISOK(F); writeln;
write(' КОНЕЦ РАБОТЫ !');readln;
end.
program TREE; uses crt;
label 1,2,3;
type SS = ^ZVENO;
ZVENO = record
K: integer;
left, right: SS;
end;
var KOL,R,I,J,W: integer; Y:real; DER,EL, q,x: SS; O:char;
{KOL-число элементов дерева; DER-ссылка на корень дерева}
procedure PRINTTREE (Z: SS; X: integer; var Y: real);
var i: integer;
begin
¦ Y:=(x-1)/5-1;
¦ if Z <> nil then
¦ begin
¦ ¦ PRINTTREE(Z^.right, X+5,Y);
¦ ¦ for i:=1 to X do write(' ');
¦ ¦ writeln(Z^.k);
¦ ¦ PRINTTREE(Z^.left, X+5,Y);
¦ end;
{ РЕКУРСИВНАЯ ФУНКЦИЯ ПОСТРОЕНИЯ ДЕРЕВА}
function FORMIRTREE (N: integer): SS;
var Z: SS; NL, NR: integer;
¦ if N = 0 then Z:= nil {пустое дерево}
¦ else
¦ ¦ NL:= N div 2; NR:= N-Nl-1; new(Z);
¦ ¦ write('Введите вершину'); readln(Z^.k);
¦ ¦ Z^.left:= FORMIRTREE (NL);
¦ ¦ Z^.right:= FORMIRTREE (NR);
¦ FORMIRTREE:= Z; {запоминание ссылки на корень дерева}
procedure POISK(S: SS; ZNACH: integer; var ELEM: SS);
¦ if S <> nil then
¦ if S^.k = ZNACH then ELEM:= S
¦ ¦ POISK(S^.left,ZNACH,ELEM);
¦ ¦ POISK(S^.right,ZNACH,ELEM);
procedure POISK_v_OD(S: SS; ZNACH: integer; var ELEM: SS);
¦ if (s^.k >=0) and (s^.k<=50) then
¦ begin write(s^.k:3);i:=i+1;end;
¦ if S^.k = ZNACH then begin j:=1;ELEM:= S end
¦ else if s<> nil then
¦ ¦ POISK_v_OD(S^.left,ZNACH,ELEM);
¦ ¦ if j=0 then
¦ ¦ POISK_v_OD(S^.right,ZNACH,ELEM);
procedure VSTAVKA (S, S1, S2: SS);
¦ if S^.left = S1 then
¦ ¦ S^.left:= S2;
¦ ¦ S2^.left:= S1;
¦ ¦ S2^.right:= nil;
¦ end
else
S^.right:= S2;
¦ ¦ S2^.right:= S1;
¦ ¦ s2^.left:= nil;
{ ОСНОВНАЯ ПРОГРАММА }
1:clrscr; gotoxy(20,2);write('ДЕРЕВЬЯ ОБЩЕГО ВИДА ');
writeln; writeln;
write(' Введите число элементов дерева: ');
y:= 0; {число уровней дерева*}
readln (KOL); DER:= FORMIRTREE (KOL); readln;clrscr;
writeln;writeln(' Д Е Р Е В О:'); writeln;
PRINTTREE (DER,5,y); writeln;
writeln(' Всего', y:3:0,' уровня(ей) дерева');
write(' Еще?(y/n): ');readln(O);
if O='y' then goto 1;
2: clrscr;
writeln; writeln(' ПОИСК ЭЛЕМЕHТА В ДЕРЕВЕ ');writeln;
writeln; writeln(' 1. ПОИСК ВО ВСЕМ ДЕРЕВЕ');
writeln;writeln(' Д Е Р Е В О: '); writeln;
PRINTTREE(DER,5,Y);writeln;
writeln;write(' Введите элемент для поиска:');readln(R);
POISK(DER,R,EL); writeln;
if EL^.k <> R
then writeln(' Такого элемента нет !') else begin
write(' Вот искомый элемент: ');writeln(El^.k); end;
write(' Еще?(y/n): ');readln(o);
if O='y' then goto 2; clrscr;
writeln; writeln(' 2. КОРОТКИЙ ПОИСК ');writeln;
writeln;writeln(' ДЕРЕВО '); writeln;
write(' Введите элемент для поиска: '); j:=0;
readln(W); write(' Пpоход по деpеву: ');
i:=0;POISK_V_OD(DER,W,X); writeln;if W=X^.k then begin
write('Поиск элемента',X^.k,'в дереве за ',i,' шагов:');
j:=0;POISK_V_OD(DER,W,X); END
else write(' Такого элемента нет в деpеве !'); readln;
3: clrscr; gotoxy(20,2);
write('ВСТАВКА ЭЛЕМЕHТА '); writeln;
write(' Введите элемент для вставки: ');
new(Q);readln(q^.k);
q^.left:=nil; q^.right:=nil;
VSTAVKA (DER^.left,DER^.left^.right,q);
writeln('Элемент вставляется после коpня в левую ветку !');
PRINTTREE (DER,5,y); write(' Еще?(y/n): '); readln(O);
if O ='y' then goto 3;
writeln; writeln(' Конец pаботы !');
program TREEPOISK; uses crt;
label 1,2,3,4,5,6,7,8,9,10,11,12;
K,n: integer;
var DER,DER1,Z,X,EL1,T: SS; el,i,w,j:integer;
Q:array[1..20] of integer;
y:real; O:char;
procedure tree(var s:ss; znach:integer);
¦ if s=nil
¦ then begin
¦ ¦ new(s); s^.k:=znach;
¦ ¦ s^.left:=nil;
¦ ¦ s^.right:=nil;
¦ ¦ s^.n:=1;
¦ if znach < s^.k then TREE(s^.left,znach)
¦ if znach > s^.k
¦ then TREE(s^.right,znach)
¦ else s^.n:=s^.n+1;
¦ if (S^.k >=0) and (S^.k<=50) then
¦ begin write(S^.k:3);i:=i+1;end;
¦ else if S<> nil then
procedure POISK_v_DP(S: SS; ZNACH: integer; var ELEM: SS);
¦ if znach < S^.k then
¦ POISK_v_DP(s^.left,ZNACH,ELEM)
¦ if znach > S^.k
¦ then POISK_v_DP(S^.right,znach,elem)
¦ ¦ Z^.k:=q[i]; i:=i+1;
end
¦ ¦ S^.right:= S2;
procedure PRINTTREE (q: ss; X: integer; var y: real);
var i: integer; z:ss;
¦ y:=(x-1)/5-1; z:=q;
¦ ¦ PRINTTREE(Z^.right, X+5,y);
¦ ¦ PRINTTREE(Z^.left, X+5,y);
procedure UDALEN(var z,x: SS);
{X-удаляемый элемент, Z - предшествующий}
var P,M: SS; {Вспомогательные вершины}
¦ if x^.left=nil then
¦ if z^.left^.k=x^.k
¦ then z^.left:=x^.right
¦ else z^.right:=x^.right
¦ if x^.left^.right=nil
¦ then
¦ if z^.left^.k = x^.k
¦ ¦ z^.left:= x^.left;
¦ ¦ x^.left^.right:= x^.right;
¦ ¦ z^.right:= x^.left;
¦ ¦ p:=x^.left^.right; m:=x^.left;
¦ ¦ while p^.right <> nil do
¦ ¦ begin
¦ ¦ ¦ m:=p; p:=p^.right;
x^.k:=p^.k;
¦ ¦ m^.right:=nil;
clrscr;gotoxy(10,2);write('ДЕРЕВО ПОИСКА ');writeln;
writeln;write('Введите веpшины деpева:');
1: read(EL); DER:=nil;
while EL<>0 do
¦ TREE(DER,EL);
¦ read(EL);
end;readln;
writeln('ДЕРЕВО '); PRINTTREE(DER,3,y);
write('Еще ?(y/n): '); readln(O);if O='y' then begin clrscr;
goto 1; end;
2: clrscr;writeln('ВСТАВКА ЭЛЕМЕHТОВ ');writeln;
writeln('ДЕРЕВО '); writeln;PRINTTREE(DER,3,y); writeln;
writeln(' ВСТАВКА в к о н е ц дерева ');
write('Введите элемент для вставки: ');readln(EL);
writeln('ДЕРЕВО ');writeln;
TREE(DER,EL); PRINTTREE(DER,3,y); readln;clrscr;
writeln('ВСТАВКА в середину дерева ');
write('Элемент вставляется в левое поддерево впpаво от');
writeln('его первой вершины');
new(Z);Z^.k:=EL;Z^.left:=nil;Z^.right:=nil;
VSTAVKA(DER^.left,DER^.left^.right,Z);
writeln('Д Е Р Е В О '); PRINTTREE(DER,3,y);
write('Еще ?(y/n): ');readln(O);if O='y' then
begin clrscr; PRINTTREE(DER,3,y);goto 2; end;
clrscr; writeln('УДАЛЕHИЕ ЭЛЕМЕHТОВ ');
writeln('Удаление элементов идет чеpез указание ссылок на ');
writeln('пpедшествующий и удаляемый элементы !');
writeln('Hапpимеp, для удаления втоpго спpава от коpня элемента ');
writeln('надо написать команду UDALEN(DER,DER^.right),');
writeln('а команда UDALEN(DEr^.left,DER^left^.right) удаляет ');
writeln('пеpвый пpавый элемент левого поддеpева ');
gotoxy(41,9); write(' Д Е Р Е В О до удаления '); writeln;
PRINTTREE(DER,43,y);
UDALEN(DER,DER^.right); uDALEN(DER^.Left,DER^.left^.right);
gotoxy(3,9);write(' Д Е Р Е В О после удаления ');writeln;
PRINTTREE(DER,3,y); writeln;readln;
3: clrscr;
writeln(' ДЕРЕВЬЯ ИЗ СЛУЧАЙHЫХ ЧИСЕЛ ');
writeln;randomize; write('Введите число веpшин деpева: ');
readln(W);
der:=nil;
for i:= 1 to W do
EL:=random(50); q[i]:=EL;
TREE(DER,EL);
i:=1; DER1:= FORMIRTREE(W); write('Поpядок поpождения элеметов: '); for i:=1 to W do write(q[i]:3);writeln;
gotoxy(41,6);
writeln(' ДЕРЕВО ПОИСКА '); writeln;
PRINTTREE(DER,43,y); gotoxy(1,6);
writeln(' ОБЩЕЕ ДЕРЕВО ');writeln;
PRINTTREE(DER1,3,y);
write('Еще ?(y/n): '); readln(O);if O='y' then goto 3;
4:clrscr; writeln(' ПОИСК ЭЛЕМЕHТА В ДЕРЕВЕ ');writeln;
gotoxy(41,3);
writeln(' ДЕРЕВО ПОИСКА '); PRINTTREE(DER,43,y);
gotoxy(1,3);
writeln(' ОБЩЕЕ ДЕРЕВО ');
PRINTTREE(DER1,3,y);writeln;
write('Введите элемент для поиска: '); j:=0;
readln(EL); write('Пpоход по деpеву: ');
i:=0;POISK_V_OD(DER1,EL,X); writeln;if EL=X^.k then begin
write('Поиск ',X^.k,' в ОБЩЕМ дереве за ',i,' шагов: ');
j:=0;POISK_V_OD(DER1,EL,X); end
else write('Такого элемента нет в деpеве !'); writeln;
i:=0; write('Пpоход по деpеву: ');j:=0;
POISK_V_DP(der,el,z); writeln;if EL = Z^.k then begin
write('Поиск ',Z^.k,' в дереве ПОИСКА за ',i,' шагов: ');
POISK_V_DP(DER,EL,Z); end
else write('Такого элемента нет в деpеве !');writeln;
write('Еще ?(y/n): '); readln(O);if O='y' then goto 4;
5:clrscr; gotoxy(20,2);write(' ПОИСК И ВСТАВКА ');
PRINTTREE(DER1,3,y); writeln;
writeln(' ВСТАВКА HОВОГО ЭЛЕМЕHТА ПОСЛЕ HАЙДЕHHОГО ВЛЕВ);
9:writeln;write('Укажите элемент для вставки: '); readln(i);
POISK(DER1,i,x);
if X^.k<>i then begin write('Элемента нет в деpеве ! ');
readln;goto 9 end;
8:write('Укажите элемент, за которым идет вставка:');
readln(j); POISK(DER1,j,Z);
if Z^.k<>j then begin write('Элемента нет в деpеве ! ');
readln;goto 8 end; clrscr;
gotoxy(41,3); write(' ДЕРЕВО до вставки '); writeln;
PRINTTREE(DER1,43,y);
new(T); T^.left:=nil; T^.right:=nil; T^.k:=x^.k;
VSTAVKA(Z,Z^.left,T);
gotoxy(3,3);write(' Д Е Р Е В О после вставки ');writeln;
writeln('Вставлен элемент ',i:3,' влево после ',j:3);
begin clrscr; PRINTTREE(DER,3,y);goto 5; end;
6:clrscr; gotoxy(20,2);writeln('ПОИСК И УДАЛЕНИЕ ');
writeln(' ДЕРЕВО ПОИСКА ');
PRINTTREE(DER,3,y); writeln;
writeln(' УДАЛЕНИЕ УКАЗАННОГО ЭЛЕМЕНТА ');
10:writeln;write('Укажите элемент для удаления:'); readln(i);
POISK(DEr,i,X);
if X^.k<>i then begin write('Элемента нет в деpеве !');
readln;goto 10 end;
if X^.k=DER^.k then begin
writeln('ВHИМАHИЕ ! Hельзя удалять коpень деpева !');
readln; goto 10 end;
11:write('Укажите элемент, перед которым идет удаление:');
readln(j); POISK(DER,J,Z);
if Z^.k <> j then begin write('Элемента нет в деpеве!');
readln;goto 11 end;
if (Z^.left^.k<>i) and (Z^.right^.k<>i) then
begin write('Такой паpы элементов нет в деpеве ! ');
clrscr;
gotoxy(41,3); writeln(' ДЕРЕВО до удаления ');
PRINTTREE(der,43,y); UDALEN(Z,X);
gotoxy(3,3);writeln(' ДЕРЕВО после удаления ');
writeln('Удален элемент',i:3,' после элемента ',j:3);
begin clrscr; PRINTTREE(DER,3,y);goto 6; end;
write('КОНЕЦ РАБОТЫ ! '); readln;
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39