, . ( ).
, - . , , , - . , .
:
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 - ;
, .
.
. ( ) .
, , , .
:
.
.
. , , - . , - .
:
;
.
:
, ;
.
.
:
.
:
( , ).