11-12.Tree

Tree ABDI PANDU KUSUMA, S.KOM., M.T

Pengenalan Tree Tree → ?? Tree = Pohon Tree: ➢ Struktur data non linear yang digunakan untuk merepresentasikan hubungan data yang bersifat hierarkis antara elemen-elemennya. ➢ Pada tree salah satu elemennya disebut dengan root (akar) dan sisa elemen lain disebut simpul (node/vertex) yang terpecah menjadi sejumlah himpunan yang tidak saling berhubungan satu sama lain, yang disebut subtree/cabang.

Bagian-bagian Tree Predesesor. Node yang berada diatas node tertentu (B predesesor dari E & F). Succesor. Node yang berada dibawah node tertentu (E & F succesor dari B). Ancestor. Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama (A & B ancestor dari F). Descendant. Seluruh node yang terletak setelah node tertentu dan terletak pada jalur yang sama (F & B descendant dari A). Parent. Predecesor satu level diatas satu node. Child. Succesor satu level dibawah satu node.

Bagian-bagian Tree Sibling. Node yang memiliki parent yang sama dengan satu node. Subtree. Bagian dari tree yang berupa suatu node beserta descandant-nya. Size. Banyaknya node dalam suatu tree. Height. Banyaknya level/ tingkat dalam suatu tree. Root. Node khusus yang tidak memiliki predecessor. Leaf. Node dalam tree yang tidak memiliki daun. Degree. Banyaknya child yang dimiliki suatu node.

Karakteristik Tree • Jika Tree mempunyai Simpul sebanyak n, maka banyaknya • Tree mempunyai Ketinggian atau ruas atau edge adalah (n-1). Kedalaman atau Height. • Mempunyai Simpul Khusus yang disebut Root, jika Simpul • Tree mempunyai Weight atau Berat tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0. atau Bobot, yakni banyaknya daun (leaf) pada Tree. • Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika • Banyaknya Simpul Maksimum sampai Simpul tersebut berderajat keluar = 0, dan berderajat Level N adalah : masuk = 1. • Setiap Simpul mempunyai Tingkatan / Level yang dimulai • Banyaknya Simpul untuk setiap Level I dari Root yang Levelnya = 1 sampai dengan Level ke – n adalah : pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Sibling.

Contoh Kasus Diketahui suatu bentuk Pohon Berakar T sebagai berikut : Tree disamping memiliki: • Simpul (node n) sebanyak 8; Edge = n - 1 = 7. • Root tree = node P. • Jumlah leaf = 4, diantaranya R,S,V,W. • Level tree = 4, diantaranya: Level 1 = node P. Level 2 = node Q & T. Level 3 = node R, S, & U. Level 4 = node V & W. • Height (ketinggian) tree = 4. • Weight (bobot) tree, banyaknya daun = 4.

Contoh Kasus • Banyaknya node yang terbentuk hingga level 4 (jika node tree dianggap penuh): =2(n)-1 =2(4)-1 =16-1 =15 • Banyaknya node maksimum untuk setiap level I (jika node tree dianggap penuh): Maksimum node level 2 = 2(I-1) = 2(2-1) = 2. Maksimum node level 3 = 2(I-1) = 2(3-1) = 4. Maksimum node level 4 = 2(I-1) = 2(4-1) = 8.

??? ADA PERTANYAAN ???

Binary Tree Binary Tree → ?? Binary Tree → 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 Binary Tree: Contoh gambar Pohon Binar • Setiap Simpul paling banyak hanya memiliki dua buah anak (Binary Tree) dengan Cabang Kiri dan Cabang Kanan. • Derajat Tertinggi dari setiap Simpul adalah dua. • Dibedakan antara Cabang Kiri dan Cabang Kanan. • Dimungkinkan tidak mempunyai Simpul.

Jenis-jenis Binary Tree Full Binary Tree. Semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas yang sama. Complete Binary Tree. Hampir sama dengan Pohon Biner Penuh, semua simpul (kecuali daun) memiliki 2 anak tetapi tiap cabang memiliki panjang ruas berbeda.

Jenis-jenis Binary Tree Similliar Binary Tree. Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda. Skewed (miring) Binary Tree. Equivalent Binary Tree. Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun Dua pohon yang memiliki struktur dan informasi yang sama.

Deklarasi Binary Tree

