STRUKTUR DATA

Deskripsi Tree

—  Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon.

—  Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah.

—  Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.

- Contoh penggunaan struktur pohon :

·         Silsilah keluarga

·         Parse Tree (pada compiler)

·         Struktur File

·         Pertandingan

- Operasi-operasi Pada Tree

·         —  Insert: menambah node ke dalam Tree secara rekursif.  Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri.  Untuk data pertama akan menjadi elemen root.

·         —  Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu.  Syaratnya adalah tree tidak boleh kosong.

·         —  Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.

·         —  Count: menghitung jumlah node dalam Tree.

·         —  Height : mengetahui kedalaman sebuah Tree.

·         —  Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree.

·         —  Child : mengetahui anak dari sebuah node (jika punya).

·           Daun/leaf : Simpul yang derajat = 0 disebut daun / leaf

·           Hubungan antar simpul : bapak, ,anak, paman, dll

·           Tingkat (level)

·           Derajat (degree)

·           Tinggi (height)/kedalaman (depth) : height = tingkat maksimum – 1

·            Ancestor : semua simpul yang terdapat pada lintasan/jalur dari akar sampai simpul tersebut

·            Forest (Hutan) : kumpulan sejumlah pohon yang tidak saling berhubungan

- Jenis Tree

·         Berdasarkan banyaknya anak :

1.       binary tree / pedigree chart : Complete Binary Tree tingkat N,Skewed BinaryTree

2.       Non Binary Tree (N-ary) & lineal chart


POHON BINER (TREE BINNERY) 

Tree adalah bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree juga bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root. 

Istilah-istilah : 

1. Pohon = kumpulan elemen, salah satunya berupa akar (root), yang lain berupa cabang (sub pohon) dimana antara cabang satu dengan yang lain tidak saling berhubungan. 
2. Node = elemen pohon yang berisi informasi dan penunjuk percabangan. 
3. Tingkat (Level) = akar ditentukan bertingkat 1 
4. derajat (Degre) = Banyaknya turunan dari suatu node. 
5. daun (Leaf) = Node yang berderajat 0, dinamakan juga sebagai node eksternal. Node lain selain akar disebut Node internal. 
6. Tinggi (high)/ kedalaman (depth) = tingkat maksimum node dalam poho -1. 
7. Anchestor suatu node yang terletak dalam satu jalur dengan node tersebut dari akar samapi node yang ditinjau. 
8. Hutan (forest) = kumpulan pohon yang saling tidak berhubungan. 
9. Pohon beraturan (ordered tree) = urutan hubungan suatu node dengan node lain diperhatikan. 


Jenis-Jenis Tree : 

- Binary Tree 
Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut tiap node dalam binary tree hanya boleh memiliki paling banyak dua child. Jenis- Jenis Binary Tree : 

- Full Binary Tree 
Jenis binary tree ini tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama. 

- Complete Binary Tree 
Jenis ini mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki 2 child. 

- Skewed Binary Tree 
Skewed Binary Tree adalah Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child. 



Implementasi Binary Tree : 

Binary tree dapat diimplementasikan dalam C++ dengan menggunakan double linkedlist. 

# Ada 3 urutan dasar yang dapat digunakan untuk mengunjungi pohon, yaitu : 
- PreOrder : cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child. 
- InOrder : kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right Child. 
- PostOrder : kunjungi Left Child, kunjungi Right Child cetak isi node yang dikunjungi.