STRUKTUR DATA SAK 1107

TUTORIAL 6

JAWAPAN

1. Berdasarkan soalan di bawah :-

20, 30, 45, 46, 31, 23, 19, 15, 18, 13, 50, 21

i. Bina pepohon gelintaran perduaan ( Binary Search Tree)

ii. Lakukan penyusuran ke atas pepohon tersebut secara

a. Preorder

(akar kiri kanan)

= 20 19 15 13 18 30 23 21 45 31 46 50

b. Inorder

(kiri akar kanan)

= 13 15 18 19 20 21 23 30 31 45 46 50

c. Postorder

(kiri kanan akar)

= 13 18 15 19 21 23 30 31 46 45 50 20

iii. Seterusnya tunjukkan perubahan sekiranya ( anggapkan nod yang sudah dihapuskan tidak wujud lagi untuk proses penghapusan seterusnya )

a. 15 dihapuskan

· jika 15 dihapuskan ia mempunyi dua anak.

Carikan pendahulu mengikut gelidah tertib sisipan 18

Gantikan dengan nod terkanan dalam subpohon kiri.

b. 19 dihapuskan

· jika 19 dihapuskan anak kirinya iatu 18 akan dinaikkan kerana ia tidak mempunyi anak kanan.

c. 46 dihapuskan

· Jika 46 dihapuskan, anak kananya iatu 50 dinaikkan kerana ia tidak mempunyi anak kiri.

d. 20 dihapuskan

· jika akar pokok iatu 20 dihapuskan ia mempunyi dua anak.

Carikan pendahulu mengikut gelidah tertib sisipan 13

Gantikan dengan nod terkcil dalam subpohon kiri.

2. Berdasarkan kepada susunan abjad dibawah :

M O R T C F E A S N

i. Bina pepohon gelintaran perduaan ( Binary Search Trees )

ii. Lakukan penyusuran ke atas pepohon tersebut secara :

a. Postorder

(akar kiri kanan)

= M C A F E O N R T Q

b. Inorder

(kiri akar kanan)

= E F A C M N O R S T

c. Preorder

(kiri kanan akar)

= E A F C N R O S T M

iii. Seterusnya, tunjukkan perubahan sekiranya ( anggapkan nod yang sudah dihapuskan tidak wujud lagi untuk proses penghapusan seterusnya )

a. C dihapuskan

· jika C dihapuskan ia mempunyi dua anak.

Carikan pendahulu mengikut gelidah tertib sisipan E

Gantikan dengan nod terkecil dalam subpohon kiri.

b. M dihapuskan

· jika M dihapuskan ia mempunyi dua anak.

Carikan pendahulu mengikut gelidah tertib sisipan F

Gantikan dengan nod terkanan dalam subpohon kiri.

c. T dihapuskan

· Jika T dihapuskan, anak kirinya iatu S dinaikkan kerana ia tidak mempunyi anak kanan.

S

d. F dihapuskan

· jika F dihapuskan ia mempunyi dua anak.

Carikan pendahulu mengikut gelidah tertib sisipan E

Gantikan dengan nod terkecil dalam subpohon kiri.

A

O

R

N

E

S

3. Bina pepohon ungkapan berdasarkan kepada ungkapan di bawah.

a.

-

A+B-C

b.

*

A/B*C/D

c.

*

V-W*(X+Y)

d. (J/K-L)/(M+N*O)

e. A/(B-C) +D*E

f. S*T/U+V-W/X

g. (A-B)*C

h. P*Q/R

i. V+W-(X+Y/Z)

-

+

X
M

/

Y

Z

V

W

+

4. Tentukan Samada pepohon di bawah adalah seimbang AVL dengan meletakkan nilai pada setiap nod.

0

1.

1

-1

0

1

0

2.

0

1

-1

3.

0

1

1

0

1

4.

0

1

1

-1

1