Penyajian Binary Tree • 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. 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.

Contoh Kasus Jika diberikan untai HAKJCBL, maka proses untuk dapat membentuk pohon biner dari untai tersebut: a) Karakter pertama ‘H’ ditempatkan sebagai akar (root). b) Karakter ‘A’,karena lebih kecil dari ‘H’, maka akan menempati cabang kiri. c) Karakter ‘K’, karena lebih besar dari ‘H’, maka akan menempati cabang kanan. d) Karakter ‘J’, lebih besar dari ‘H’ dan kecil dari ‘K’, maka menempati cabang kiri ‘K’. e) Karakter ‘C’,karena lebih besar dari ‘A’, maka akan menempati cabang kanan. f) Karakter ‘B’, karena lebih kecil dari ‘C’, maka akan menempati cabang kiri. g) Karakter ‘L’, lebih besar dari ‘K’, maka menempati cabang kiri kanan. Sehingga terbentuk pohon biner seperti berikut:

Kunjungan pada Binary Tree Kunjungan pada Binary Tree merupakan salah satu operasi yang sering dilakukan pada suatu Pohon Biner tepat satu kali (Binary Tree Traversal). Operasi pada kunjungan binary tree terbagi menjadi 3 bentuk, diantaranya: a) Kunjungan secara PreOrder (Depth First Order) b) Kunjungan secara InOrder (Symetric Order) c) Kunjungan secara PostOrder • 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).

Kunjungan Secara PreOrder (Depth First Order) Teknis urutannya: 1) Cetak isi simpul yang dikunjungi (simpul akar) 2) Kunjungi Cabang Kiri 3) Kunjungi Cabang Kanan Hasil Kunjungan PreOrder diatas adalah A B D E C

Kunjungan Secara PreOrder (Depth First Order) Contoh bentuk binary tree lainnya: Coding C++ untuk kunjungan secara preorder :

Kunjungan Secara InOrder (Symetric Order) Teknis urutannya: 1) Kunjungi Cabang Kiri 2) Cetak isi simpul yang dikunjungi (Simpul Akar) 3) Kunjungi Cabang Kanan Hasil Kunjungan Secara InOrder : D B E A C

Kunjungan Secara InOrder (Symetric Order) Contoh bentuk binary tree lainnya: Coding C++ untuk kunjungan secara InOrder :

Kunjungan PostOrder Teknis urutannya: 1) Kunjungi Cabang Kiri 2) Kunjungi Cabang Kanan 3) Cetak isi simpul yang dikunjungi (Simpul Akar) Hasil dari Kunjungan PostOrder diatas adalah D E B C A

Kunjungan PostOrder Contoh bentuk binary tree lainnya: Coding C++ untuk kunjungan secara PostOrder :

Notasi Prefix, Infix, & Postfix pada Binary Tree Pada binary tree apabila dikunjungi secara PreOrder akan menghasilkan Notasi Prefix, kunjungan secara InOrder menghasilkan Notasi Infix, dan kunjungan PostOrder menghasilkan Notasi Postfix. Perhatikan 3 binary tree berikut:

Perhatikan 3 binary tree berikut: Notasi Prefix: (Gambar.a): +A*BC Notasi Postfix: (Gambar.b): *+AB-BC Notasi Infix: (Gambar.a): ABC*+ (Gambar.c): ^-*+ABC-DE+FG (Gambar.b): AB+BC-* (Gambar.a): (A+(B*C)) (Gambar.c): AB+C*DE--FG+^ (Gambar.b): ((A+B) * (B-C)) (Gambar.c): ((((A+B) * C) – (D-E))^(F+G))

Latihan Program infix ke prefix pada binary tree. Penyelesaian:

Latihan (lanjutan) Lanjutan Penyelesaian:

Latihan (lanjutan) Lanjutan Penyelesaian:

Tugas 6 Buat aplikasi program binary tree untuk konversi postfix ke prefix! [ NIM GANJIL ] Buat aplikasi program binary tree untuk konversi prefix ke postfix! [ NIM GENAP ] Tugas dikerjakan secara individual (DOC & CPP) dikirimkan via Edlink bentuk link bit.ly melalui google drive dengan format “Tugas6_NIM_Nama Mhs_Genap/Ganjil_SK3” terakhir pada tanggal 12 Januari 2022 jam 18.00.