TREE

Pengenalan Diri
• Adrian Joshua (8020220334)
• Ergasia Metra Kinesis. A (8020220235)
• M. Abdhan Shalihan (8020220148)
• Vhicram Mustafa (8020220224)
 Pendahuluan
Konsep 'tree' dalam pemrograman merujuk pada struktur data hierarkis yang
sering digunakan untuk merepresentasikan hubungan antara elemen-elemen
data. Dalam struktur ini, setiap elemen disebut 'simpul' dan memiliki satu simpul
yang disebut 'akar' serta simpul-simpul lain yang mungkin menjadi 'anak' dari
simpul tersebut. Pohon ini memiliki beberapa varian. Sebagai contoh, pada pohon
biner, setiap simpul memiliki paling banyak dua anak, sementara pada pohon
pencarian biner, urutan nilai dijaga sedemikian rupa sehingga setiap simpul kiri
memiliki nilai lebih kecil daripada simpul tersebut, dan setiap simpul kanan
memiliki nilai lebih besar.
Operasi umum pada tree melibatkan pengurutan (traversal), pencarian nilai
tertentu, serta penyisipan dan penghapusan simpul. Penggunaan pohon dalam
pemrograman melibatkan representasi hierarki data, yang sangat berguna untuk
berbagai keperluan seperti representasi struktur direktori pada sistem operasi atau
model hubungan dalam [Link] terhadap konsep 'tree' penting
karena menyediakan dasar bagi implementasi struktur data dan algoritma yang
efisien dalam pemrograman."
 TREE
Tree merupakan salah satu bentuk
struktur data tidak linear
yangmenggambarkan hubungan
yang bersifat hirarkis (hubungan
one to many) antaraelemen-elemen. Tree merupakan salah satu bentuk
Tree bisa didefinisikan sebagai struktur data tidak linear
kumpulan simpul/node dengan
satuelemen khusus yang disebut yangmenggambarkan hubungan yang
Root dan node lainnya. Tree juga bersifat hirarkis (hubungan one to many)
adalah suatu graphyang acyclic, antaraelemen-elemen. Tree bisa
simple, connected yang tidak
mengandung loop. didefinisikan sebagai kumpulan
simpul/node dengan satuelemen khusus
yang disebut Root dan node lainnya. Tree
juga adalah suatu graphyang acyclic,
simple, connected yang tidak
mengandung loop.
 BINERY TREE
Binary Tree merupakan salah satu bentuk struktur data tidak linear
yangmenggambarkanhubungan yang bersifat hirarkis (hubungan one to many)
antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node
dengan satuelemen khusus yang disebut Root dan node lainnya ( disebut
subtree).Dalam tree terdapat jenis-jenis tree yang memiliki sifat khusus,
diantaranyaadalah binary tree.
Binary tree adalah suatu tree dengan syarat bahwa tiap node (simpul) hanya boleh
memiliki maksimal dua subtree dan kedua subtree tersebut harus [Link]
node dalam binary treee boleh memiliki paling banyak dua child (anaksimpul),
secara khusus anaknya dinamakan kiri dan [Link] Tree merupakan
himpunan vertex-vertex yang terdiri dari 2 subtree(dengan disjoint) yaitu subtree
kiri dan subtree kanan. Setiap vertex dalam binarytree mempunyai derajat keluar
max = 2
BINERY TREE
 BINERY TREE
Sebuah pohon biner adalah grafik asiklis yang terhubung dimana
setiaptingkatan dari susut tidak lebih dari 3. Ini dapat ditunjukkan bahwa
dalam pohonbiner manapun, terdapat persis dua atau lebih simpul dengan
tingkat satu daripadayang terdapat dengan tingkat tiga, tetapi bisa terdapat
angka apa saja dari simpul dengan tingkat dua. Sebuah pohon biner berakar
merupakan sebuah grafik yangmempunyai satu dari sudutnya dengan
tingkat tidak lebih dari dua sebagai akar.
Dengan akar yang dipilih, setiap sudut akan memiliki ayah khusus,
dandiatas dua anak bagaimanapun juga, sejauh ini terdapat keterbatasan
informasiuntuk membedakan antara anak kiri atau kanan. Jika kita
membuang keperluanyang tak terkoneksi, membolehkan bermacam koneksi
dalam komponen di grafik,kita memanggil struktur sebuah hutan.
 ISTILAH DALAM TREE
