: :

, ( ), (), . , . , , .

() . : ( ), , , .

, , , , , . , . . , , : O(n) = C log2n ( O(n) = n).

. 9, 44, 0, 7, 10, 6, 12, 45 .

9 , , , . .

  :

:

;

;

( ..);

.

, ( ). , .

Type BT=LongInt; U = ^BinTree; BinTree = Record Inf : BT; L, R : U End;

: .

{ , Turbo Pascal}

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;

{ , Turbo Pascal}

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;

C++.

typedef long BT;

struct BinTree{

BT inf;

BinTree *L; BinTree *R;

};

/* , C++ */

BinTree* InsIteration(BinTree *T, BT x)

{ BinTree *vsp, *A;

A = (BinTree *) malloc(sizeof(BinTree));

A->inf=x; A->L=0; A->R=0;

if (!T) T=A;

else {vsp = T;

while (vsp)

{if (A->inf < vsp->inf)

if (!vsp->L) {vsp->L=A; vsp=A->L;}

else vsp=vsp->L;

else

if (!vsp->R) {vsp->R=A; vsp=A->R;}

else vsp=vsp->R;

}

}

return T;

}

/* , C++ */

BinTree* InsRec(BinTree *Tree, BT x)

{

if (!Tree) {Tree = (BinTree *) malloc(sizeof(BinTree));

Tree->inf=x; Tree->L=0; Tree->R=0;

}

else if (x < Tree->inf) Tree->L=InsRec(Tree->L, x);

else Tree->R=InsRec(Tree->R, x);

return Tree;

}

() . () , () ( ). .

.

{Turbo Pascal}

Procedure PrintTree(T : U);

begin

if T Nil

then begin PrintTree(T^.L); write(T^.inf : 6); PrintTree(T^.R) end;

end;

// C++

void PrintTree(BinTree *T)

{

if (T) {PrintTree(T->L); cout infR);}

}

, true (1), , false (0) .

{Turbo Pascal}

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;

/* C++ */

int Find(BinTree *Tree, BT x)

{ if (!Tree) return 0;

else if (Tree->inf==x) return 1;

else if (x < Tree->inf) return Find(Tree->L, x);

else return Find(Tree->R, x);

}

. x ( ):

1) , x, 1 ( , );

2) , x, 2.

1 . ( 1), ( 0).

, . .

{Turbo Pascal}

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;

{C++}

BinTree * Delete(BinTree *Tree, BT x)

{ BinTree* P, *v;

if (!Tree) cout L = Delete(Tree->L, x);

else if (x > Tree-> inf) Tree->R = Delete(Tree->R, x);

else {P = Tree;

if (!Tree->R) Tree = Tree->L; // 1

else if (!Tree->L) Tree = Tree->R; // 1

else { v = Tree->L;

while (v->R->R) v = v->R; // 2

Tree->inf = v->R->inf;

P = v->R; v->R = v->R->L;

}

free(P);

}

return Tree;

}

. , .