[̲] [] [] [ ]

 

10.5.

 

, , . . .

G V, U

 

G = (V, U),

 

V , U . 璺 .

. . 10.29. 4 1 4. 璺 1 2, 2 1, 2 3, 4 4. .

 

. 10.29

 

u v1 v2, , v2 v1. :

 

u

v1 ú¾ v2 , v1 ú¾ v2

 

G v0 vn v0, v1, v2, ... vn-1, vn ,

 

v0 ú¾ v1, v1 ú¾ v2, ..., vn-1 ú¾ vn

 

v0 ¾ vn. v0 vn, , vn v0. . 10.29 1 3, 1 1, 4 4 . , .

v0 vn , v0 = vn. . 10.29 1 1, 2 2 4 4.

G , V V1, V2 , :

 

V1 È V2 = V, V1 Ç V2 = Æ,

u1 u2

"v1 Î V1, v2 Î V2 u1, u2 Î U , v1 ú¾ v2 v2 ú¾ v1

 

, , , . . 10.30 , {1, 2, 3} {4}, .

G , .

. 10.29

 

v , . v , . 0 , 0 .

, . .

 

1. , , . , , (. 10.30).

 

. 10.30

 

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

 

2. , 2 : , (. 10.31). .

 

. 10.31

 

10.5.1

 

, :

1.    .

2.    ?

3.    .

4.    .

5.    ˳ .

6.    .

 

ij 1, 3, 4, 5, 6 ; 2 .

.

t1, t2 n n, t1 t2.

. . .

˳ , . ˳ .

, . .

 

. 10.32. : . 璺 . nil. . , , nil.

 

. 10.32

 

. , 䳿 . Init, Empty, Root, LeftSon . MakeTree (. 10.33) . RightSon nil .

 

unit IntBTree;

 

interface

 

type btree = ^telem; {}

telem = record { }

d: integer;

rs, ls: btree

end;

 

function Init: btree; { }

function Empty(t: btree): boolean; { ? }

function MakeTree(n: integer; t1, t2: btree): btree;{ }

function Root(t: btree): integer; { }

function LeftSon(t: btree): btree; { ˳ }

function RightSon(t: btree): btree; { }

 

implementation

 

.................

 

function MakeTree(n: integer; t1, t2: btree): btree;

var p: btree;

begin

new(p);

p^.d:=n;

p^.ls:=t1; p^.rs:=t2;

MakeTree:=p

end;

 

.................

 

function RightSon(t: btree): btree;

begin

if t=nil then RightSon:=nil

else RightSon:=t^.rs

end;

 

end.

. 10.33

 

, , , .

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

 

1, 2, 4, 8, 9, 5, 3, 6, 10, 7

8, 4, 9, 2, 5, 1, 6, 10, 3, 7

8, 9, 4, 5, 2, 10, 6, 7, 3, 1

 

, . NodeCount . PrtKLP, PrtLKP PrtLPK -, - -. , . 10.34, .

 

. 10.34 , BtreeTst

 

program BtreeTst;

 

uses IntBTree;

 

function NodeCount(t: btree): word;

begin

if Empty(t) then NodeCount:=0

else

NodeCount:=1+NodeCount(LeftSon(t))+NodeCount(RightSon(t))

end;

 

procedure PrtKLP(t: btree);

begin

if Empty(t) then write(' ,')

else begin

write(Root(t),',');

PrtKLP(LeftSon(t));

PrtKLP(RightSon(t))

end

end;

 

procedure PrtLKP(t: btree);

begin

if Empty(t) then write(' ,')

else begin

PrtLKP(LeftSon(t));

write(Root(t),',');

PrtLKP(RightSon(t))

end

end;

 

procedure PrtLPK(t: btree);

begin

if Empty(t) then write(' ,')

else begin

PrtLPK(LeftSon(t));

PrtLPK(RightSon(t));

write(Root(t),',');

end

end;

 

var t: btree;

 

begin

 

t:=MakeTree(1,MakeTree(2,MakeTree(3,Init,Init),MakeTree(4,Init,Init)),

MakeTree(5,MakeTree(6,Init,Init),Init));

writeln;

writeln(' ',NodeCount(t));

write('='); PrtKLP(t); writeln;

write('='); PrtLKP(t); writeln;

write('='); PrtLPK(t); writeln;

end.

 

BtreeTst :

 

6

=1,2,3, , ,4, , ,5,6, , , ,

= ,3, ,2, ,4, ,1, ,6, ,5, ,

= , ,3, , ,4,2, , ,6, ,5,1,

 

ѳ.

 

/* btree.h */

 

typedef struct telem *btree; /* */

struct telem { /* */

int d;

btree ls, rs;

};

 

extern btree init(); /* */

extern int empty(btree t); /* ? */

extern btree make(int n, btree t1, btree t2); /* */

extern int root(btree t); /* */

extern btree leftson(btree t); /* ˳ */

extern btree rightson(btree t); /* */

 

[̲] [] [] [ ]