bahan kuliah struktur data
DESCRIPTION
bahan kuliah struktur dataTRANSCRIPT
Halaman 1
STRUKTUR DATASTRUKTUR DATA
PengajarPengajarJaidanJaidan JauhariJauhari, MT, MT
AlamatAlamat [email protected][email protected]
[email protected][email protected]
DisarikanDisarikan Dari Dari BerbagaiBerbagai SumberSumber, , TerutamaTerutama Dari Diktat Dari Diktat StrukturStruktur Data Data InformatikaInformatikaITB ITB KaranganKarangan Dr. Dr. InggrianiInggriani LiemLiem
Halaman 2
SILABUS MATERI KULIAHSILABUS MATERI KULIAH
Pengantar Struktur DataReview Record dan ArrayStack (Tumpukan)Queue (Antrian)Linked List dan Variasi ListMultiListPohon BinerGraph
Halaman 3
BUKU SUMBERBUKU SUMBER1. Inggriani Liem. 1997. Diktat Kuliah Algoritma dan
Pemrograman Prosedural. Bandung : ITB2. Inggriani Liem. 2003. Diktat Kuliah Struktur Data.
Bandung : ITB3. Rinaldi Munir. 2003. Algoritma dan Pemrograman II.
Bandung : Penerbit Informatika4. Bambang Wahyudi. 2004. Struktur Data dan Algoritma.
Yogyakarta : Andi Offset5. Dwi Sanjaya. 2001. Bertualang dengan Struktur Data di
Planet Pascal. Yogyakarta : JJ Learning6. P. Insap Santoso.1997. Struktur Data dengan Turbo
Pascal. Yogyakarta : Andi Offset
Halaman 4
KomponenKomponen PenilaianPenilaian
Tugas 20%Ujian 1 20 % (Pertemuan ke-4)Ujian 2 20% (Pertemuan ke-8)Ujian 3 20% (Pertemuan ke-12)Ujian Akhir Semester 20%
Halaman 5
AturanAturan dandan SanksiSanksi--sanksisanksiKehadiran minimal 80%, kurang dari 80% tidak lulus (mendapat nilai E)Keterlambatan maksimal 10 menit (Lebih dari 10 menit tidakdiijinkan memasuki ruangan)Pengumpulan Tugas yang melebihi waktu yang telah ditentukanakan diberikan nilai nolKecurangan dalam bentuk apapun akan mendapatkan nilai EMahasiswa berpakaian rapi dan sopan, yang ditunjukkan antara lain 1. Memakai sepatu tertutup2. Memakai baju berkerah3. Tidak memakai aksesoris yang tidak diijinkan4. Tidak memakai pakaian yang kurang dasar atau lebih dasar5. dan lain-lainSelama perkuliahan berlangsung mahasiswa tidak diijinkanmeninggalkan ruang kuliah kecuali sangat terpaksa dan itupunharus membuat surat ijin dan hanya boleh satu kali
Halaman 6
PENGERTIAN STRUKTURPENGERTIAN STRUKTUR DATADATA
Struktur data adalah cara menyimpan ataumerepresentasikan data di dalam komputer agar bisa dipakai secara efisien
Sedangkan data adalah representasi dari fakta dunianyata.
Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalambentuk tulisan, suara, gambar, sinyal atausimbol
Halaman 7
Secara garis besar type data dapat dikategorikanmenjadi :1. Type data sederhana
a. Type data sederhana tunggal, misalnyaInteger, real, boolean dan karakter
b. Type data sederhana majemuk, misalnyaString
2. Struktur Data, meliputia. Struktur data sederhana, misalnya array dan
record
Halaman 8
b. Struktur data majemuk, yang terdiridariLinier : Stack, Queue, serta List dan
MultilistNon Linier : Pohon Biner dan Graph
Pemakaian struktur data yang tepat di dalamproses pemrograman akan menghasilkanalgoritma yang lebih jelas dan tepat, sehingga menjadikan program secarakeseluruhan lebih efisien dan sederhana.
Halaman 9
Struktur data yang ″standar″ yang biasanyadigunakan dibidang informatika adalah :
List linier (Linked List) dan variasinyaMultilistStack (Tumpukan)Queue (Antrian) Tree ( Pohon ) Graph ( Graf )
Halaman 10
REVIEW RECORD (REKAMAN)REVIEW RECORD (REKAMAN)
Disusun oleh satu atau lebih field. Tiap field menyimpan data dari tipe dasar tertentu atau dari tipe bentukan lain yang sudah didefinisikan sebelumnya. Nama rekaman ditentukan oleh pemrogram.
Rekaman disebut juga tipe terstruktur.
Contoh :1. type Titik : record <x : real, y : real>
jika P dideklarasikan sebagai Titik maka mengacu field pada P adalah P.x dan P.y.
Halaman 11
2. Didefinisikan tipe terstruktur yang mewakili Jam yang dinyatakan sebagai jam (hh), menit (mm) dan detik (ss), maka cara menulis type Jam adalah :type JAM : record
<hh : integer, {0…23}mm : integer, {0…59}ss : integer {0…59}
>Jika J adalah peubah (variabel) bertipe Jammaka cara mengacu tiap field adalah J.hh, J.mmdan J.ss
Halaman 12
Terjemahan dalam bahasa C :1. type Titik : record <x : real, y : real>
diterjemahkan menjadi :typedef struct { float x;
float y;} Titik;
2. type JAM : record<hh : integer, {0…23}mm : integer, {0…59}
ss : integer {0…59}>
Diterjemahkan menjadi :typedef struct
{ int hh; /*0…23*/int mm; /*0…59*/int ss; /*0…59*/} Jam;
Halaman 13
REVIEW ARRAY (LARIK)REVIEW ARRAY (LARIK)
1. PendahuluanLarik adalah struktur data statik yang menyimpan sekumpulan elemen yang bertipe sama.Setiap elemen diakses langsung melalui indeksnya. Indeks larik harus tipe data yang menyatakan keterurutan misalnya integer atau karakter.
Halaman 14
Banyaknya elemen larik harus sudah diketahui sebelum program dieksekusi.Tipe elemen larik dapat berupa tipe sederhana, tipe terstruktur atau tipe larik lain.Nama lain array adalah Larik, tabel atau vektor
Halaman 15
Cara Pendefinisian Array1. Sebagai Peubah
Contoh :L : array[1..50] of integerNamaMhs : array[‘a’..’j’] of string
2. Sebagai tipe baruContoh :type LarikInt : array[1..100] of integerP : LarikInt
Halaman 16
3. Mendefinisikan ukuran maksimum elemen larik sebagai konstantaContoh :Const Nmaks = 100 type Larikint : array[1..Nmaks] of integerP : LarikInt
Cara menterjemahkan ke bahasa C :#define Nmaks 100typedef int Larikint[Nmaks+1];Larikint P;
Halaman 17
Cara Mengacu Elemen Larik
Elemen larik diacu melalui indeksnya. Nilai indek harus terdefinisi.
Contoh cara mengacu elemen larik adalah :L[4] {mengacu elemen keempat dari larik L }
NamaMhs[‘b’] {mengacu elemen kedua dari larik NamaMhs}
P[k] {mengacu elemen ke-k dari larik P, asalkan nilai k sudah terdefinisi }
Halaman 18
Menginisialisasi Larik
menginisialisasi elemen larik adalah memberikanharga awal untuk seluruh elemen larik, misalnyamenginisialisasi dengan nilai 0 seperti di bawah ini :Procedure InisDgn0(output A:larik, input N:integer){menginisialisasi setiap elemen larik A[1..N] dengan nol} {K. Awal : N adalah banyak elemen efektif larik,
nilainya terdefinisi}{K. Akhir : seluruh elemen larik A bernilai nol}Deklarasi :
K : integerDeskripsi :
for k 1 to N doA[k] 0
endfor
Halaman 19
Mengisi elemen larik dari piranti masukan
Elemen larik dapat diisi dengan nilai yang dibaca dari piranti masukan seperti contoh di bawah ini :Procedure BacaLarik(output A:larik, input N:integer){mengisi elemen larik A[1..N] dengan nilai yang
dibaca dari piranti masukan} {K. Awal : N adalah jumlah elemen efektif larik, nilainya
terdefinisi}{K. Akhir : seluruh elemen larik A berisi nilai-nilai yang dibaca dari
piranti masukan}Deklarasi :
K : integerDeskripsi :
for k 1 to N doread (A[k])
endfor
Halaman 20
Larik Bertype Terstruktur
Larik tidak hanya dapat berisi data bertype tunggal, tapi dapat juga berisi data yang bertipeterstruktur
Contoh :const Nmaks = 100type Mahasiswa : record
<nim : integer,nama_mhs : string,KodeMK : string,Nilai : char >
TabMhs : array[1..Nmaks] of Mahasiswa
Halaman 21
Contoh Cara mengacu elemen TabMhs :1. TabMhs[2].Nim
mengacu field Nim dari elemen kedualarik
2. Write(TabMhs[k].KodeMK)menuliskan field KodeMK dari elemenke k dari larik
Halaman 22
TugasTugas 11
Buatlah dalam notasi algoritma atau bahasa C :1.Definisikan sebuah type terstruktur untuk
menyatakan data nasabah disebuah bank. Data nasabah terdiri atas field Nomor Account, NamaNasabah, Alamat Nasabah, Kota Nasabah, danNomor Telpon Nasabah.Untuk setiap field definisikan type data yang cocok
Halaman 23
2.Dari soal nomor 1 buatlah program dalambahasa pemrograman berbasis bahasa C, untukmemasukkan data nasabah sebanyak N, denganN diinputkan dari papan ketik, kemudianmenuliskan kembali semua data nasabah dalambentuk matrik.Petunjuk :
Gunakan notasi pengulangan untukmenyelesaikan permasalahan tersebut
Tugas dikumpulkan pada pertemuanberikutnya disertai listing program dancontoh keluarannya
Halaman 24
ADT (Abstract Data Type)ADT (Abstract Data Type)ADT adalah definisi type dan sekumpulanprimitif (operasi dasar) terhadap type tersebut.Type diterjemahkan menjadi type terdefinisidalam bahasa pemrograman yang bersangkutan, misalnya menjadi record dalamPascal/Ada dan Struct dalam bahasa C
Halaman 25
Primitif dalam konteks pemrogramanprosedural, diterjemahkan menjadifungsi dan prosedur.
Primitif dikelompokkan menjadi :1. Konstruktor/Kreator, pembentuk nilai
type. Biasanya namanya diawali denganMake.
2. Selektor, untuk mengakses komponen type. Biasanya namanya diawali denganGet.
Halaman 26
3. Prosedur Pengubah nilai komponen4. Validator komponen type, yang
dipakai untuk mengetes apakah dapatmembentuk type sesuai batasan.
5. Destruktor/Dealokator, yaitu untukmenghancurkan nilai objek, sekaligusmemori penyimpannya
6. Baca/tulis, untuk interface denganinput/output device
Halaman 27
7. Operator Relasional terhadap type tersebut untuk mendefinisikan lebihbesar, lebih kecil, sama dengan dansebagainya.
8. Aritmatika terhadap type tersebut, dalam pemrograman biasanya hanyaterdefinisi untuk bilangan numerik.
9. Konversi dari type tersebut ke type dasar dan sebaliknya
Halaman 28
ADT biasanya diimplementasi menjadi dua buahmodul, yaitu :1. Definisi/spesifikasi type dan primitif
- Spesifikasi type sesuai denganbahasa yang dipakai
- Spesifikasi dari primitif sesuai dengan kaidahdalam konteks prosedural, yaitu :a. Fungsi : nama, domain, range, dan pre kondisi
jika adab. Prosedur : Keadaan Awal, Keadaan Akhir dan
proses yang dilakukan2. Body/realisasi dari primitif, berupa kode program dalam
bahasa yang bersangkutan. Realisasi fungsi dan prosedurharus sedapat mungkin memanfaatkan Selektor danKonstruktor
Halaman 29
Halaman 30
4. Linked List (List Linier)4. Linked List (List Linier)4.1. DefinisiList linier adalah sekumpulan elemen
bertype sama, yang mempunyaiketerurutan tertentu, yang setiapelemennya terdiri dari 2 bagian :
Type Elmtlist = record< Info : InfoType,
Next : address >
Halaman 31
Dengan Info Type adalah sebuah type terdefenisi yang menyimpan informasisebuah elemen list ; Next adalah address dari elemen berikutnya ( suksesor ).
Dengan demikian, jika didefinisikan First adalah alamt elemen pertama list, makaelemen berikutnya dapat diakses secarasuksesif dari elemen pertama tersebut
Halaman 32
Jadi, sebuah list linier dikenali :elemen pertamanya, biasanya melalui alamatelemen pertama yang disebut : Firstalamat elemen berikutnya ( suksesor ), jikakita mengetahui alamat sebuah elemen , yang dapat diakses melalui field NEXTsetiap elemen mempunyai alamat, yaitutempat elemen disimpan dapat diacu.Untukmengacu sebuah elemen , alamat harusterdefenisi . Dengan alamat tersebut Informasiyang tersimpan pada elemen list dapat diakses. elemen terakhirnya. Ada berbagai cara untukmengenali elemen akhir
Halaman 33
Jika L adalah list , dan P adalah address :Alamat elemen pertama list L dapat diacudengan notasi :
First (L)Elemen yang diacu oleh P dapat dikonsultasiinformasinya dengan notasi :
Info(P)Next(P)
Halaman 34
Beberapa defenisi :1. List L adalah List kosong , jika First (L) = Nil2. Elemen terakhir dikenali, dengan salah satu
cara adalah karena Next(Last) =Nil
Halaman 35
II. Skema traversal untuk list linierList terdiri dari sekumpulan elemen. Seringkali diperlukan untuk memprosessetiap elemen list dengan cara yang sama. Karena itu salah primitif operasi konsultasidasar pada struktur list adalah traversal, yaitu “mengunjungi” setiap elemen list untuk diproses.
Halaman 36
Karena Urutan akses adalah dari elemenpertama sampai dengan elementerakhir, maka traversal list secaranatural dilakukan dari elemen pertama, suksesornya, dan seterusnya sampaidengan elemen terakhir.
Halaman 37
Skema traversal yang dipakai adalah Sbb :
Procedure SKEMAListTransversal1( Input L : List ) {K. Awal : List L terdefinisi , mungkin kosong }{K. Akhir : semua elemen list L dikunjungi dan telah
diproses }{Proses : Traversal sebuah list linier. Dengan MARK,
tanpa pemrosesan khusus pada list kosong}
Deklarasi
Halaman 38
Deklarasi :P : address { address untuk traversal , type
terdefenisi }Deskripsi :
InisialisasiP ← First ( L ) { First Element } While ( P ≠Nil ) do
Proses ( P )P ← Next ( P ) { Next element }
endwhileTerminasi
Halaman 39
Procedure SKEMAListTransversal 2( Input L : List )
{ K. Awal : List L terdefenisi , mungkin kosong } { K. Akhir : semua elemen list L “dikunjungan “
dan telah diproses }{ Proses : Transversal sebuah list linier yang
diidentifikasi oleh elemen pertama L , Dengan MARK dan pemrosesankhusus pada list kosong }
Deklarasi :
Halaman 40
DeklarasiP : address { address untuk traversal , type
terdefenisi }Deskripsi
If (First ( L ) = Nil) then Write ( ‘List kosong ‘ )
else
Halaman 41
InsialisasiP ← First ( L ) { First Element }Repeat
Proses ( P )P ← Next ( P ) { Next element }
until P=NilTerminasi
Halaman 42
III. Skema Sequential Search untuk list linier Selain traversal, proses pencarian suatu elemenlist adalah primitif yang sering kali didefinisikan pada struktur list. Pencariandapat berdasarkan nilai, atau berdasarkanalamat.
III.1. Search suatu Nilai, output adalah addressSearch ini sering dipakai untuk mengenalisuatu elemen list berdasarkan nilai informasiyang disimpan pada elemen yang dicari. Biasanya dengan alamat yang ditemukan, akan dilakukan suatu proses terhadap elemenlist tersebut.
Halaman 43
Procedure SKEMAListSearch1 ( Input L : List, X : InfoType, Output P : address, Found: Boolean )
{ K. Awal : List linier L sudah terdefinisi dan siapdikonsultasi, X terdefenisi }
{ K.Akhir : P : address pada pencarian beurutan, dimana X diketemukan, P = Nil jikatidak ketemu, Found berharga true jikaharga X yang dicari ketemu, false jikatidak }
Halaman 44
{Proses : Sequential Search harga X pada sebuahlist linier L, Semua elemen diperiksa
dengan intruksi yang sama, versidengan Boolean}
Deklarasi
Deskripsi
Halaman 45
P ← First ( L )Found ← falseWhile ( P ≠ Nil ) and ( not found ) do
if X = Info (P) thenFound ←True
else P ← Next (P)
endifendwhile { P = Nil or Found}{Jika Found maka P adalah address dimana
harga yang dicari diketemukan}
Halaman 46
III. 2. Search suatu Elemen yang beralamat tertentu
Procedure SKEMAList Search@( Input L : List, P : address, Found: Boolean )
{K. Awal : List linier L sudah terdefinisi dan siapdikonsultasi, X terdefenisi }
{K.Akhir : Jika ada elemen list beralamat P, Found berharga true, Jika tidak ada elemen list beralamat P, Found berharga false }
{Proses : Sequential Search @ P pada sebuah list linier L, Semua elemen diperiksa dengan intruksiyang sama }
Halaman 47
DeklarasiPt : address
DeskripsiPt ← First ( L )Found ← falseWhile ( Pt ≠ Nil ) and ( not found ) do
if Pt = P thenFound ← true
else Pt ← Next (Pt)
endifendwhile { Pt = Nil or Found}{ Jika Found maka P adalah elemen list}
Halaman 48
IV. Definisi fungsional list linier danalgoritmanyaSecara fungsional, pada sebuah list linier biasanya dilakukan pembuatan,
penambahan atau penghapusan elemen yang dapat ditulis sebagai berkut :
Jika diberikan L, L1 dan L2 adalah list linier dengan elemen ElmtList, makaoperasi yang dapat dilakukan :
ListEmpty, CreateList, Insert, Delete, Concat dan UpdateList
Halaman 49
IV. 1. Pengetesan List KosongPemeriksaan apakah sebuah list kosong sangat
penting, karena Keadaan Awal danKeadaan Akhir beberapa prosedur harusdidefinisikan berdasarkan keadaan list. Operasi pada list kosong sering kali membutuhkan penanganan khususRealisasi algoritmik dari definisifungsional ini adalah sebuah fungsisebagai berikut.
Halaman 50
Function IsEmptyList (L : List ) → boolean{ Test apakah sebuah list L kosong,
Mengirimkan true jika list kosong, falsejika tidak kosong}
DeklarasiDeskripsi
return(First (L) = Nil)
Halaman 51
IV.2 Pembuatan sebuah elemen padalist linier
Pembuatan sebuah list berarti membuatsebuat list KOSONG, yang selanjutnyasiap diproses (ditambah elemennya, dsb). Realisasi algoritmik daridefenisi funfsional ini adalah sebuahprosedur sebagai berikut.
Halaman 52
Procedure CreateList( Output L : List ){K. Awal : Sembarang }K. Akhir : terbentuk list L yang kosong : First
(L) diinisialisasi dengan NIL )Proses : Membuat list kosong}
DeklarasiDeskripsi
First (L) ← Nil
Halaman 53
IV. 3 Penyisipan sebuah elemenpada list linier
Fungsi insert (penyisipan) harus dijabarkan lebihrinci, karena dapat menjadi penyisipan sebagaielemen pertama, setelah sebuah address P ataupenyisipan menjadi elemen terakhir ataubahkan menjadi elemen ditengah
Penyisipan sebuah elemen dapat dilakukanterhadap sebuah elemen yang sudah dialokasi(diketahui address-nya ), atau sebuah elemenyang hanya diketahui nilai Info-nya (berartibelum dialokasi).
Halaman 54
IV. 2.1. INSERT-First (Address)Menambahkan sebuah elemen yang diketahui
alamatnya sebagai elemen pertama list.Procedure InsertFirst (Input/Output L:List, Input
P: address){K. Awal : List L mungkin kosong{K. Akhir : P adalah elemen pertama list L}{Proses : Insert sebuah elemen beralamat P sebagai
elemen pertama list linier L yang mungkinkosong}
DeklarasiDeskripsi
Next (P) ← First (L)First (L) ← P
Halaman 55
IV.2.2 INSERT-First (Nilai)Menambahkan sebuah elemen yang diketahui nilainya sebagai elemen pertama
list.
Procedure InsFirst (Input/output L :List, Input E : infotype ){ K. Awal : List L mungkin kosong }{ K. Akhir : Sebuah elemen dialokasikan dan menjadi elemen
pertama list L, jika alokasi berhasil. Jika alokasi gagallist tetap seperti semula }
{ Proses : Insert sebuah elemen sebagai elemen pertama list} Deklarasi
P : addressDeskripsi
Alokasi (P)If P ≠ Nil then
Info (P) ← ENext (P) ← First (L) First (L) ← P
Halaman 56
IV.2.2. INSERT-AFTER Menyisipkan sebuah elemen beralamat P sebagai
suksesor dari sebuah elemen list linier yang beralamatPrec
Procedure InsertAfter ( Input P, Prec: address ){K. Awal : Prec adalah elemen list, prec ≠ Nil, P sudah
dialokasikan, P ≠ Nil, Next (P) = NilK. Akhir : P menjadi suksesor PrecProses : Insert sebuah elemen beralamat P pada List
linier L}DeklarasiDeskripsi
Next (P) ← Next (Prec) Next (Prec) ← P
Halaman 57
IV. 2.3. INSERT – LastMenyisipkan sebuah elemen beralamat P sebagai elemen
terakhir sebuah list linier. Ada dua kemungkinan list kosong atau tidak kosong
Procedur InsertLast@(Input/Output L: List, Input P : address)
{K. Awal : List L mungkin kosong, P sudah dialokasi, P ≠ Nil, Next (P) = Nil
K. Akhir : P adalah elemen terakhir list LProses : Insert sebuah elemen beralamat P sbg elemen
terakhir dari list linier L yg mungkin kosong }
Halaman 58
DeklarasiLast : address { address untuk traversal}
DeskripsiIf Fisrt (L) = Nil then { insert sebagai elemen pertama}
InsertFirst(L, P)Else{ Traversal list sampai address terakhir}
Last ← First (L)While (Next (Last ) ≠ Nil ) do
Last ← Next (Last )endwhile {Next ( Last) = Nil, Last adalah elemen terakhir;
insert P after last }InsertAfter (P, Last)
endif
Halaman 59
Procedure InsertLast(Input/output L :List, Input E : Infotype){ K. Awal : List L mungkin kosong, P sudah dialokasi,
P ≠ Nil, Next(P)=Nil K. Akhir : P adalah elemen terakhir list L Proses : Insert sebuah elemen beralamat P sebagai
elemen terakhir dari list linier L yang mungkinkosong }
DeklarasiLast : address { address untuk traversal }
DeskripsiAlokasi (P) If (P ≠ Nil) then
Info(P) ←EInsertLast@(L,P)
Halaman 60
IV.3. Penghapusan sebuah elemen pada list linier
Penghapusan harus dijabarkan lebih rinci, Karenapenghapusan elemen dapat merupakanpertama, setelah sebuah address P ataupenghapusan elemen terakhir. Perbedaan inimelehirkan 3 operasi dasar penghapusanelemen list yang diturunkan dari definisifungsional inimenjadi realisasi algoritma.
Operasi penghapusan dapat mengakibatkan list kosong, jika list semula hanya terdiri dari satuelemen.
Halaman 61
IV.3.1. DELETFirst : menghapus elemen pertamalist linier
a. Elemen yang dihapus dicatat alamatnyaProcedure DeleteFirst@ (Input/Output L : List, Output
P : address){K. Awal : List L tidak kosong, minimal 1 elemen
pertama pasti ada }{K. Akhir : menghapus elemen pertama L
P adalah @ elemen pertama L sebelumpenghapusan, L yang baru adalah Next (L)
DeklarasiDeskripsi
P ← First (L) First (L) ← Next ( First (L) )
Halaman 62
Procedure DeleteFirst (Input/Output L : List, Output E : InfoType)
{K. Awal : List L tidak kosong, minimal 1 elemenpertama pasti ada }
{K. Akhir : menghapus elemen pertama LE adalah Nilai elemen pertama L sebelumpenghapusan, L yang baru adalah Next (L)
DeklarasiDeskripsi
P ← First (L) E ← Info (P)First (L) ← Next ( First (L) ) Dealokasi (P)
Halaman 63
IV. 3.2. Delete After :Penghapusan suksesor sebuah elemen :Procedure DeleteAfter ( Input Prec : adrress, Output
P : address ){ K. Awal : List tidak kosong, Prec adalah elemen list
, Next (Prec) ≠ Nil } Prec ≠elemen terakhirK. Akhir : Menghapus suksesor Prec, P adalah @
suksesor Prec sebelum penghapusan, Next (Prec) yang baru adalah suksesor darisuksesor Prec sebelum penghapusan }
DeklarasiDeskripsi
P ← Next (Prec)Next (Prec) ← Next (Next (Prec))
Halaman 64
Dengan primitip ini, maka penghapusan sebuahberalamat P dapat dilakukan dengan : mencaripredesesor dari P, yaitu alamat Prec memakaiDeleteAfter (Prec)
Procedure DeleteP ( Input/Output L ; List, OutputP : address )
{ K. Awal : List L tidak kosong , P adalah elemen list L K. Akhir : Menghapus P dari list, P mungkin
elemen pertama, “tengah” atau terakhir }Deklarasi
Prec : address { alamat predesesor } Deskripsi
Halaman 65
{ Cari predesesor P }if (P = First (L) then {Delete list dengan
satu elemen }DeleteFirst (L,P)
elsePrec ← First (L) While (Next(Prec) ≠ P ) do
Prec ← Next (Prec)endwhile { Next (Prec) = P , hapus P }DeleteAfter (Prec , P)
endif
Halaman 66
IV. 3.3. DELETELast :Menghapus elemen terakhir list dapat dilakukan jika
alamat dari elemen sebelum elemen terakhirdiketahui. Persoalan selanjutnya menjadi persoalanDeleteAfter, kalau last bukan satu- satunya elemenlist linier. Ada dua kasus, yaitu list menjadi kosongatau tidak.
Procedure DeleteLast (Input L : List, Output P : address)
{K. Awal : List L tidak kosong, minimal mengandung1 elemen
K. Akhir : menghapus elemen terakhir dari list, list mungkin menjadi kosong
Proses : P adalah alamat elemen terakhir list sebelum penghapusan }
Halaman 67
DeklarasiLast , preclast :address { address untuk traversal }
Deskripsi{ Find last dan address sebelum last }Last ← First (L) Preclast ← Nil { predesesor dari L tak terdefenisi }While ( Next ( Last ) ≠ Nil do { Traversal list sampai @ terakhir}
Preclast ← Last ; Last ← Next ( last )endwhile { Next ( Last ) = Nil, Last adalah elemen terakhir;
preclast = sebelum last } P ← LastIf Preclast = Nil then { list dg 1 elemen, jadi kosong }
First(L) ← Nil Else
Next ( preclast )← Nil endif
Halaman 68
IV. 5. Konkatenasi dua buah list linierConcat adalah menggabungkan dua list. Dalam contoh
berikut list kedua disambungkan ke list pertama. JadiLast (L1) menjadi predesesor First (L2). Realisasialgoritma adalah sebuah prosedur sebagai berikut :
Procedure CONCAT (Input L1, L2 : List, Output : L3 : List )
{K. awal : L1 ≠ L2, L1 ≠ L3,dan L3 ≠ L2; L1, L2 mungkin kosong
K. Akhir : L3 adalah hasil konkatenasi (menyambung) dua buah list linier, L2 ditaruh dibelakangL1 }
Halaman 69
DeklarasiLast1 : address { alamat elemen terakhir list pertama }
DeskripsiCratelist (L3) {inisialisasi list hasil }If Fist (L1) = Nil then
First (L3) ← First (L2)Else { Traversal list 1 sampai address terakhir,
Hubungkan last dengan Fisrt 2}First (L3) ← First (L1)Last1 ← First (L1) While ( Next (Last 1 ) ≠ Nil ) do
Last1 ← Next (Last 1) endwhile {Next ( Last 1) ← First (L2)}
Next(Last1) ← First (L2)}endif
Halaman 70
Bagian Deklarasi dari algoritma pada List Linier :Deklarasi
type InfoType = … {Sebuah type terdefinisi}type Address pointer to ElmtLtype ElmtL = record
<Info : InfoType,Next : Address >
type List = record <First : Address >{Deklarasi Nama Peubah}
L : ListP : Address
Halaman 71
SoalSoal--SoalSoal LatihanLatihanI. Apakah perbedaan struktur data list linier
ditinjau dari sudut pandang operasinya, jikadibandingkan dengan struktur data stack dan queue?
II. Untuk data yang bagaimanakah yang dapatdirepresentasikan dengan menggunakanstruktur data list linier?
III. Diketahui sebuah list linier dengan elemenbertipe integer, buatlah :1. Sebuah prosedur untuk menghitung
jumlah elemen list yang genap2. Prosedur untuk menghitung rata-rata
elemen list yang ganjil
Halaman 72
3. Prosedur untuk menghitung banyaknyaelemen list yang positif (lebih besar darinol)
4. Prosedur untuk mencetak elemen list yang genap
IV. Diketahui sebuah list dengan elemen bertypeinteger terurut membesar, buatlah :
1. Fungsi untuk mengirimkan elemen pertamalist
2. Fungsi untuk mencari elemen list yang minimum
3. Fungsi untuk menghitung banyaknyaelemen yang lebih besar dari 100
Halaman 73
Halaman 74
5. Stack (5. Stack (TumpukanTumpukan))5.1. DefinisiSTACK (Tumpukan) adalah list linier yang : 1. Dikenali elemen puncaknya (TOP)2. Aturan penyisipan dan penghapusan
elemennya tertentu :-Penyisipan selalu dilakukan “di atas “ TOP-Penghapusan selalu dilakukan pada TOP
Halaman 75
Karena aturan penyisipan dan penghapusan semacamitu, TOP adalah satu-satunya alamat tempat terjadioperasi. Elemen yang ditambahkan paling akhir akanmenjadi elemen yang akan dihapus.Dikatakanbahwa elemen Stack akan tersusun secara LIFO
(Last In First Out).Maka secara lojik, sebuah STACK dapat
digambarkan sebagai list linier yang setiapelemennya adalah
Type ElmtS = record<Info : InfoType,
Next : address >
Halaman 76
dengan InfoType terdefinisi yang menentukaninformasi yang disimpan pada setiapelemen stack, dan address adalah“alamat” dari elemen
Selain itu alamat elemen terbaru (TOP) dicatat, sedangkan alamat elemen yang paling “bawah”, yaitu yang paling lama biasanyadiebut BOTTOM.
TOP adalah elemen pertama list, supayapenambahan dan penghapusan denganmudah dan efisien dapat dilakukan.
Halaman 77
Sehingga jika S adalah sebuah Stack, dan P adalah address makaTop (S) adalah alamat elemen TOP, dimanaoperasi penyisipan/penghapusan dilakukan.Info (P) adalah informasi yang disimpan padaalamat PNext (P) adalah alamat suksesor PElmtS (P) adalah sebuah elemen stack yang beralamat P Stack kosong adalah Stack dengan Top (S) = Nil ( tidak terdefinisi )
Halaman 78
Bagian Deklarasi dari algoritma pada Stack :Deklarasi
type InfoType = … {Sebuah type terdefinisi}type Address pointer to ElmtStype ElmtS = record
<Info : InfoType,Next : Address >
type Stack = record <TOP : Address>{Deklarasi Nama Peubah}
S : StackP : Address
Halaman 79
Pada stack, jarang sekali dilakukantraversal, karena keunikan Stack justrupada operasi yang hanya menyangkutelemen TOP. Namun dibutuhkantraversal misalnya untuk mencetak isiStack.
5.3. Search pada StackPada stack, elemen yang diproses hanyalah
elemen pada TOP. Maka hampir tidak pernahdilakukan search.
5.2. Traversal 5.2. Traversal padapada StackStack
Halaman 80
5.4. 5.4. OperasiOperasi dandan fungsifungsi dasardasarpadapada STACK.STACK.
a. Test STACK kosongMengetahui bahwa stack kosong atautidak sangat penting, sebab semua operasiakan dilakukan berdasarkan kosong atautidaknya suatu Stack. Realisasi algoritmadari definisi fungsional ini adalah sebuahfungsi yang melakukan test terhadap Stack sebagai berikut :
Halaman 81
function StackEmpty (S : STACK) →Boolean
{ TEST stack kosong : Mengirim true, jikatumpukan kosong, false jika tumpukan tidakkosong}
Deklarasi
Deskripsireturn (Top (S) = Nil)
Halaman 82
b. Pembuatan STACK kosongMembuat Stack kosong diperlukan untuk memulaimemakai stack. Realisasi algoritma dari definisifungsional ini adalah sebuah prosedur yang melakukan inisialisasi stack sebagai berikut
Procedure CreateEmptyS (Output S : STACK){K. Awal : sembarang, K. Akhir : sebuah stack S yang kosong siap dipakai
terdefinisiProses : Membuat stack kosong }
DeklarasiDeskripsi
Top (S) ← Nil
Halaman 83
c.Penambahan sebuah elemen padaSTACK (Push)Penambahan selalu dilakukan pada TOP, dankarena alamat TOP diketahui maka prosesnyasederhana. Berikut ini akan diberikan skemaprosedur penyisipan tersebut. Realisasi algoritmadari definisi fungsional ini adalah salah satu daridua buah prosedur yang melakukan penambahanelemen stack sebagai berikut. Prosedur pertamamenambahkan suatu ElmtS yang diketahuialamatnya dan yang kedua menambahkan suatunilai ElmtS yang diberikan.
Halaman 84
procedure Push@ (Input/Output S : STACK Input P : address)
{Menambahkan sebuah elemen baru pada TOP sebuahstack, dengan elemen yang diketahui alamatnya}
{K.Awal : Stack mungkin kosong, P terdefinisi (berartiterdefinisi informasinya, Next (P) = Nil}
{K.Akhir : Top (S) adalah P}DeklarasiDeskripsi
{ insert sebagai elemen pertama }Next (P) ← TOP (S)TOP (S) ← P
Halaman 85
procedure Push( Input / Output S:STACK Input E: InfoType ){ Menambahkan sebuah elemen baru pada TOP sebuah stack,
dengan elemen yang diketahui informasinya }{ K. Awal : Stack mungkin kosong , E terdefenisi , alokasi alamat
selalu berhasil } { K. Akhir : TOP (S) berisi E )Deklarasi
P : addressDeskripsi
Alokasi ( P ) { alokasi selau berhasil }Info(P) ← E { insert sebagai elemen pertama }Next(P) ← TOP(S) TOP(S) ← P
Halaman 86
d. Penghapusan sebuah elemen padaSTACK (Pop)Penghapusan elemen Stack selalu dilakukan padaTOP , hanya saja harus diperhitungkan bahwamugkin Stack akan menjadi kosong akibatterjadinya penghapusan. Jika Stack menjadikosong , maka harga TOP harus diganti . Realisasialgoritma dari definisi funsional ini adalah salahsatu dari dua buah prosedur yang melakukanpengambilan elemen stack sebagai berikut . Prosedur pertama mengambil suatu Elmts denganmenyimpan alamatnya dan yang kedua mengambilnilai , dan membebaskan alamat ( dealokasi ) yang tadinya dipakai
Halaman 87
procedure PopStack@(Input/Output S : STACK Output P : address)
{K.Awal : Stack tidak kosongK.Akhir : Alamat elemen Top (S) disimpan pada
P, sehingga informasinya dapat diaksesmelalui P
Proses : Menghapus elemen stack, stack tidak bolehkosong dan mungkin menjadi kosong }
DeklarasiDeskripsi
P ← TOP (S)TOP (S) ← Next(TOP(S))
Halaman 88
procedure PopStack(Input/Output S : STACK Output E : InfoType)
{K.Awal : Stack tidak kosongK.Akhir : Alamat elemen Top (S) disimpan pada
E, alamat TOP yang lama didealokasiProses : Menghapus elemen stack, stack tidak boleh
kosong dan mungkin menjadi kosong }Deklarasi
P : addressDeskripsi
P ← TOP (S)E ← Info(P)TOP (S) ← Next(TOP(S))Dealokasi (P)
Halaman 89
SoalSoal--SoalSoal LatihanLatihan1. Mengapa cara penyusunan elemen pada
Stack sering disebut tersusun secaraLIFO?
2. Mengapa pada Stack Traversal dan Search jarang dilakukan?
3. Penghapusan elemen pada Stack selaludilakukan pada elemen yang paling atas, bagaimana jika terpaksa harus menghapuselemen yang paling bawah?
Halaman 90
4. Buatlah sebuah fungsi untuk menghitung jumlahelemen stack yang genap, jika diketahui sebuahstack dengan elemen bertype integer.
5. Buatlah fungsi/prosedur untuk mencetak elemenstack yang ganjil
6. Buatlah juga fungsi untuk menghitung rata-rata elemen Stack yang genap
7. Buatlah sebuah fungsi untuk mengirimkanelemen pertama Stack
8. Buatlah sebuah fungsi untuk mengirimkanelemen Stack yang maksimum jika diketahuielemen Stack terurut mengecil bertype integer
Halaman 91
Halaman 92
6. Queue (6. Queue (AntrianAntrian))6.1. Definisi
Queue (Antrian) adalah list linier yang :1. Dikenali elemen pertama (Head) dan elemen
terakhirnya (Tail)2. Aturan penyisipan dan penghapusan elemennya
disefinisikan sebagai berikut :- Penyisipan selalu dilakukan setelah elementerakhir
- Penghapusan selalu dilakukan pada elemenpertama
3. Satu elemen dengan elemen lain dapat diaksesmelalui informasi Next
Halaman 93
Struktur data ini banyak dipakai dalaminformatika misalnya untuk merepresentasi :1. Antrian job dalam sistem operasi2. Antrian dalam dunia nyata
Maka secara lojik, sebuah Queue dapatdigambarkan sebagai list linier yang setiapelemennya adalah :Type ElmtQ = record
<Info : InfoType, Next : address >
Halaman 94
dengan InfoType terdefinisi yang menentukaninformasi yang disimpan pada setiap elemenqueue, dan address adalah “alamat” darielemen
Selain itu alamat elemen Pertama (Head) danelemen terakhir (Tail) dicatat.
Maka jika Q adalah Queue dan P adalah Address, penulisan untuk Queue adalah :Head(Q)Tail(Q)Next(P)Info(P)
Halaman 95
Bagian Deklarasi dari algoritma pada Queue :Deklarasi
type InfoType = … {Sebuah type terdefinisi}type Address pointer to ElmtQtype ElmtQ = record
<Info : InfoType,Next : Address >
type Queue = record <Head : Address, Tail : Address>
{Deklarasi Nama Peubah}Q : QueueP : Address
Halaman 96
Pada queue, jarang sekali dilakukantraversal, karena keunikan Queue justrupada operasi yang hanya menyangkutelemen pertama dan terakhir. Namundibutuhkan traversal misalnya untukmencetak isi Antrian.
6.3. Search pada QueuePada Queue, elemen yang diproses hanyalah
elemen pada pertama dan terakhir. Makahampir tidak pernah dilakukan search.
6.2. Traversal 6.2. Traversal padapada QueueQueue
Halaman 97
6.4. 6.4. OperasiOperasi dandan fungsifungsi dasardasarpadapada Queue.Queue.
a. Test Queue kosongMengetahui bahwa Queue kosong atau tidaksangat penting, sebab semua operasi akandilakukan berdasarkan kosong atau tidaknyasuatu Queue. Realisasi algoritma dari definisifungsional ini adalah sebuah fungsi yang melakukan test terhadap Queue sebagaiberikut :
Halaman 98
function IsQEmpty (Q : Queue) → Boolean{ TEST Queue kosong : Mengirim true, jika
antrian kosong, false jika antrian tidakkosong}
DeklarasiDeskripsi
return ((Head(Q) = Nil) and (Tail(Q) = Nil))
Halaman 99
b. Pembuatan Queue kosongMembuat Queue kosong diperlukan untuk memulaimemakai Queue. Realisasi algoritma dari definisifungsional ini adalah sebuah prosedur yang melakukan inisialisasi Queue sebagai berikut :
Procedure CreateEmptyQ (Output Q : Queue){K. Awal : sembarang, K. Akhir : sebuah queue Q yang kosong terbentukProses : Membuat queue kosong }
DeklarasiDeskripsi
Head(Q) ← NilTail(Q) ← Nil
Halaman 100
c.Penambahan sebuah elemen padaQueuePenambahan selalu dilakukan pada ekor, dan karena alamat ekor diketahui makaprosesnya sederhana, yaitu hanyaInsertLast.
Berikut ini akan diberikan skema prosedurpenyisipan tersebut.
Halaman 101
Realisasi algoritma dari definisi fungsional iniadalah salah satu dari dua buah proseduryang melakukan penambahan elemenQueue sebagai berikut :
Prosedur pertama menambahkan suatuElemen Queue yang diketahui alamatnyadan yang kedua menambahkan suatu nilaiElemen queue yang diberikan.
Halaman 102
procedure InsertQ@ (Input/Output Q : Queue Input P : address)
{K.Awal : Queue mungkin kosong, P terdefinisi(berarti terdefinisi informasinya, Next (P) = Nil
K.Akhir : P menjadi elemen Tail dari Q danTail yang baru adalah P
Proses : Insert sebuah elemen beralamat P pada Tail dari antrian Q }
Deklarasi
Halaman 103
DeskripsiIf IsQEmpty(Q) then
Head(Q) ← PTail(Q) ← P
elseNext(Tail(Q)) ← PTail(Q) ← P
endif
Halaman 104
procedure InsertQ(Input/Output Q : Queue Input E : InfoType)
{K.Awal : Queue mungkin kosong, E terdefinisi
K.Akhir : Elemen Tail dari Q yang barubernilai E
Proses : Insert sebuah elemen nilai padaTail dari antrian Q }
Deklarasi
Halaman 105
DeskripsiAlokasi (P)Info (P) ← EIf IsQEmpty(Q) then
Head(Q) ← PTail(Q) ← P
elseNext(Tail(Q)) ← PTail(Q) ← P
endif
Halaman 106
d. Penghapusan Elemen Pada QueuEPenghapusan elemen pada queue selaludilakukan pada elemen pertama, hanya sajaperlu diperhitungkan bahwa mungkin queue menjadi kosong akibat terjadinyapenghapusan. Jika queue menjadi kosong, maka harga Tail harus diganti. Jika akibatpenghapusan queue tidak kosong, makaelemen terakhir tidak berubah.
Halaman 107
Berikut adalah skema penghapusan tersebut. Prosedur pertama melakukan penghapusanElmtQ yang berada di Head danyang dicatatadalah alamatnya, yaitu P. Prosedur yang kedua menghapus elemen Head dari queue danmenyimpannya pada suatu elmtQ sertamembebaskan alamat yang tadinya dipakaioleh elemen Head tersebut.
Halaman 108
procedure DeleteQ@(Input/Output Q : Queue Output P : address)
{K.Awal : Queue tidak kosongK.Akhir : P bukan lagi elemen dari Q, P ≠ Nil,
Next(P) = NilProses : Menghapus elemen Head dari antrian,
antrian tidak boleh kosong danmungkin menjadi kosong }
DeklarasiDeskripsi
Halaman 109
P ← Head(Q)Head(Q) ← Next(Head(Q))if (Head(Q) = Nil) then
Tail(Q) ← NilendifNext(P) ← Nil
Halaman 110
procedure DeleteQ(Input/Output Q : Queue Output E : InfoType)
{K.Awal : Queue tidak kosongK.Akhir : Jika P adalah Head(Q). P bukan lagi
elemen dari Q, P ≠ Nil, Next(P) = Nil
Proses : Menghapus elemen Head dari antrian, antrian tidak boleh kosong danmungkin menjadi kosong }
DeklarasiDeskripsi
Halaman 111
P ← Head(Q)E ← Info(Head(Q))Head(Q) ← Next(Head(Q))if (Head(Q) = Nil) then
Tail(Q) ← NilendifNext(P) ← NilDealokasi(P)
Halaman 112
SoalSoal--SoalSoal
1. Mengapa cara penyusunan elemen padaQueue Sering disebut tersusun secaraFIFO?
2. Mengapa pada Queue Traversal danSearch jarang dilakukan?
3. Penghapusan elemen pada Queue selaludilakukan pada elemen yang paling depan, bagaimana jika terpaksa harus menghapuselemen yang paling belakang?
Halaman 113
4. Buatlah sebuah fungsi untuk menghitung jumlahelemen queue yang ganjil, jika diketahui sebuahqueue dengan elemen bertype integer.
5. Buatlah fungsi/prosedur untuk mencetak elemenqueue yang genep
6. Buatlah juga fungsi untuk menghitung rata-rata elemen queue yang ganjil
7. Buatlah sebuah fungsi untuk mengirimkan elemenpertama queue
8. Buatlah sebuah fungsi untuk mengirimkan elemenqueue yang maksimum jika diketahui elemen queue terurut membesar dan bertype integer
Halaman 114
Halaman 115
7. 7. PohonPohon (Tree)(Tree)7.1. Definisi Rekurens Dari PohonSebuah pohon adalah himpunan terbatas tidak
kosong, dengan elemen yang dibedakansebagai berikut :
1. Sebuah elemen yang dibedakan dari yang lain yang disebut sebagai AKAR (root) daripohon
2. Elemen yang lain (jika masih ada) dibagi-bagi menjadi beberapa sub himpunan yang disjoint dan masing-masing sub himpunantersebut adalah pohon yang disebut sebagaisub pohon dari pohon tersebut.
Halaman 116
Beberapa Istilah1. Hutan
Hutan adalah sequence (list) dari pohon2. Simpul (Node)
Simpul adalah elemen dari pohon yang memungkinkan akses pada sub pohon dimanasimpul tersebut berfungsi sebagai Akar
3. CabangCabang adalah hubungan antara Akar dengansub pohon
Halaman 117
4. AyahAkar dari sebuah pohon adalah Ayah darisub pohon
5. AnakAnak dari sebuah pohon adalah Sub pohon
6. SaudaraSaudara adalah simpul-simpul yang mempunyai Ayah yang sama
7. DaunDaun adalah simpul terminal dari pohon. Semua simpul selain Daun adalah simpulbukan terminal
Halaman 118
8. Jalan (Path)Jalan adalah suatu urutan tertentu dariCabang
9. DerajatDerajat sebuah pohon adalah banyaknyaanak dari dari pohon tersebut.Jika sebuah simpul berderajat N disebut
pohon N-aire1 disebut pohon 1-aire/uner2 disebut pohon 2-aire/biner
Halaman 119
10. Tingkat (Level)Level pohon adalah panjangnya jalan dariAkar sampai dengan simpul yang bersangkutan. Panjang dari jalan adalahbanyaknya simpul yang dikandung padajalan tersebut. Akar mempunyai tingkat samadengan 1.
Dua buah simpul disebut sebagai Sepupu jikamempunyai tingkat yang sama dalam sebuahpohon.
Halaman 120
11. Kedalaman (Tinggi)Kedalaman (Tinggi) dari pohon adalah nilaimaksimum dari tingkat simpul yang ada padapohon tersebut. Kedalaman adalah panjangmaksimum jalan dari Akar menuju ke sebuahdaun
12. LebarLebar sebuah Pohon adalah maksimumbanyaknya simpul yang ada pada suatuTingkat (Level)
Halaman 121
7.2. Struktur Pohon BinerDefinisiSebuah pohon biner (Binary Tree) adalah
himpunan terbatas yang :Mungkin kosong atauTerdiri dari sebuah simpul yang disebutsebagai Akar dan dua buah himpunan lain yang disjoint yang merupakan pohon bineryang disebut sebagai Sub Pohon Kiri (Left) dan Sub Pohon Kanan (Right) dari pohon binertersebut.
Halaman 122
Pohon biner merupakan tipe yang sangat pentingdari struktur data dan banyak dijumpaidalam berbagai terapan. Karakteristik yang dimiliki oleh pohon biner adalah bahwasetiap simpul paling banyak hanyamemiliki dua buah anak, dan mungkintidak punya anak.
Istilah-istilah yang digunakan sama denganistilah pada pohon secara umum.
Halaman 123
Notasi Prefiks, Infiks dan Postfiks1. Notasi Prefiks
Notasi Prefiks ditulis dengan cara mengikutialur sebagai berikut :
Halaman 124
2. Notasi InfiksNotasi ini ditulis dengan cara mengikuti alursebagai berikut :
Halaman 125
3. Notasi PosfiksNotasi ini ditulis dengan cara mengikuti alursebagai berikut :
Halaman 126
Rekonstruksi Algoritma{Deklarasi Type}
Type Infotype = … {terdefinisi}Type node = record <Info : infotype,
Left : address,Right: address >
Type BinTree : address
{Primitif}
Halaman 127
function Akar (P : BinTree)→ infotype{Mengirimkan nilai Akar pohon biner P}
function Left (P : BinTree)→ infotype{Mengirimkan anak kiri pohon biner P}
function Right (P : BinTree)→ infotype{Mengirimkan anak kanan pohon biner P}
Halaman 128
function IsEmpty(P : BinTree)→boolean{ Test apakah sebuah pohon kosong,
mengirimkan True jika kosong dan False jikatidak}
procedure MakeTree(input Akar : infotype, L : BinTree, R : BinTree, output P : BinTree)
{ K. Awal : sembarangK. Akhir : Terbentuk sebuah pohon binerProses : Menghasilkan sebuah pohon biner
dari Akar, L dan R}
Halaman 129
{Traversal}Procedur PreOrder(input P : BinTree){K. AWAL : P terdefinisiK. AKHIR : Semua simpul P sudah
diproses secara preorder}
Procedure InOrder(input P : BinTree){K. AWAL : P terdefinisiK. AKHIR : Semua simpul P sudah
diproses secara inorder}
Halaman 130
Procedure PostOrder(input P : BinTree){K. AWAL : P terdefinisiK. AKHIR : Semua simpul P sudah
diproses secara postorder}
Procedure PrintTree(input P : BinTree, h : integer){K. AWAL : P terdefinisi, h adalah jarak indentasiK. AKHIR : Semua simpul P sudah ditulis dengan
indentasi}
Halaman 131
{Search}function Search(P : BinTree, X : infotype)→boolean{Mengirimkan True jika ada node P bernilai X, false
jika tidak}
{fungsi lain}function NbElmt(P : BinTree)→integer{Mengirimkan banyaknya elemen (node) pohon
biner P}
Halaman 132
function NbDaun(P : BinTree) →integer{ Mengirimkan banyaknya daun pohon biner P}function IsUnerLeft(P : BinTree) →boolean{ Mengirimkan True jika pohon biner tidak
kosong P adalah pohon unerleft yaitu hanyamempunyai sub pohon kiri}
function IsUnerRight(P : BinTree) →boolean{ Mengirimkan True jika pohon biner tidak
kosong P adalah pohon unerright yaitu hanyamempunyai sub pohon kanan}
Halaman 133
function IsBin(P : BinTree)→boolean{ Mengirimkan True jika pohon biner tidak
kosong P adalah pohon biner yaitu mempunyaisub pohon kanan dan sub pohon kiri}
function IsSkewLeft(P : BinTree)→boolean{ Mengirimkan True jika pohon biner P adalah
pohon condong kiri}
function IsSkewRight(P : BinTree)→boolean{ Mengirimkan True jika pohon biner P adalah
pohon condong kanan}
Halaman 134
function Tinggi(P : BinTree)→integer{ Mengirimkan tinggi dari pohon biner P}
function Level(P : BinTree, X : infotype)→integer{ Mengirimkan level dari node X yang merupakan
salah satu simpul dari pohon biner P}
{Operasi Lain}
Halaman 135
Procedure AddDaunTerkiri(input/output P:BinTree, input X: infotype)
{K. AWAL : P boleh kosongK. AKHIR : P bertambah simpulnya, dengan X
adalah simpul daun terkiri}Procedure AddDaun(input/output P:BinTree, input
X, Y : infotype, input Kiri : boolean){K. AWAL : P tidak boleh kosong, X adalah salah
satu daun pohon Biner PK. AKHIR : P bertambah simpulnya, dengan Y
adalah anak kiri X (jika kiri) atausebagai anak kanan X (jika not kiri)}
Halaman 136
Procedure DelDaunTerkiri(input/outputP:BinTree, output X: infotype)
{K. AWAL : P tidak kosongK. AKHIR: P dihapus daun terkirinya dan
didealokasi, dengan X adalah info yang semula disimpan pada daunterkiri yang dihapus}
Procedure DelDaun(input/output P:BinTree, output X: infotype)
{K. AWAL : P tidak kosong, X adalah salah satudaun
K. AKHIR : X dihapus dari P}