zzzz

Pertemuan 9
STRUKTUR POHON &
KUNJUNGAN POHON BINER

Pohon (Tree) termasuk struktur non linear yang
didefinisikan sebagai data yang terorganisir dari suatu
item informasi cabang yang saling terkait
Root
A
Level
DEFINISI POHON (TREE)
---------------------------------- 0
E
B C
F
G
D
H
----------------------- 1
------------------ 2
Height = 2
1. Predesesor
Node yang berada diatas node tertentu.
(contoh : B predesesor dari E dan F)
2. Succesor
Node yang berada dibawah node tertentu.
Istilah – istilah Dalam Pohon
(contoh : E dan F merupakan succesor dari B)
3. Ancestor
Seluruh node yang terletak sebelum node tertentu dan
terletak pada jalur yang sama.
(contoh : A dan B merupakan ancestor dari F)
4. Descendant
Seluruh node yang terletak sesudah node tertentu
dan terletak pada jalur yang sama.
(contoh : F dan B merupakan ancestor dari A)
5. Parent
Predesesor satu level diatas satu node
(contoh : B merupakan parent dari F)
6. Child
Succesor satu level dibawah satu node
(contoh : F merupakan child dari B)
7. Sibling
Node yang memiliki parent yang sama dengan satu
node (contoh : E dan F adalah sibling)
8. Subtree
Bagian dari tree yang berupa suatu node beserta
descendant-nya (contoh : Subtree B, E, F dan
Subtree D, G, H)
9. Size
Banyaknya node dalam suatu tree (contoh : gambar
tree diatas memiliki size = 8)
10. Height
Banyaknya tingkat/level dalam suatu tree (contoh :
gambar tree diatas memiliki height = 2) karena
program C++ diawali dari index ke-0
11. Root (Akar)
Node khusus dalam tree yang tidak memiliki
predesesor (Contoh : A)
12. Leaf (Daun)
Node-node dalam tree yang tidak memiliki daun
(contoh : Node E,F,C,G,H)
13. Degree (Derajat)
Banyaknya child yang dimiliki oleh suatu node
(contoh : Node A memiliki derajat 3, node B memiliki
derajat 2)
Struktur ini biasanya digunakan untuk menyajikan data
yang mengandung hubungan hirarkial antara elemenelemennya.
Bentuk Pohon Berakar yang lebih mudah dikelola dalam
komputer adalah Pohon Biner (Binary Tree) yang lebih
dikenal sebagai Pohon Umum (General Tree) yang dapat
POHON BINAR (BINARY TREE)
didefinisikan sebagai kumpulan simpul yang mungkin
kosong atau mempunyai akar dan dua Subpohon yang
saling terpisah yang disebut dengan Subpohon Kiri /
cabang kiri (Left Subtree) dan Subpohon Kanan / cabang
kanan (Right Subtree).
Karakteristik Pohon Binar (Binary Tree) :
1. Setiap Simpul paling banyak hanya memiliki dua buah
anak
2. Derajat Tertinggi dari setiap Simpul adalah dua.
3. Dibedakan antara Cabang Kiri dan Cabang Kanan.
4. Dimungkinkan tidak mempunyai Simpul
Berikut ini diberikan contoh gambar Pohon Binar (Binary
Tree) dengan Cabang Kiri dan Cabang Kanan.
ISTILAH PADA POHON BINER
• Pohon Biner Penuh
(Full Binary Tree)
Semua simpul (kecuali daun)
memiliki 2 anak dan tiap cabang
memiliki panjang ruas yang sama
A
B C
D E F G
• Pohon Biner Lengkap
(Complete Binary Tree)
Hampir sama dengan Pohon Biner
Penuh, semua simpul (kecuali
daun) memiliki 2 anak tetapi tiap
cabang memiliki panjang ruas
berbeda
A
B C
D E
• Pohon Biner Similer
Dua pohon yang memiliki struktur yang sama tetapi
informasinya berbeda
A
B C
• Pohon Biner Ekivalent
P
Q R
Dua pohon yang memiliki struktur dan informasi yang
sama
P
Q R
P
Q R
• Pohon Biner Miring (Skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu
anak / turunan kecuali daun
Deklarasi Pohon Biner
(Dengan Program C++)
Dalam setiap simpul selalu berisi dua buah Pointer untuk
menunjuk ke cabang Kiri dan cabang Kanan dan informasi
yang akan disimpan dalam simpul tersebut.

• Tree dapat dibuat dengan menggunakan linked list
secara rekursif.
• Linked list yang digunakan adalah double linked list non
circular
• Data yang pertama kali masuk akan menjadi node root.
Penyajian Pohon Binar
(Binary Tree)
• Data yang lebih kecil dari data node root akan masuk
dan menempati node kiri dari node root, sedangkan jika
lebih besar dari data node root, akan masuk dan
menempati node di sebelah kanan node root.
Bila diberikan untai HAKJCBL, maka proses untuk dapat
membentuk pohon biner dari untai diatas adalah :
1. Karakter pertama ‘H’ ditempatkan sebagai akar (root)
2. Karakter ‘A’,karena lebih kecil dari ‘H’, maka akan
menempati cabang kiri.
3. Karakter ‘K’, karena lebih besar dari ‘H’, maka akan
menempati cabang kanan.
4. Karakter ‘J’, lebih besar dari ‘H’ dan kecil dari ‘K’, maka
menempati cabang kiri ‘K’.
Dan begitu seterusnya sehingga terbentuk
pohon biner seperti berikut :




Pertemuan 10
KUNJUNGAN
PADA POHON BINER

3. Kunjungan secara Postorder, mempunyai urutan :
a. Kunjungi Cabang Kiri
b. Kunjungi Cabang Kanan
c. Cetak isi simpul yang dikunjungi (Simpul Akar)
Pada ketiga cara kunjungan diatas, kunjungan ke
Cabang Kiri dilakukan terlebih dahulu, baru kemudian
kunjungan ke Cabang Kanan. Dengan orientasi
semacam ini, Ketiga kunjungan diatas disebut dengan
Left To Right Oriented (LRO).
Jika kunjungan ke Cabang Kanan dilakukan lebih
dahulu baru kemudian kunjungan ke Cabang Kiri, maka
Orientasi semacam ini disebut Right To Left Oriented
(RLO).
A
B C
D E
A B D E C
Klik Animasi
Klik Animasi
Kunjungan PreOrder dalam Program C++
A
B C
D E
D B E A C
Klik Animasi
Klik Animasi
Kunjungan InOrder dalam Program C++
A
3. Kunjungan secara Postorder, mempunyai urutan :
a. Kunjungi Cabang Kiri
b. Kunjungi Cabang Kanan
c. Cetak isi simpul yang dikunjungi (Simpul Akar)
B C
D E
D E B C A
Klik Animasi
Klik Animasi
Kunjungan PostOrder dalam Program C++
Kunjungan LevelOrder
Selain kunjungan yang dijelaskan diatas, masih ada
satu macam kunjungan masih ada satu macam
kunjungan lagi yaitu kunjungan LevelOrder.
Kunjungan dimulai dari simpul yang ada pada tingkat
1 (Akar), diteruskan pada simpul di tingkat 2, tingkat 3
dan seterusnya.
Secara singkat kunjungan Level Order ini dapat dijelaskan
sebagai berikut.
1. Dimulai dengan memasukkan Akar kedalam antrean.
2. Kemudian mengeluarkan Akar tersebut keluar dari
antrean.
Pada saat Akar tersebut dikeluarkan dari antrean, cabang
kiri dan cabang kanan secara berturut-turut dimasukkan
dalam antrean.
Dengan kata lain jika suatu elemen dikeluarkan dari
antrean, maka cabang kiri dan kanan dari elemen yang
baru saja dikeluarkan dimasukkan kedalam antrean.
APLIKASI POHON BINER
NOTASI PREFIX, INFIX DAN POSTFIX
Pada bagian ini akan dibahas tentang bagaimana
menyusun sebuah Pohon Binar yang apabila dikunjungi
secara PreOrder akan menghasilkan Notasi Prefix,
kunjungan secara InOrder menghasilkan Notasi Infix, dan
kunjungan PostOrder menghasilkan Notasi Postfix.


Berdasarkan Gambar diatas, apabila dilakukan kunjungan
secara PreOrder, maka akan diperoleh Notasi Prefix dari
persamaan-persamaan yang digambarkan tersebut, yaitu :
+A*BC (Gambar.a)
*+AB-BC (Gambar.b)
^-*+ABC-DE+FG (Gambar.c)
Jika dilakukan kunjungan secara InOrder, akan diperoleh
Notasi Infixnya, yaitu :
(A+(B*C)) (Gambar.a)
((A+B) * (B-C)) (Gambar.b)
(((A+B) * C) – (D-E)^(F+G) (Gambar.c)
Jika dilakukan kunjungan secara PostOrder, akan
diperoleh Notasi Postfixnya, yaitu :
ABC*+ (Gambar.a)
AB+BC-* (Gambar.b)
AB+C*DE-FG+^ (Gambar.c)





Pertemuan 11
GRAPH dan
MATRIK PENYAJIAN GRAPH
Suatu Graph mengandung 2 himpunan, yaitu :
1. Himpunan V yang elemennya disebut simpul (Vertex
atau Point atau Node atau Titik)
2. Himpunan E yang merupakan pasangan tak urut dari
simpul. Anggotanya disebut Ruas (Edge atau rusuk
atau sisi)
GRAPH
Graph seperti dimaksud diatas, ditulis sebagai G(E,V).
Contoh :
Gambar berikut menanyakan Graph G(E,V) dengan :
1. V mengandung 4 simpul, yaitu simpul A,B,C,D.
2. E mengandung 5 ruas, yaitu :
e1 = (A,B) e4 = (C,D)
e2 = (B,C) e5 = (B,D)
e3 = (A,D)
Gambar dibawah ini menyatakan suatu Multigraph.
Disini, ruas e2 pada kedua titik ujungnya adalah simpul
yang sama, yaitu simpul A. Ruas semacam ini disebut
Gelung atau Self-Loop. Sedangkan ruas e5 dan e6
mempunyai titik ujung yang sama, yaitu simpul-simpul B
dan C. Kedua ruas ini disebut ruas berganda atau ruas
sejajar.
e3
e5
e4
e2
e1
e6
Suatu Graph yang tidak mengandung ruas sejajar maupun
self-loop, sering disebut juga sebagai Graph sederhana
atau simple Graph.
Suatu Graph G’(E’,V’) disebut Sub Graph dari G(E,V), bila E’
himpunan bagian dari E dan V’ himpunan bagian dari V.
Jika E’ mengandung semua ruas dari E yang titik ujungnya
di V’, maka G’ disebut Subgraph yang direntang oleh V’
(Spanning Subgraph).
Contoh Sub Graph:
Contoh Spanning Sub Graph :
Graph G disebut berlabel jika ruas dan atau simpulnya
dikaitkan dengan suatu besaran tertentu. Khususnya jika
setiap Ruas e dari G dikaitkan dengan suatu bilangan
non negatif d(e), maka d(e) disebut bobot atau panjang
GRAPH BERLABEL
dari ruas e.
Contoh :
Gambar berikut ini menyajikan hubungan antar kota.
Disini simpul menyatakan kota dan label d(e) menyatakan
jarak antara dua kota.
DERAJAT GRAPH
Derajat simpul V, ditulis d(v) adalah banyaknya ruas
yang menghubungi v. Karena setiap ruas dihitung dua
kali ketika menentukan derajat suatu Graph, maka :
Jumlah derajat semua simpul suatu Graph (derajat) =
dua kali banyaknya ruas Graph (Size) Atau dapat
dituliskan :
Derajat Graph = 2 x Size
Pada gambar diatas Jumlah Semua Simpul = 4, maka
Jumlah Derajat Semua Simpul = 8
Jika Derajat masing-masing simpul pada Graph berjumlah
Genap maka Graph tersebut disebut EULER Graph
Contoh :
D E
B
C
A F
Pada gambar diatas, banyak ruas/size = 7, sedangkan
derajat masing-masing simpul adalah :
d(A) = 2
d(B) = 5
d(C) = 3
d(D) = 3
d(E) = 1
d(F) = 0
maka, total jumlah derajat simpul adalah : 14
E disebut simpul bergantung/akhir, yaitu simpul yang
berderajat satu. Sedangkan F disebut simpul terpencil,
yaitu simpul yang berderajat Nol.
Walk atau perjalanan dalam Graph G adalah barisan simpul
dan ruas berganti-ganti : V1,e1,V2,e2,......., e n-1, Vn
Disini ruas ei menghubungkan simpul Vi dan Vi+1.
Banyaknya ruas disebut Panjang Walk. Walk dapat ditulis
lebih singkat dengan hanya menulis deretan ruas :
KETERHUBUNGAN
e1,e2, ...., en-1 atau deretan simpul : V1, V2,....., Vn-1, Vn
dimana : V1 = simpul awal
Vn = simpul akhir.
Walk disebut tertutup bila V1 = Vn

Graph merupakan Walk Terbuka, karena tidak ada ruas
yang menghubungkan Simpul U dan T.
Merupakan suatu Path atau Trail terbuka dengan
derajat setiap simpulnya = 2, kecuali simpul awal U dan
simpul akhir T berderajat = 1.

· Barisan ruas a,b,c,d,b,c,g,h adalah Walk bukan Trail
(karena ruas b dua kali muncul).
· Barisan simpul A, B, E, F bukan Walk (karena tdk
ada ruas yang menghubungkan simpul B ke F).
· Barisan simpul A, B, C, D, E, C, F adalah Trail
bukan Jalur/Path (karena c dua kali muncul)
· Barisan ruas a, d, g, k adalah Jalur/Path karena
menghubungkan A dengan F
· Ruas a, b, h, g, e, a, adalah Cycle.
Graph yang tidak mengandung Cycle disebut Acyclic.
Contoh dari Graph Acyclic adalah pohon atau Tree.
Contoh dari acyclic

GRAPH TERARAH (DIRECTED GRAPH / DIGRAPH)
Graph terarah adalah Graph yang dapat menghubungkan
V1 ke V2 saja (1 arah).
Maksimum jumlah busur dari n simpul adalah : n ( n - 1)
Suatu Graph Berarah (Directed Graph) D terdiri atas 2
himpunan :
1) Himpunan V, anggotanya disebut simpul.
2) Himpunan A, merupakan himpunan pasangan terurut,
yang disebut ruas berarah atau arkus.
Contoh, Gambar dibawah ini adalah sebuah Graph
Berarah D(V,A) dengan :
1. V mengandung 4 simpul, yaitu 1, 2, 3 dan 4
2. A mengandung 7 arkus, yaitu (1,4) ,(2,1), (2,1),
(4,2), (2,3), (4,3) dan (2)
Arkus (2,2) disebut gelung (self-loop), sedangkan
arkus (2,1) muncul lebih dari satu kali, disebut
arkus sejajar atau arkus berganda.
Bila arkus suatu Graph Berarah menyatakan suatu bobot,
maka Graph Berarah tersebut dinamakan jaringan /
Network. Biasanya digunakan untuk menggambarkan
situasi dinamis.
Bila V’ himpunan bagian dari V serta A’ himpunan bagian
dari A, dengan titik ujung anggota A’ terletak di dalam V’,
maka dikatakan bahwa D’(V’,A’) adalah Graph bagian
(Subgraph) dari D(V,A).
Bila A’ mengandung semua arkus anggota A yang titik
ujungnya anggota V’, maka dikatakan bahwa D’(V’,A’)
adalah Graph Bagian yang dibentuk atau direntang oleh V’.

