2.
1. .
, ( ), (), . , . , , .
() . : ( ), , , .
, , , , , . , . . , , : O (n) = C log2 n ( O (n) = n).
. 9, 44, 0, 7, 10, 6, 12, 45 .
9 , , , . .
2.
:
;
;
( ..);
.
, ( ). , .
Type BT=LongInt; U = ^BinTree; BinTree = Record Inf: BT; L, R: U End;
: .
: ( )
Procedure InsIteration(Var T: U; X: BT);
Var vsp, A: U;
Begin
New(A); A^.Inf:= X; A^.L:=Nil; A^.R:= Nil;
If T=Nil Then T:=A
Else Begin vsp:= T;
While vsp <> Nil Do
If A^.Inf < vsp^.Inf
Then
If vsp^.L=Nil Then Begin vsp^.L:=A; vsp:=A^.L End Else vsp:=vsp^.L
Else
If vsp^.R = Nil Then Begin vsp^.R:= A; vsp:=A^.R End Else vsp:= vsp^.R;
End
End;
: ( )
Procedure InsRec(Var Tree: U; x: BT);
|
|
|
Begin
If Tree = Nil
Then Begin
New(Tree);
Tree^.L:= Nil;
Tree^.R:= Nil;
Tree^.Inf:= x
End
Else If x < Tree^.inf
Then InsRec(Tree^.L, x)
Else InsRec(Tree^.R, x)
End;
3.
() . () , () ( ). .
.
:
Procedure PrintTree(T: U);
begin
if T <> Nil
then begin PrintTree(T^.L); write(T^.inf: 6); PrintTree(T^.R) end;
end;
, true (1), , false (0) .
:
function find(Tree: U; x: BT): boolean;
begin
if Tree=nil then find:= false
else if Tree^.inf=x then Find:= True
else if x < Tree^.inf
then Find:= Find(Tree^.L, x)
else Find:= Find(Tree^.R, x)
end;
. x ( ):
1) , x, 1 ( , );
2) , x, 2.
1 . ( 1), ( 0).
, . .
:
function Delete(Tree: U; x: BT): U;
var P, v: U;
begin
if (Tree=nil)
then writeln(' !')
else if x < Tree^.inf then Tree^.L:= Delete(Tree^.L, x) { 1}
else
if x > Tree^.inf
then Tree^.R:= Delete(Tree^.R, x) { 1}
else
begin { 1}
P:= Tree;
if Tree^.R=nil
then Tree:=Tree^.L
else if Tree^.L=nil
then Tree:=Tree^.R
else begin
v:= Tree^.L;
while v^.R^.R <> nil do v:= v^.R;
Tree^.inf:= v^.R^.inf;
P:= v^.R;
v^.R:=v^.R^.L;
end;
dispose(P);
end;
Delete:= Tree
end;
. , .
