Struktur Pohon / Tree

TREE (POHON)
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.
Sifat sifat pohon



1. Jika Pohon mempunyai simpul sebanyak n,maka banyaknya ruas atau edge adalah n-1
2. Mempunyai simpul khusus yang di sebut root,jika simpul tersebut mempunyai derajat keluar >=0,dan derajat masuk = 0
3. Mempunyai simpul yang disebut daun/leaf,jika simpul tersebut berderajat keluar = 0,dan berderajat masuk = 1
4. 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
5. Pohon mempunyai ketinggian atau kedalaman atau height ,yang merupakan level tertinggi.
6. Pohon mempunyai berat atau weight,yang banyaknya daun pada pohon.


Hutan (forest) adalah Kumpulan pohon yang tidak saling berhubungan




(klik untuk memperbesar gambar) Cara menggambarkan bentuk pohon :

* cara pertama

merupakan cara paling banyak digunakan dan paling mudah digunakan,caranya seperti gambar di atas.

* cara kedua

dengan membuat diagram venn seperti gambar di bawah ini

* Cara ketiga

dengan cara menggunakan notasi kurung untuk gambar pada diagram venn di atas.
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

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. 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)

semua simpul (kecuali daun) memiliki dua anak dan tiap cabang memiliki panjang ruas yang sama

* Pohon Binar lengkap(complate binary tree)

hampir sama dengan pohon biner penuh,bedanya tiap cabang memiliki ruas berbeda

* Pohon biner Similer

Dua pohon yang memiliki struktur sama tapi informasinya berbeda

* Pohon biner Ekivalent

Dua pohon yang memiliki struktur sama dan informasi yang sama

* 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 arah cabang kiri dan cabang kanan dan informasi yang akan di simpan dalam simpul tersebut.


* 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