.


:




:

































 

 

 

 





, . ( ).

 

, - . , , , - . , .

 

:

i j, i=0, j=N-1.

k[i] k[j], , j , j 1.

i i 1, , j. , i j .

 

.

 

. :

- ;

. - ;

- , ;

.

 

:

( ) ""

 

procedure quick(item:^char; left,right:integer);

var

i,j:Integer;

x,y:char; begin

i:=left;

j:=right;

x:=item[int((left+right)/2)];

repeat

while (item[i]<x) and (i<right) do

i:=i+1;

while (x<item[j]) and (j>left) do

j:=j-1;

if i<=j then

begin

y:=item[i];

item[i]:=item[j];

item[j]:=y;

i:=i+1;

j:=j-1;

end;

until i<j;

if left<j then

quick(item,left,j);

if i<right then

quick(item,i,right);

end.

 

:

f, d, a, c, b, e

e, d, a, c, b, f

b, c, a, d, e, f

a, b, c, d, e, f

 

, . .

 

: NLog2N, N/6*Log2N.

 

: , N-. .

 

: (), , , ( ).

 

- , ( , ) ( ) . : .

 

, ( , ) - , .

 

: , , , , .

 

?

, , .

- , ; , , - , .

 

, - , - . , ( ) , - ( ), :

:

 

type

info=(* *);

ptr=^node;

node=record

key:Integer;

left,right:ptr;

data:^info

end;

var

tree:ptr;

 

, .

"" (node), . ( ) - (root). () - . , - . - .

 

: , ; ; ; ( - ).

 

. 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86, 82.

1. - 70;

2. 60<70, 70;

3. 85>70, 70;

4. 87>70, 87 ; 87>85, 87 85. . .

k, k , , . , , , . , .

 

, . - .

 

:

1. - , , ;

2. - , ;

3. - , , .

, ().

 

, .

 

 

, .

 

, - , , , ; , , .

 

- .

 

- - . , -, -.

 

, , .

 

- , - . , . . .

""

 

procedure addnode_r(r,prev:ptr; newkey:integer);

begin

if r=nil then

begin

new(r);

r^.left:=nil;

r^.right:=nil;

r^.key:=newkey;

if tree=nil then

tree:=r; { }

else

begin

if newkey<prev^.key then

prev^.left:=r

else

prev^.right:=r

end;

exit

end;

if newkey<r^.key then

addnode_r(r^.left,r,newkey)

else

addnode_r(r^.right,r,newkey)

end;

 

, , , .

:

, ;

;

;

.

 

nil.

 

, . . .

""

 

function maketree(n_node:integer):ptr;

var

newnode:ptr;

newkey,nl,nr:integer;

begin

if n_node=0 then

newnode:=nil

else

begin

nl:=n_node div 2;

nr:=n_node-nl-1;

{ }

read(newkey);

new(newnode);

with newnode^ do

begin

key:=newkey;

left:=maketree(nl);

right:=maketree(nr)

end;

end;

maketree:=newnode

end;

 

read(n);

tree:=maketree(n);

{ }

 

 

(inorder), (preorder) (postorder) ""

 

procedure inorder(r:ptr);

begin

if r=nil then exit;

inorder(r^.left);

writeln(...); { }

inorder(r^.right)

end;

 

procedure preorder(r:ptr);

begin

if r=nil then exit;

writeln(...); { }

preorder(r^.left);

preorder(r^.right)

end;

 

procedure postorder(r:ptr);

begin

if r=nil then exit;

postorder(r^.left);

postorder(r^.right)

writeln(...); { }

end;

 

- , . , . , .

 

:

""

 

procedure addnode2(skey:integer; var tree:ptr; newdata:^info);

var

r,s:ptr;

t:^info;

begin

if not searchtree(skey,tree,r) then

begin

new(t); {}

t:=newdata; {}

new(s); {}

s^.key:=skey;

s^.left:=nil; {}

s^.right:=nil;

s^.data:=t;

if tree=nil then

tree:=s

else

if skey<r^.key then

r^.left:=s

else

r^.right:=s

end

end;

 

:

""

 

function search_tree(skey:integer; var tree,fnode:ptr):boolean;

var

p,q:ptr;

b:boolean;

begin

b:=false;

p:=tree;

if tree<>nil then

repeat

q:=p;

if p^.key=skey then

b:=true

else

begin

if skey<p^.key then

p:=p^.left

else

p:=p^.right

end

until (b) or (p=nil);

search_tree:=b;

fnode:=q;

end;

 

. ( ) - Log2N .

( ) - .

- , , , . ( 0 ).

 

, , .

.

 

- , . , , . .

 

, , , nil.

 

.

50.

:

;

;

.

 

""

 

procedure delnode(var d:ptr; key:integer);

var

q:ptr;

 

procedure del1(var r:ptr);

begin

if r^.right=nil then

begin

q^.key:=r^.key;

q^.data:=r^.data;

q:=r;

r:=r^.left

end

else

del1(r^.right)

end;

 

begin

if d=nil then exit { }

else

if key<d^.key then

delnode(d^.left,key)

else

if key>d^.key then

delnode(d^.right,key)

else

begin

q:=d; { }

if q^.right=nil then

d:=q^.left

else

if q^.left=nil then

d:=q^.right

else { }

del1(q^.left)

end

end;

 

del1 . , q^, key data q^ r^. , r (r:=r^.left).

 

 

 

- ( ) . , , , , . .

 

. . , , . , , .

 

, , :

;

( , , );

.

 

. :

.

.

 

:

, , ;

;

, , , .

 

:

, , () . , - . N , , . N - ;

, .

 

.

. ( ) .

, , , .

 

:

.

 

.

. , , - . , - .

 

:

;

.

 

 

:

, ;

.

 

.

:

.

 

 

:

( , ).

 

 





:


: 2016-10-06; !; : 599 |


:

:

, ,
==> ...

788 - | 797 -


© 2015-2024 lektsii.org - -

: 0.15 .