TREE

 TREE ( POHON)

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya.

Istilah Istilah Dalam Tree (Pohon)

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 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 = 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 nodecontoh : Node A memiliki derajat 3, node B memiliki derajat 2)

Istilah Istilah Dasar Pada Tree yaitu

satu bentuk Graph terhubung yang tidak mengandung sirkuit.Karena merupakan Graph terhubung, maka pada Pohon (Tree) selalu terdapat Path atau Jalur yang menghubungkan setiap simpul dalam dua pohon.Pohon (Tree) dapat juga didefinisikan sebagai kumpulan elemen yang salah satu elemennya disebut dengan Akar (Root) dan sisa elemen lain (Simpul) yang terpecah menjadi sejumlah himpunan yang saling tidak berhubungan yang disebut dengan Subpohon (Subtree) atau cabang.

Pohon Binar (Binar Tree)

Struktur ini biasanya digunakan untuk menyajikan data yang mengandung hubungan hirarkial antara elemen-elemennya. Bentuk Pohon Berakar yang lebih mudah dikelola dalam komputer adalah Pohon Biner (Binary Tree) yang lebih dikenal sebagai Pohon Umum (General Tree) yang dapat 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 

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 Biner Penuh, 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

Penyajian Pohon Binar (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

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

5. Karakter ‘C’,karena lebih besar dari ‘A’, maka akan menempati cabang kanan.

6. Karakter ‘B’, karena lebih kecil dari ‘C’, maka akan menempati cabang kiri.

7. Karakter ‘L’, lebih besar dari ‘K’, maka menempati cabang kiri kanan.