Прошу помочь в нелегком деле работы с деревьями
Задание такое:
Определить, находится ли максимальное число сбалансированного дерева глубже, чем минимальное.
Спасибо.
Type
ref = ^node;
node = record
Key: integer;
Left, right: ref;
Bal: -1..1;
count: integer;
end;
procedure search(x: integer; var p: ref; var h: boolean);
var
p1, p2: ref;
begin
if p = nil then begin
new(p);
h := true;
with p^ do begin
key := x;
count := 1;
left := nil;
right := nil;
bal := 0;
end
end
else
if x < p^.key then begin
search(x, p^.left, h);
if h then
case p^.bal of
1 :
begin
p^.bal := 0; h := false
end;
0 : p^.bal := -1;
-1:
begin
p1:= p^.left;
if p1^.bal = -1 then begin
p^.left := p1^.right;
p1^.right := p;
p^.bal := 0;
p := p1
end
else begin
p2 := p1^.right;
p1^.right := p2^.left;
p2^.left :=p1;
p^.left := p2^.right;
p2^. right := p;
if p2^.bal =-1 then p^.bal:=1 else p^.bal := 0;
if p2^.bal = 1 then p1^.bal := -1 else p1^.bal :=0;
p :=p2;
end;
p^.bal := 0;
h := false;
end
end
end
else
if x > p^.key then begin
search(x, p^.right, h);
if h then
case p^.bal of
-1:
begin
p^.bal := 0; h :=false;
end ;
0 : p^.bal := 1;
1 :
begin
p1 := p^.right;
if p1^.bal =1 then begin
p^.right := p1^.left;
p1^.left := p;
p^.bal := 0;
p := p1;
end
else begin
p2 := p1^.left;
p1^.left := p2^.right;
p2^.right := p1;
p^.right := p2^.left;
p2^.left := p;
if p2^.bal = 1 then p^.bal := -1 else p^.bal:=0;
if p2^.bal = -1 then p1^.bal := 1 else p1^.bal := 0;
p :=p2;
end ;
p^.bal := 0; h:= false;
end
end
end
else begin
p^.count := p^.count + 1; h :=false;
end
end;
const
n = 7;
arr: array[1 .. n] of integer =
(1, 2, 3, 4, 5, 6, 7);
var
root: ref;
i: integer;
h: boolean;
p: ref;
cr, cl: integer;
begin
root := nil;
for i := 1 to n do
search(arr[i], root, h);
{ ну и проверяем глубину }
writeln('right branch');
p := root; cr := 0;
while p <> nil do begin
inc(cr);
writeln(p^.key);
p := p^.right
end;
writeln('left branch');
p := root; cl := 0;
while p <> nil do begin
inc(cl);
writeln(p^.key);
p := p^.left
end;
if cl > cr then writeln('min is deeper')
else if cl < cr then writeln('max is deeper')
else writeln('deepths are equal');
end.