- , , , ( ) , . , , , .. - . , , ,
, ,
, ,
, , , () . , , , , , . . ( ) , , 0
, , . , . , , . , .
, n (n>=0) .
, , () . , , , () ().
, , , . , n, n-.
n- . , , , , .
, 1.
. . , , .
:
-
-
-
type
tree_ptr=^tree; //tree_ptr , tree
tree=
record
c: char;
|
|
|
left, right: tree_ptr;
end;
, ( ) , . .
, .
:
, :
, ;
- , ;
- , .
- , .
Function find(root:tree; key:integer; var p, paent: tree):Boolean;
begin
p:=root;
while p<>nil do begin
if key=p^.inf then begin ( )
Find =true
exit;
end;
Parent:=p ( )
If key<p.inf then
P:=p^.left ( )
Else p:=p^.right;
End;
find:=false;
end;
nill
p^.inf ,
p
, . , , , , . , (). . , , . , , , 5.
5 ; 5<10, , . 5 6; 5<6, . (). 5 1; 5>1, , . , .
( ), , -. , .
: , , . , .
procedure del (var root: tree; key: integer);
var
p: tree; { }
parent: tree; { }
y: tree; {, }
function spusk(p:tree):tree;
var
y: tree; {, }
pred:tree; { y}
begin
y:=p^.right;
if y^.left=nil then y^.left:=p^.left {1}
else {2}
begin
repeat
pred:=y; y:=y^.left;
until y^.left=nil;
y^.left:=p^.left; {3}
pred^.left:=y^.right; {4}
y^.right:=p^.right; {5}
end;
spusk:=y;
end;
begin
if not find(root, key, p, parent) then {6}
begin writeln( ); exit; end;
if p^.left=nil then y:=p^.right {7}
else
if p^.right=nil then y:=p^.left {8}
else y:=spusk(p); {9}
if p=root then root:=y {10}
else {11}
if key<parent^.inf then
|
|
|
parent^.left:=y
else parent^.right:=y;
dispose(p); {12}
end.
del root key . find p parent. , ({6}).
{7}-{9} y, . p , ( ) ({7}).
, p , ({8}).
, , spusk, ({9}).
, ({1}). ( ) , ({2}), pred, y , , (- ).
{3} . ({5}), . y, ({4}), .
spusk , . , ({10}), ({11}).
, ({12}).
1 ( ):
-
2 ( )
3 ( )
Procedure pass_dir (t:tree_ptr); //
t tree_ptr ,
Begin
if t<>nill then
begin
write(t^.c);
pass_dir(t^.left);
pass_dir(t^.right);
end;
end.
Procedure pass_back (t:tree_ptr); //
t tree_ptr ,
Begin
if t<>nill then
begin
pass_back(t^.left);
write(t^.c);
pass_back(t^.right);
end;
end.
Procedure pass_end (t:tree_ptr); //
t tree_ptr ,
Begin
if t<>nill then
begin
pass_end(t^.left);
pass_end(t^.right);
write(t^.c);
end;
end.
.
- , . PascalABC.NET ( ) ( , - ).
T ^T, :
type pinteger = ^integer;
var p: ^ record r,i: real end;
pointer.
, , ^:
var
i: integer;
pi: ^integer;
...
pi:= @i; // i
pi^:= 5; // i 5
.
:
|
|
|
var
p: pointer;
pr: ^real;
...
p:= pr;
:
pr:= p;
pr^:= 3.14;
(=) (<>). , , nil ( ): p:= nil.
! .NET T - (, , ). : , . , , , . , . , , .
