. - , :
.
. .
21.6
. . , . , , , .
:
: , .
: .
while do
end while
, . , , .
: . .
: .
{ }
for from 1 to do
while do
{ }
end while
{ SST }
end for
(SST-Shortest Sceleton Tree - ).
. . .
: , . , , .
21.8
21.9 21.11 .
+/- | |||
(1, 7) | |||
(3, 4) | |||
(2, 7) | |||
(3, 7) | |||
(2, 3) | , | ||
(4, 7) | , | ||
(1, 5) | |||
(1, 2) | , | ||
(1, 6) | . . . | ||
(5, 7) | |||
(5, 6) | |||
(6, 7) |
21.9
21.10
21.11
: =57.
21.7 .
( ) (. 21.12) :
1. , , .
|
|
2. , , .
3. .
21.12
, ; . 1, , , .
, , .
, , .
.
- .
, .
.
. 21.13 3, 8 2, 1, 1.
21.13
. , .. , , .., .
, , , 62: .
() , . , 2.
, , , , .
( 2 3 4), ( 9 8), ( 5 4), ( 3, 5, 7, 9).
, .
, .
. 21.14 3.
21.14
, .
, .
6.77 6 7, 8, 9 (8,9).
21.5 ( ). , .
21.8
, .. , .
3 :
1. .
2. .
3. .
( , , , , , preorder):
|
|
1. .
2. .
3. .
( , , inorder):
1. .
2. .
3. .
( , , , , postorder):
1. .
2. .
3. .
21.9
.
:
1. ( ).
2. .
3. :
, ;
, (.. ).
4. , , .
, .
.
: . . . .
21.10
1. . .
2. ?
3. .
4. ?
5. ?
6. ?
7. . ? .
8. () .
9. .
10. .
11. .
12. .
13. .
14. .
22. .
22.1
22.1.1
( ) , . .
, ().
, , .
, , .
.
, , , , .
, .
. . 22.1: 1. 1, 3, 1, 4 , ; 2. 1, 3, 5, 2, 3, 4 , ; 3. 1, 4, 3, 2, 5 ; 4. 1, 3, 5, 2, 3, 4, 1 , ; 5. 1, 3, 4, 1 .
22.1
, (. 22.2).
22.2 ()
|
|
:
() .
, , .
, .
. . 22.3 .
22.3
, .
, . , , .
, , .
. . 22.3 , .
22.1.2
. , , , , . , , , .
, , .
. , . 22.4, ; .
22.4
.
.
: .
:
. - 2, 2 .
- .
22.1.3
. , , . . :
- .
.
22.1.4
. , , , . , .
. , . . , - .
, .
. , . .
. , . 22.5.
22.5
:
. , : .
|
|
. , ,
( ), , .
. . 22.6 .
22.6