1. Predesesor
Node yang berada diatas node tertentu. (contoh : B predesesor dari E dan F)
2. Succesor
Node yang berada dibawah node tertentu. (contoh : E dan F merupakan succesordari 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)
 ISTILAH DALAM TREE
7. Sibling
Node yang memiliki parent yang sama dengan satu node. (contoh : E dan F adalahsibling)
8. Subtree
Bagian dari tree yang berupa suatu node beserta descendant-nya (contoh : SubtreeB, 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 = 3)
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 derajat3, node B memiliki derajat 2)
 ISTILAH PADA POHON BINER
1. Pohon Biner Penuh (Full Binary Tree)
Semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang
memiliki panjang ruas yang sama.
2. Pohon Biner Lengkap (Complete Binary Tree)
Hampir sama dengan Pohon BinerPenuh, semua simpul (kecuali
daun) memiliki 2 anak tetapi tiap cabang memiliki panjang ruas
berbeda.
3. Pohon Biner Similer
Dua pohon yang memiliki struktur yang sama tetapi informasinya
berbeda.
4. Pohon Biner Ekivalent
Dua pohon yang memiliki struktur dan informasi yang sama.
5. Pohon Biner Miring (Skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu anak / turunan
kecuali daun.
 SIFAT UTAMA POHON BERAKAR
1. Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edgeadalah (n-1).
2. Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memilikiderajat keluar
>= 0, dan derajat masuk = 0.
3. Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebutberderajat
keluar = 0, dan berderajat masuk = 1.
4. Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yangLevelnya = 1
sampai dengan Level ke - n pada daun paling bawah. Simpul yangmempunyai Level sama
disebut Bersaudara atau Brother atau Stribling.
5. Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakanLevel
tertinggi
6. Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf)pada Pohon.
7. Banyaknya Simpul Maksimum sampai Level N adalah :

8. Banyaknya Simpul untuk setiap Level I adalah :

 KUNJUNGAN PADA POHON BINER
1. Kunjungan secara preorder ( Depth
First Order), mempunyai urutan
a. Cetak isi simpul yang dikunjungi (
simpul akar )
b. Kunjungi cabang kiri
c. Kunjungi cabang kanan .
 KUNJUNGAN PADA POHON BINER
2. Kunjungan secara inorder
( symetric order) mempunyai
urutan :
a. Kunjungi cabang kiri
b. Cetak isi simpul yang
dikunjungi (simpul akar)
c. Kunjungi cabang kanan
 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 ).
 APLIKASI POHON BINER
Pada bagian ini akan dibahas tentang
bagaimana menyusun sebuah PohonBiner
yang apabila dikunjungi secara PreOrder
akan menghasilkan Notasi
Prefix,kunjungan secara InOrder
menghasilkan Notasi Infix, dan
kunjungan PostOrder menghasilkan
Notasi Postfix.
 APLIKASI POHON BINER
1. PrefixYaitu notasi yang terbentuk atas operator dengan operand, dimana
operatorberada didepan operand.
Contoh : A + B * C (Infix)Maka notasi prefixnya adalah + A*BC
2. InfixYaitu notasi yang terbentuk atas operator dengan operand, dimana
operatorberada diantara operand. Notasi ini hanya dikenal oleh manusia
dan selaludigunakan dalam perhitungan aritmatika.
Contoh : A + B * C( A + B ) * CA – ( B + C ) * D ^ E
3. PostfixYaitu notasi yang terbentuk atas operator dengan operand, dimana
operatorberada dibelakang operand. Notasi ini hanya dikenal oleh processor
dan dipahamidalam ALU.
Contoh : A + B * C (Infix). Maka notasi postfixnya adalah ABC*+
 KESIMPULAN
Tree merupakan salah satu bentuk struktur data tidak linear
yangmenggambarkan hubungan yang bersifat hirarkis (hubungan one
to many) antaraelemen-elemen. Tree bisa didefinisikan sebagai
kumpulan simpul/node dengan satu elemen khusus yang disebut Root
dan node lainnya. Tree juga adalah suatu graphyang acyclic, simple,
connected yang tidak mengandung loop.
TERIMA KASIH><