CRITICAL PATH
1
2
3
4 5

Merupakan Spanning Tree yang mempunyai Bobot dan
tidak mempunyai arah dengan hasil penjumlahan
bobotnya adalah minimum.
Lihat gambar Graph G berikut :
MINIMUM SPANNING TREE
V2
V1
V4
V3
V5
Langkah yang dilakukan untuk membentuk minimum
spanning tree adalah :
Bentuk kembali semua simpul tetapi tanpa ruas.
Gambar dan telusuri ruas dengan bobot paling kecil,
seterusnya (secara ascending) hingga semua simpul
terhubung
Total Minimum
Spanning Tree = 22
(4)
V1
V2
V3
V4 V5
(5)
(6)
(7)

Karena V8 sudah dilewati setelah
penelusuran ke V4, maka penelusuran yang
berikutnya dianggap tidak dilewati lagi
Klik Animasi

2. Breadth First Search (BFS).
Berbeda dengan cara BFS, dengan BFS penelusuran
akan diawasi dari Node-1, kemudian melebar pada
Adjacent Node dari Node-1 dan diteruskan pada
Node-2, Node- 3 dan seterusnya.
Dari gambar di atas akan diperoleh urutan :
V1 , V2 ---> V3 , V4 ---> V5 ---> V6 ---> V7, V8
Klik Animasi



Pertemuan 12-14
PRESENTASI
PROJECT