POHON
Soal & Penyelesaian
1.
Tulislah sebuah program C++ untuk merealisasikan pohon
biner.
Penyelesaian:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
|
//pohonBiner.cpp
//Mendemonstrasikan pohon biner
#include
<iostream>
#include
<stack>
#include
<conio.h>
using namespace std;
class Simpul
{
public:
int iData; //item data (kunci)
double dData; //item data
Simpul*
pAnakKiri; //anak kiri dari simpul
Simpul*
pAnakKanan; //anak kanan dari simpul
//konstruktor
Simpul() :
iData(0), dData(0.0), pAnakKiri(NULL),
pAnakKanan(NULL)
{ }
~Simpul()
//destruktor
{ cout
<< "X-" <<
iData << " "; }
void tampilSimpul() //menampilkan
simpul, contoh {75, 7.5}
{
cout
<< "{" <<
iData << ", " << dData << "} ";
}
}; //akhir kelas Simpul
class Pohon
{
private:
Simpul*
pAkar; //simpul pertama pada pohon
public:
Pohon() :
pAkar(NULL) //konstruktor
{ }
Simpul* cari(int kunci) //mencari
simpul dengan kunci tertentu
{ //(asumsi
pohon tak-kosong)
Simpul*
pSkrg = pAkar; //diawali di akar
while(pSkrg->iData != kunci)
//ketika tidak cocok,
{
if(kunci < pSkrg->iData) //ke
kiri?
pSkrg = pSkrg->pAnakKiri;
else //atau ke kanan?
pSkrg = pSkrg->pAnakKanan;
if(pSkrg
== NULL) //jika tidak ada anak,
return NULL; //tidak ditemukan
}
return pSkrg; //ditemukan
} //akhir
cari()
void sisip(int id, double dd)
//menyisipkan simpul baru
{
Simpul*
SimpulBaru = new Simpul; //menciptakan
simpul baru
SimpulBaru->iData = id; //menyisipkan data
SimpulBaru->dData = dd;
if(pAkar==NULL) //tidak ada simpul pada akar
pAkar
= SimpulBaru;
else //akar ditempati
{
Simpul*
pSkrg = pAkar; //diawali di akar
Simpul*
pInduk;
while(true) //(keluar scr internal)
{
pInduk
= pSkrg;
if(id < pSkrg->iData) //ke kiri?
{
pSkrg = pSkrg->pAnakKiri;
if(pSkrg
== NULL) //jika di akhir,
{ //sisip di kiri
pInduk->pAnakKiri = SimpulBaru;
return;
}
}
//akhir if ke kiri
else //atau ke kanan?
{
pSkrg = pSkrg->pAnakKanan;
if(pSkrg
== NULL) //jika di akhir,
{ //sisip di kanan
pInduk->pAnakKanan = SimpulBaru;
return;
}
}
//akhir else ke kanan
}
//akhir while
} //akhir
else tidak di akar
} //akhir
sisip()
void jelajah(int tipeJelajah)
{
switch(tipeJelajah)
{
case 1: cout << "\nPenjelajahan Preorder: ";
preOrder(pAkar);
break;
case 2: cout << "\nPenjelajahan Inorder: ";
inOrder(pAkar);
break;
case 3: cout << "\nPenjelajahan Postorder: ";
postOrder(pAkar);
break;
}
cout
<< endl;
}
void preOrder(Simpul* pAkarLokal)
{
if(pAkarLokal != NULL)
{
cout
<< pAkarLokal->iData << " "; //menampilkan
simpul
preOrder(pAkarLokal->pAnakKiri);
//anak kiri
preOrder(pAkarLokal->pAnakKanan);
//anak kanan
}
}
void inOrder(Simpul* pAkarLokal)
{
if(pAkarLokal != NULL)
{
inOrder(pAkarLokal->pAnakKiri);
//anak kiri
cout
<< pAkarLokal->iData << " "; //menampilkan
simpul
inOrder(pAkarLokal->pAnakKanan);
//anak kanan
}
}
void postOrder(Simpul* pAkarLokal)
{
if(pAkarLokal != NULL)
{
postOrder(pAkarLokal->pAnakKiri);
//anak kiri
postOrder(pAkarLokal->pAnakKanan);
//anak kanan
cout
<< pAkarLokal->iData << " "; //menampilkan
simpul
}
}
void tampilPohon()
{
stack<Simpul*> tumpukan;
tumpukan.push(pAkar);
int jumSpasi = 32;
bool apaBarisKosong = false;
cout
<<"......................................................";
cout
<< endl;
while(apaBarisKosong==false)
{
stack<Simpul*>
tumpukanLokal;
apaBarisKosong
= true;
for(int j=0; j<jumSpasi; j++)
cout
<< " ";
while(tumpukan.empty()==false)
{
Simpul*
temp = tumpukan.top();
tumpukan.pop();
if(temp != NULL)
{
cout << temp->iData;
tumpukanLokal.push(temp->pAnakKiri);
tumpukanLokal.push(temp->pAnakKanan);
if(temp->pAnakKiri
!= NULL || temp->pAnakKanan != NULL)
apaBarisKosong = false;
}
else
{
cout << "--";
tumpukanLokal.push(NULL);
tumpukanLokal.push(NULL);
}
for(int j=0; j<jumSpasi*2-2; j++)
cout << " ";
}
cout
<< endl;
jumSpasi
/= 2;
while(tumpukanLokal.empty()==false)
{
tumpukan.push(
tumpukanLokal.top() );
tumpukanLokal.pop();
}
}
cout
<<"......................................................";
cout
<< endl;
} //akhir
tampilPohon()
void hapus() //menghapus semua simpul
{
hapusRekursif(pAkar); } //mulai dari akar
void hapusRekursif(Simpul*
pAkarLokal) //menghapus simpul-simpul
{
if(pAkarLokal != NULL)
{
hapusRekursif(pAkarLokal->pAnakKiri);
//subpohon kiri
hapusRekursif(pAkarLokal->pAnakKanan);
//subpohon kanan
delete pAkarLokal; //menghapus simpul
ini
}
}
}; //akhir kelas Pohon
int main()
{
int nilai;
char pilihan = NULL;
Simpul*
ditemukan;
Pohon pohon;
//menciptakan Pohon
pohon.sisip(50,
5.0); //menyisipkan pohon-pohon
pohon.sisip(25,
2.5);
pohon.sisip(75,
7.5);
pohon.sisip(12,
1.2);
pohon.sisip(37,
3.7);
pohon.sisip(43,
4.3);
pohon.sisip(30,
3.0);
pohon.sisip(33,
3.3);
pohon.sisip(87,
8.7);
pohon.sisip(93,
9.3);
pohon.sisip(97,
9.7);
while(pilihan != 'k') //berinteraksi
dengan pengguna
{ //sampai
pengguna mengetikkan 'k'
cout <<
"masukkan huruf pertama dari
";
cout <<
"tampil, sisip, cari,
jelajah, atau keluar: ";
cin >>
pilihan;
switch(pilihan)
{
case 't': //menampilkan Pohon
pohon.tampilPohon();
break;
case 's': //menyisipkan sebuah Simpul
cout
<< "Masukkan
nilai yang akan disisipkan: ";
cin
>> nilai;
pohon.sisip(nilai,
nilai + 0.9);
break;
case 'c': //mencari sebuah Simpul
cout
<< "Masukkan nilai yang
akan dicari: ";
cin >>
nilai;
ditemukan
= pohon.cari(nilai);
if(ditemukan != NULL)
{
cout
<< "Ditemukan: ";
ditemukan->tampilSimpul();
cout
<< endl;
}
else
cout
<< "Tidak ditemukan."
<< nilai << endl;
break;
case 'j': //menjelajah Pohon
cout
<< "Masukkan
tipe jelajah (1 = preorder, "
<< "2 = inorder, 3 = postorder): ";
cin
>> nilai;
pohon.jelajah(nilai);
break;
case 'k': //keluar program
pohon.hapus();
cout
<< endl;
break;
default:
cout
<< "Entri tak-valid\n";
} //akhir
switch
} //akhir while
getch();
return 0;
} //akhir main()
|
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar: s
Masukkan nilai yang akan disisipkan: 23
masukkan huruf pertama dari tampil, sisip, cari,
jelajah, atau keluar: s
Masukkan nilai yang akan disisipkan: 34
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar: s
Masukkan nilai yang akan disisipkan: 45
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar: s
Masukkan nilai yang akan disisipkan: 56
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar: s
Masukkan nilai yang akan disisipkan: 67
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar: c
Masukkan nilai yang akan dicari: 45
Ditemukan: {45, 45.9}
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar: t
.................................................................
50
25 75
12 37 56 87
-- 23 30
43 -- 67
-- 93
-- --
-- -- -- 33 --
45 -- --
-- -- --
-- -- 97
----------------------34----------------------------------------
..................................................................
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar: j
Masukkan tipe jelajah (1 = preorder, 2 =
inorder, 3 = postorder): 1
Penjelajahan Preorder: 50 25 12 23 37 30 33 34
43 45 75 56 67 87 93 97
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar: j
Masukkan tipe jelajah (1 = preorder, 2 =
inorder, 3 = postorder): 2
Penjelajahan Inorder: 12 23 25 30 33 34 37 43
45 50 56 67 75 87 93 97
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar: j
Masukkan tipe jelajah (1 = preorder, 2 =
inorder, 3 = postorder): 3
Penjelajahan Postorder: 23 12 34 33 30 45 43 37
25 67 56 97 93 87 75 50
masukkan huruf pertama dari tampil, sisip,
cari, jelajah, atau keluar:
2.
Tulislah sebuah program C++ untuk merealisasikan pohon
234.
Penyelesaian:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
|
//pohon234.cpp
//Mendemonstrasikan pohon 234
#include
<iostream>
#include
<conio.h>
using namespace std;
class ItemData
{
public:
double dData; //sebuah data
ItemData() :
dData(0.0) //konstruktor default
{ }
ItemData(double dd) : dData(dd) //konstruktor
1-argumen
{ }
void tampilItem() //format
"/27"
{ cout
<< "/" << dData; }
}; //akhir kelas ItemData
class Simpul
{
private:
enum {ORDE=4};
int jumItem;
Simpul*
pInduk;
Simpul*
arrayAnak[ORDE]; //array ptr ke simpul
ItemData*
arrayItem[ORDE-1]; //array ptr ke data
public:
Simpul() :
jumItem(0)
{
for(int j=0; j<ORDE; j++) //menginisialisasi array
arrayAnak[j] = NULL;
for(int k=0; k<ORDE-1; k++)
arrayItem[k] = NULL;
}
//menghubungkan
anak ke simpul ini
void hubungKeAnak(int noAnak, Simpul* pAnak)
{
arrayAnak[noAnak] = pAnak;
if(pAnak != NULL)
pAnak->pInduk = this;
}
//mendiskoneksi
anak dari simpul ini
Simpul*
diskonekAnak(int noAnak)
{
Simpul*
pSimpulTemp = arrayAnak[noAnak];
arrayAnak[noAnak] = NULL;
return pSimpulTemp;
}
Simpul*
bacaAnak(int noAnak)
{ return arrayAnak[noAnak]; }
Simpul*
bacaInduk()
{ return pInduk; }
bool apaDaun()
{ return (arrayAnak[0]==NULL) ? true : false; }
int bacaJumItem()
{ return jumItem; }
ItemData
bacaItem(int indeks)
{ return *( arrayItem[indeks] ); }
bool apaPenuh()
{ return (jumItem==ORDE-1) ? true : false; }
int cariItem(double kunci)
//menghasilkan indeks
{ //item (di
dalam Simpul)
for(int j=0; j<ORDE-1; j++) //jika ditemukan,
{ //jika
tidak,
if(arrayItem[j] == NULL) //menghasilkan -1
break;
else if(arrayItem[j]->dData ==
kunci)
return j;
}
return -1;
} //akhir
cariItem
int sisipItem(ItemData* pItemBaru)
{
//asumsi
simpul tidak penuh
jumItem++; //menambahkan item baru
double kunciBaru =
pItemBaru->dData; //kunci dari item baru
for(int j=ORDE-2; j>=0; j--) //berawal di kanan,
{ //
memeriksa item-item
if(arrayItem[j] == NULL) //jika item null,
continue; //ke kiri satu sel
else //tidak null,
{
//membaca kuncinya
double kunciNya =
arrayItem[j]->dData;
if(kunciBaru < kunciNya) //jika
lebih besar
arrayItem[j+1] = arrayItem[j]; //geser ke kanan
else
{
arrayItem[j+1] = pItemBaru; //sisipkan item baru
return j+1; //menghasilkan
indeks
}
}
//akhir else (tak null)
} //akhir
for
arrayItem[0]
= pItemBaru; //menyisipkan item baru
return 0;
} //akhir
sisipItem()
ItemData*
hapusItem() //menghapus item terbesar
{
//asumsi
simpul tidak penuh
ItemData*
pTemp = arrayItem[jumItem-1]; //simpan item
arrayItem[jumItem-1] = NULL; //mendiskonek
jumItem--; //item berkurang satu
return pTemp; //menghasilkan item
}
void tampilSimpul() //format
"/24/56/74/"
{
for(int j=0; j<jumItem; j++)
arrayItem[j]->tampilItem(); //format "/56"
cout
<< "/"; //final “/”
}
}; //akhir kelas Simpul
class Pohon234
{
private:
Simpul*
pAkar; //simpul akar
public:
Pohon234()
{ pAkar = new Simpul; }
int cari(double kunci)
{
Simpul*
pSimpulSkrg = pAkar; //diawali akar
int nomorAnak;
while(true)
{
if((
nomorAnak=pSimpulSkrg->cariItem(kunci) ) != -1)
return nomorAnak; //ditemukan
else
if( pSimpulSkrg->apaDaun() )
return -1; //tidak ditemukan
else //cari lebih dalam
pSimpulSkrg = bacaAnakBrktnya(pSimpulSkrg, kunci);
} //akhir
while
}
void sisip(double dNilai) //menyisipkan sebuah ItemData
{
Simpul*
pSimpulSkrg = pAkar;
ItemData*
pTempItem = new ItemData(dNilai);
while(true)
{
if( pSimpulSkrg->apaPenuh() )
//jika simpul penuh,
{
pecah(pSimpulSkrg); //memecah
pSimpulSkrg = pSimpulSkrg->bacaInduk();
//melakukan
pencarian
pSimpulSkrg = bacaAnakBrktnya(pSimpulSkrg, dNilai);
}
//akhir if(Simpul penuh)
else if( pSimpulSkrg->apaDaun() ) //jika simpul adalah daun,
break; //sisipkan
//Simpul tidak
penuh, bukan daun; pergi ke level bawah
else
pSimpulSkrg = bacaAnakBrktnya(pSimpulSkrg, dNilai);
} //akhir
while
pSimpulSkrg->sisipItem(pTempItem); //menyisipkan item baru
} //akhir
sisip()
void pecah(Simpul* pSimpulIni)
//memecah simpul
{
//diasumsikan simpul penuh
ItemData
*pItemB, *pItemC;
Simpul
*pInduk, *pAnak2, *pAnak3;
int indeksItem;
pItemC =
pSimpulIni->hapusItem();
pItemB =
pSimpulIni->hapusItem();
pAnak2 =
pSimpulIni->diskonekAnak(2);
pAnak3 =
pSimpulIni->diskonekAnak(3);
Simpul*
pKananBaru = new Simpul; //menciptakan
simpul baru
if(pSimpulIni==pAkar) //jika akar,
{
pAkar
= new Simpul(); //menciptakan
simpul baru
pInduk = pAkar; //akar adalah induk
pAkar->hubungKeAnak(0, pSimpulIni); //konek ke induk
}
else //tidak akar
pInduk =
pSimpulIni->bacaInduk(); //membaca induk
//menangani
induk
indeksItem = pInduk->sisipItem(pItemB); //item B ke
induk
int n = pInduk->bacaJumItem();
for(int j=n-1; j>indeksItem; j--)
{
Simpul* pTemp = pInduk->diskonekAnak(j);
pInduk->hubungKeAnak(j+1, pTemp);
}
//koneksi
kananBaru ke induk
pInduk->hubungKeAnak(indeksItem+1, pKananBaru);
//menangani
kananBaru
pKananBaru->sisipItem(pItemC);
pKananBaru->hubungKeAnak(0, pAnak2);
pKananBaru->hubungKeAnak(1, pAnak3);
} //akhir
pecah()
//membaca
anak simpul sesuai untuk nilai yang dicari
Simpul* bacaAnakBrktnya(Simpul*
pSimpul, double nilai)
{
int j;
//asumsi
simpul tidak kosong, tidak penuh, tidak daun
int jumItem =
pSimpul->bacaJumItem();
for(j=0; j<jumItem; j++)
{
if( nilai <
pSimpul->bacaItem(j).dData )
return pSimpul->bacaAnak(j);
}
return pSimpul->bacaAnak(j);
}
void tampilPohon()
{
tampilPohonRekursif(pAkar, 0, 0);
}
void tampilPohonRekursif(Simpul*
pSimpulIni, int level, int nomorAnak)
{
cout
<< "level="
<< level
<< " anak="
<< nomorAnak << " ";
pSimpulIni->tampilSimpul();
cout
<< endl;
int jumItem =
pSimpulIni->bacaJumItem();
for(int j=0; j<jumItem+1; j++)
{
Simpul* pSimpulBrktnya = pSimpulIni->bacaAnak(j);
if(pSimpulBrktnya != NULL)
tampilPohonRekursif(pSimpulBrktnya, level+1, j);
else
return;
}
} //akhir
tampilPohonRekursif()
}; //akhir kelas Pohon234
int main()
{
double nilai;
Pohon234* pPohon
= new Pohon234;
pPohon->sisip(50);
pPohon->sisip(40);
pPohon->sisip(60);
pPohon->sisip(30);
pPohon->sisip(70);
while(true)
{
int ditemukan;
cout <<
"Masukkan huruf pertama
dari tampil, sisip, atau cari: ";
char pilihan;
cin >>
pilihan;
switch(pilihan)
{
case 't':
pPohon->tampilPohon();
break;
case 's':
cout
<< "Masukkan
nilai untuk disisipkan: ";
cin
>> nilai;
pPohon->sisip(nilai);
break;
case 'c':
cout
<< "Masukkan
nilai yang dicari: ";
cin
>> nilai;
ditemukan = pPohon->cari(nilai);
if(ditemukan != -1)
cout << "ditemukan
" << nilai << endl;
else
cout << "tidak ditemukan " << nilai
<< endl;
break;
default:
cout
<< "Entri tak-valid\n";
} //akhir
switch
} //akhir while
getch();
return 0;
delete pPohon;
} //akhir main()
|
Masukkan huruf pertama dari tampil, sisip, atau
cari: t
level=0 anak=0 /50/
level=1 anak=0 /30/40/
level=1 anak=1 /60/70/
Masukkan huruf pertama dari tampil, sisip, atau
cari: s
Masukkan nilai untuk disisipkan: 34
Masukkan huruf pertama dari tampil, sisip, atau
cari: s
Masukkan nilai untuk disisipkan: 67
Masukkan huruf pertama dari tampil, sisip, atau
cari: s
Masukkan nilai untuk disisipkan: 77
Masukkan huruf pertama dari tampil, sisip, atau
cari: s
Masukkan nilai untuk disisipkan: 89
Masukkan huruf pertama dari tampil, sisip, atau
cari: t
level=0 anak=0 /50/67/
level=1 anak=0 /30/34/40/
level=1 anak=1 /60/
level=1 anak=2 /70/77/89/
Masukkan huruf pertama dari tampil, sisip, atau
cari: s
Masukkan nilai untuk disisipkan: 68
Masukkan huruf pertama dari tampil, sisip, atau
cari: s
Masukkan nilai untuk disisipkan: 97
Masukkan huruf pertama dari tampil, sisip, atau
cari: t
level=0 anak=0 /67/
level=1 anak=0 /50/
level=2 anak=0 /30/34/40/
level=2 anak=1 /60/
level=1 anak=1 /77/
level=2 anak=0 /68/70/
level=2 anak=1 /89/97/
Masukkan huruf pertama dari tampil, sisip, atau
cari: c
Masukkan nilai yang dicari: 60
ditemukan 60
Masukkan huruf pertama dari tampil, sisip, atau
cari:
Masukkan huruf pertama dari tampil, sisip, atau
cari: t
level=0 anak=0 /50/67/
level=1 anak=0 /30/34/40/
level=1 anak=1 /60/
level=1 anak=2 /70/77/89/
Masukkan huruf pertama dari tampil, sisip, atau
cari: s
Masukkan nilai untuk disisipkan: 68
Masukkan huruf pertama dari tampil, sisip, atau
cari: s
Masukkan nilai untuk disisipkan: 97
Masukkan huruf pertama dari tampil, sisip, atau
cari: t
level=0 anak=0 /67/
level=1 anak=0 /50/
level=2 anak=0 /30/34/40/
level=2 anak=1 /60/
level=1 anak=1 /77/
level=2 anak=0 /68/70/
level=2 anak=1 /89/97/
Masukkan huruf pertama dari tampil, sisip, atau
cari: c
Masukkan nilai yang dicari: 60
ditemukan 60
Masukkan huruf pertama dari tampil, sisip, atau
cari:
3.
Demonstrasikanlah penggunaan dari pohon Splay.
Penyelesaian:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
|
//pohonSplay.cpp
/*
*
Program C++ untuk mengimplementasikan pohon SPlay
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <conio.h>
using namespace std;
struct splay
{
int
kunci;
splay* LAnak;
splay* RAnak;
};
class PohonSplay
{
public:
PohonSplay()
{
}
// RR(Y rotasi ke kanan)
splay* RR_Rotasi(splay* k2)
{
splay* k1 = k2->LAnak;
k2->LAnak = k1->RAnak;
k1->RAnak = k2;
return k1;
}
// LL(Y rotasi ke kiri)
splay* LL_Rotasi(splay* k2)
{
splay* k1 = k2->RAnak;
k2->RAnak = k1->LAnak;
k1->LAnak = k2;
return k1;
}
// implementasi pohon splay top-down
splay* Splay(int kunci, splay* akar)
{
if (!akar)
return NULL;
splay header;
/* header.RAnak menunjuk ke pohon
L;
header.LAnak menunjuk ke pohon R
*/
header.LAnak = header.RAnak = NULL;
splay* PohonLMaks = &header;
splay* PohonRMin = &header;
while (1)
{
if (kunci < akar->kunci)
{
if (!akar->LAnak)
break;
if (kunci < akar->LAnak->kunci)
{
akar =
RR_Rotasi(akar);
// hanya mode
zig-zig perlu dirotasi sekali,
if (!akar->LAnak)
break;
}
/* Link ke pohon R */
PohonRMin->LAnak =
akar;
PohonRMin =
PohonRMin->LAnak;
akar = akar->LAnak;
PohonRMin->LAnak = NULL;
}
else if (kunci >
akar->kunci)
{
if (!akar->RAnak)
break;
if (kunci > akar->RAnak->kunci)
{
akar =
LL_Rotasi(akar);
// hanya mode
zag-zag perlu dirotasi sekali,
if (!akar->RAnak)
break;
}
/* Link ke pohon L */
PohonLMaks->RAnak =
akar;
PohonLMaks =
PohonLMaks->RAnak;
akar = akar->RAnak;
PohonLMaks->RAnak = NULL;
}
else
break;
}
/* merakit pohon L, Pohon Middle,
dan pohon R */
PohonLMaks->RAnak =
akar->LAnak;
PohonRMin->LAnak =
akar->RAnak;
akar->LAnak = header.RAnak;
akar->RAnak = header.LAnak;
return akar;
}
splay* Simpul_Baru(int kunci)
{
splay* simpul_p = new splay;
if (!simpul_p)
{
fprintf(stderr, "Kehabisan memori!\n");
exit(1);
}
simpul_p->kunci = kunci;
simpul_p->LAnak =
simpul_p->RAnak = NULL;
return simpul_p;
}
splay* Sisip(int kunci, splay* akar)
{
static splay* simpul_p = NULL;
if (!simpul_p)
simpul_p =
Simpul_Baru(kunci);
else
simpul_p->kunci = kunci;
if (!akar)
{
akar = simpul_p;
simpul_p = NULL;
return akar;
}
akar = Splay(kunci, akar);
if (kunci < akar->kunci)
{
simpul_p->LAnak =
akar->LAnak;
simpul_p->RAnak = akar;
akar->LAnak = NULL;
akar = simpul_p;
}
else if (kunci >
akar->kunci)
{
simpul_p->RAnak =
akar->RAnak;
simpul_p->LAnak = akar;
akar->RAnak = NULL;
akar = simpul_p;
}
else
return akar;
simpul_p = NULL;
return akar;
}
splay* Hapus(int kunci, splay* akar)
{
splay* temp;
if (!akar)
return NULL;
akar = Splay(kunci, akar);
if (kunci != akar->kunci)
return akar;
else
{
if (!akar->LAnak)
{
temp = akar;
akar = akar->RAnak;
}
else
{
temp = akar;
akar = Splay(kunci,
akar->LAnak);
akar->RAnak =
temp->RAnak;
}
free(temp);
return akar;
}
}
splay* Cari(int kunci, splay* akar)
{
return Splay(kunci, akar);
}
void
InOrder(splay* akar)
{
if (akar)
{
InOrder(akar->LAnak);
cout<< "kunci: " <<akar->kunci;
if(akar->LAnak)
cout<< " | anak kiri: "<< akar->LAnak->kunci;
if(akar->RAnak)
cout << " | anak kanan: " << akar->RAnak->kunci;
cout<< "\n";
InOrder(akar->RAnak);
}
}
};
int main()
{
PohonSplay st;
int
vektor[10] = {9,8,7,6,5,4,3,2,1,0};
splay *akar;
akar = NULL;
const int panjang = 10;
int
i;
for(i
= 0; i < panjang; i++)
akar = st.Sisip(vektor[i], akar);
cout<<"\nInOrder: \n";
st.InOrder(akar);
int
masukan, pilihan;
while(1)
{
cout<<"\nOperasi Pohon Splay \n";
cout<<"1. Sisip "<<endl;
cout<<"2. Hapus"<<endl;
cout<<"3. Cari"<<endl;
cout<<"4. Keluar"<<endl;
cout<<"Masukkan pilihan Anda: ";
cin>>pilihan;
switch(pilihan)
{
case
1:
cout<<"Masukkan nilai yang akan disisipkan:
";
cin>>masukan;
akar = st.Sisip(masukan, akar);
cout<<"\nSetelah Sisip: "<<masukan<<endl;
st.InOrder(akar);
break;
case
2:
cout<<"Masukkan nilai yang akan dihapus: ";
cin>>masukan;
akar = st.Hapus(masukan, akar);
cout<<"\nSetelah Hapus: "<<masukan<<endl;
st.InOrder(akar);
break;
case
3:
cout<<"Masukkan nilai yang akan dicari:
";
cin>>masukan;
akar = st.Cari(masukan, akar);
cout<<"\nSetelah Cari
"<<masukan<<endl;
st.InOrder(akar);
break;
case
4:
exit(1);
default:
cout<<"\nTidak valid! \n";
}
}
cout<<"\n";
getch();
return
0;
}
|
InOrder:
kunci: 0 | anak kanan: 1
kunci: 1 | anak kanan: 2
kunci: 2 | anak kanan: 3
kunci: 3 | anak kanan: 4
kunci: 4 | anak kanan: 5
kunci: 5 | anak kanan: 6
kunci: 6 | anak kanan: 7
kunci: 7 | anak kanan: 8
kunci: 8 | anak kanan: 9
kunci: 9
Operasi Pohon Splay
1. Sisip
2. Hapus
3. Cari
4. Keluar
Masukkan pilihan Anda: 1
Masukkan nilai yang akan disisipkan: 23
Setelah Sisip: 23
kunci: 0
kunci: 1 | anak kiri: 0 | anak kanan: 3
kunci: 2
kunci: 3 | anak kiri: 2 | anak kanan: 5
kunci: 4
kunci: 5 | anak kiri: 4 | anak kanan: 7
kunci: 6
kunci: 7 | anak kiri: 6 | anak kanan: 8
kunci: 8
kunci: 9 | anak kiri: 1
kunci: 23 | anak kiri: 9
Operasi Pohon Splay
1. Sisip
2. Hapus
3. Cari
4. Keluar
Masukkan pilihan Anda: 1
Masukkan nilai yang akan disisipkan: 34
Setelah Sisip: 34
kunci: 0
kunci: 1 | anak kiri: 0 | anak kanan: 3
kunci: 2
kunci: 3 | anak kiri: 2 | anak kanan: 5
kunci: 4
kunci: 5 | anak kiri: 4 | anak kanan: 7
kunci: 6
kunci: 7 | anak kiri: 6 | anak kanan: 8
kunci: 8
kunci: 9 | anak kiri: 1
kunci: 23 | anak kiri: 9
kunci: 34 | anak kiri: 23
Operasi Pohon Splay
1. Sisip
2. Hapus
3. Cari
4. Keluar
Masukkan pilihan Anda: 3
Masukkan nilai yang akan dicari: 34
Setelah Cari 34
kunci: 0
kunci: 1 | anak kiri: 0 | anak kanan: 3
kunci: 2
kunci: 3 | anak kiri: 2 | anak kanan: 5
kunci: 4
kunci: 5 | anak kiri: 4 | anak kanan: 7
kunci: 6
kunci: 7 | anak kiri: 6 | anak kanan: 8
kunci: 8
kunci: 9 | anak kiri: 1
kunci: 23 | anak kiri: 9
kunci: 34 | anak kiri: 23
Operasi Pohon Splay
1. Sisip
2. Hapus
3. Cari
4. Keluar
Masukkan pilihan Anda:
4.
Demonstrasikanlah penggunaan dari pohon AVL.
Penyelesaian:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
|
//pohonAVL
/*
* Program C++ untuk mengimplementasikan
pohon AVL
*/
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<conio.h>
#define pow2(n) (1 << (n))
using namespace std;
/*
* Deklarasi Simpul
*/
struct simpulAVL
{
int
data;
struct
simpulAVL *kiri;
struct
simpulAVL *kanan;
}*akar;
/*
* Deklarasi kelas
*/
class PohonAVL
{
public:
int
tinggi(simpulAVL *);
int
selisih(simpulAVL *);
simpulAVL *rotasi_rr(simpulAVL *);
simpulAVL *rotasi_ll(simpulAVL *);
simpulAVL *rotasi_lr(simpulAVL *);
simpulAVL *rotasi_rl(simpulAVL *);
simpulAVL* setimbang(simpulAVL *);
simpulAVL* sisip(simpulAVL *, int );
void
tampil(simpulAVL *, int);
void
inorder(simpulAVL *);
void
preorder(simpulAVL *);
void
postorder(simpulAVL *);
PohonAVL()
{
akar = NULL;
}
};
/*
* Program penguji
*/
int main()
{
int pilihan, item;
PohonAVL avl;
while (1)
{
cout<<"\n---------------------"<<endl;
cout<<"Implementasi Pohon AVL"<<endl;
cout<<"\n---------------------"<<endl;
cout<<"1.Sisipkan elemen ke dalam pohon"<<endl;
cout<<"2.Tampilkan Pohon AVL Seimbang"<<endl;
cout<<"3.Penjelajahan InOrder"<<endl;
cout<<"4.Penjelajahan PreOrder"<<endl;
cout<<"5.Penjelajahan PostOrder"<<endl;
cout<<"6.Keluar"<<endl;
cout<<"Masukkan pilihan Anda: ";
cin>>pilihan;
switch(pilihan)
{
case
1:
cout<<"Masukkan nilai yang akan disisipkan:
";
cin>>item;
akar = avl.sisip(akar, item);
break;
case
2:
if (akar == NULL)
{
cout<<"Pohon kosong"<<endl;
continue;
}
cout<<"Pohon AVL Seimbang:"<<endl;
avl.tampil(akar, 1);
break;
case
3:
cout<<"Penjelajahan Inorder:"<<endl;
avl.inorder(akar);
cout<<endl;
break;
case
4:
cout<<"Penjelajahan Preorder:"<<endl;
avl.preorder(akar);
cout<<endl;
break;
case
5:
cout<<"Penjelajahan Postorder:"<<endl;
avl.postorder(akar);
cout<<endl;
break;
case
6:
exit(1);
break;
default:
cout<<"Pilihan Salah"<<endl;
}
}
getch();
return
0;
}
/*
* Tinggi Pohon AVL
*/
int PohonAVL::tinggi(simpulAVL *temp)
{
int
h = 0;
if
(temp != NULL)
{
int
tinggiL = tinggi (temp->kiri);
int
tinggiR = tinggi (temp->kanan);
int
tinggiMaks = max (tinggiL, tinggiR);
h = tinggiMaks + 1;
}
return
h;
}
/*
* Selisih tinggi
*/
int PohonAVL::selisih(simpulAVL *temp)
{
int
tinggiL = tinggi (temp->kiri);
int
tinggiR = tinggi (temp->kanan);
int
faktorB= tinggiL - tinggiR;
return
faktorB;
}
/*
* RotasiRR
*/
simpulAVL
*PohonAVL::rotasi_rr(simpulAVL *induk)
{
simpulAVL *temp;
temp = induk->kanan;
induk->kanan = temp->kiri;
temp->kiri = induk;
return
temp;
}
/*
* Rotasi LL
*/
simpulAVL
*PohonAVL::rotasi_ll(simpulAVL *induk)
{
simpulAVL *temp;
temp = induk->kiri;
induk->kiri = temp->kanan;
temp->kanan = induk;
return temp;
}
/*
* Rotasi LR
*/
simpulAVL
*PohonAVL::rotasi_lr(simpulAVL *induk)
{
simpulAVL *temp;
temp = induk->kiri;
induk->kiri = rotasi_rr (temp);
return rotasi_ll (induk);
}
/*
* Rotasi RL
*/
simpulAVL
*PohonAVL::rotasi_rl(simpulAVL *induk)
{
simpulAVL *temp;
temp = induk->kanan;
induk->kanan = rotasi_ll (temp);
return rotasi_rr (induk);
}
/*
* Menyeimbangkan Pohon AVL
*/
simpulAVL
*PohonAVL::setimbang(simpulAVL *temp)
{
int
faktor_seimbang = selisih (temp);
if
(faktor_seimbang > 1)
{
if
(selisih (temp->kiri) > 0)
temp = rotasi_ll (temp);
else
temp = rotasi_lr (temp);
}
else
if (faktor_seimbang < -1)
{
if
(selisih (temp->kanan) > 0)
temp = rotasi_rl (temp);
else
temp = rotasi_rr (temp);
}
return
temp;
}
/*
* Menyisipkan elemen ke dalam pohon
*/
simpulAVL
*PohonAVL::sisip(simpulAVL *akar, int
nilai)
{
if
(akar == NULL)
{
akar = new simpulAVL;
akar->data = nilai;
akar->kiri = NULL;
akar->kanan = NULL;
return akar;
}
else
if (nilai < akar->data)
{
akar->kiri = sisip(akar->kiri,
nilai);
akar = setimbang (akar);
}
else
if (nilai >= akar->data)
{
akar->kanan =
sisip(akar->kanan, nilai);
akar = setimbang (akar);
}
return
akar;
}
/*
* Menampilkan Pohon AVL
*/
void PohonAVL::tampil(simpulAVL *ptr, int level)
{
int
i;
if
(ptr!=NULL)
{
tampil(ptr->kanan, level + 1);
printf("\n");
if
(ptr == akar)
cout<<"Akar -> ";
for
(i = 0; i < level && ptr != akar; i++)
cout<<" ";
cout<<ptr->data;
tampil(ptr->kiri, level + 1);
}
}
/*
* Penjelajahan Inorder atas pohon AVL
*/
void PohonAVL::inorder(simpulAVL *pohon)
{
if (pohon == NULL)
return;
inorder (pohon->kiri);
cout<< pohon->data<<" ";
inorder (pohon->kanan);
}
/*
* Penjelajahan Preorder atas pohon AVL
*/
void PohonAVL::preorder(simpulAVL * pohon)
{
if (pohon == NULL)
return;
cout<< pohon->data<<" ";
preorder (pohon->kiri);
preorder (pohon->kanan);
}
/*
* Penjelajahan Postorder atas pohon AVL
*/
void PohonAVL::postorder(simpulAVL *pohon)
{
if
(pohon == NULL)
return;
postorder (pohon ->kiri );
postorder (pohon ->kanan );
cout<< pohon
->data<<" ";
}
|
---------------------
Implementasi Pohon AVL
---------------------
1.Sisipkan elemen ke dalam pohon
2.Tampilkan Pohon AVL Seimbang
3.Penjelajahan InOrder
4.Penjelajahan PreOrder
5.Penjelajahan PostOrder
6.Keluar
Masukkan pilihan Anda: 1
Masukkan nilai yang akan disisipkan: 23
---------------------
Implementasi Pohon AVL
---------------------
1.Sisipkan elemen ke dalam pohon
2.Tampilkan Pohon AVL Seimbang
3.Penjelajahan InOrder
4.Penjelajahan PreOrder
5.Penjelajahan PostOrder
6.Keluar
Masukkan pilihan Anda: 1
Masukkan nilai yang akan disisipkan: 34
---------------------
Implementasi Pohon AVL
---------------------
1.Sisipkan elemen ke dalam pohon
2.Tampilkan Pohon AVL Seimbang
3.Penjelajahan InOrder
4.Penjelajahan PreOrder
5.Penjelajahan PostOrder
6.Keluar
Masukkan pilihan Anda: 2
Pohon AVL Seimbang:
34
Akar -> 23
---------------------
Implementasi Pohon AVL
---------------------
1.Sisipkan elemen ke dalam pohon
2.Tampilkan Pohon AVL Seimbang
3.Penjelajahan InOrder
4.Penjelajahan PreOrder
5.Penjelajahan PostOrder
6.Keluar
Masukkan pilihan Anda: 1
Masukkan nilai yang akan disisipkan: 45
---------------------
Implementasi Pohon AVL
---------------------
1.Sisipkan elemen ke dalam pohon
2.Tampilkan Pohon AVL Seimbang
3.Penjelajahan InOrder
4.Penjelajahan PreOrder
5.Penjelajahan PostOrder
6.Keluar
Masukkan pilihan Anda: 3
Penjelajahan Inorder:
23
34 45
---------------------
Implementasi Pohon AVL
---------------------
1.Sisipkan elemen ke dalam pohon
2.Tampilkan Pohon AVL Seimbang
3.Penjelajahan InOrder
4.Penjelajahan PreOrder
5.Penjelajahan PostOrder
6.Keluar
Masukkan pilihan Anda: 4
Penjelajahan Preorder:
34
23 45
---------------------
Implementasi Pohon AVL
---------------------
1.Sisipkan elemen ke dalam pohon
2.Tampilkan Pohon AVL Seimbang
3.Penjelajahan InOrder
4.Penjelajahan PreOrder
5.Penjelajahan PostOrder
6.Keluar
Masukkan pilihan Anda: 5
Penjelajahan Postorder:
23
45 34
---------------------
Implementasi Pohon AVL
---------------------
1.Sisipkan elemen ke dalam pohon
2.Tampilkan Pohon AVL Seimbang
3.Penjelajahan InOrder
4.Penjelajahan PreOrder
5.Penjelajahan PostOrder
6.Keluar
Masukkan pilihan Anda:
No comments:
Post a Comment