adalah salah satu bentuk sirkuit salah satu bentuk graph terhubung yang tidak mengandung sirkuit.
karena merupakan graph terhubung,maka pada pohon (tree) selalu terdapat path yang menghubungkan setiap simpul dalam pohon.
tree dapat juga didefinisikan sebagai kumpulan elemen yang salah satu elemenya di sebut akar(root) dan sisa elemen lainya (simpul)yang terpecah menjadi sebuah himpunan yang saling tidak berhubungan yang di sebut sub pohon (subtree) atau cabang.
dibawah ini gambar proses pembentukan pohon
dengan membuat diagram venn seperti gambar di bawah ini Sifat sifat pohon
- Jika Pohon mempunyai simpul sebanyak n,maka banyaknya ruas atau edge adalah n-1
- Mempunyai simpul khusus yang di sebut root,jika simpul tersebut mempunyai derajat keluar >=0,dan derajat masuk = 0
- Mempunyai simpul yang disebut daun/leaf,jika simpul tersebut berderajat keluar = 0,dan berderajat masuk = 1
- Setiap simpul mempunyai Tingkatan/level yang dimulai dari root yang levelnya =1,sampai dengan level ke-n yang berada pada daun yang paling bawah.simpul yang mempunyai level sama di sebut bersaudara
- Pohon mempunyai ketinggian atau kedalaman atau height ,yang merupakan level tertinggi.
- Pohon mempunyai berat atau weight,yang banyaknya daun pada pohon.
- cara kedua
- Cara ketiga
hasilnya : (P(Q(R,S)),T(U(V,W)))
- Cara Keempat
dengan menggunakan notasi tingkat dan notasi garis
POHON BINAR (BINARY TREE)
Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur ini biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan hierarkykal antara elemen-elemen mereka.
Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah pohon binary. Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar T didefinisikan terdiri dari sebuah himpunan hingga elemen yang disebut simpul
Karakteristik Pohon binar
- Setiap simpul paling banyak hanya memiliki dua buah anak.
- Derajat tertinggi dari setiap simpul adalah dua
- Dibedakan antara cabang kiri dan cabang kanan
- Dimmungkinkan tidak memiliki simpul
dibawah ini contoh pohon binar dengan cabang kiri dan kanan
Istilah pada pohon binar(binary tree)
- Pohon binar penuh (full binary tree)
- Pohon Binar lengkap(complate binary tree)
- Pohon biner Similer
- Pohon biner Ekivalent
- Pohon biner Miring(skewed Tree)
Deklarasi Pohon Biner dengan program C++
Dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke arah cabang kiri dan cabang kanan dan informasi yang akan di simpan dalam simpul tersebut. (klik untuk memperbesar gambar)
Penyajian Pohon Binar (binary tree)
- Tree dapat dibuat dengan menggunakan linked list secara rekursif
- Linked list yang digunakan adalah double linked list non circural
- data yang pertama kali masuk akan menjadi node root
- data yang lebih kecil dari node root akan masuk dan menempati node kiri dari node root,sedangkan jika lebih besar akan masuk dan menempati node sebelah kanan node root
0 komentar:
Posting Komentar