Daftar Isi
Definisi Tree
Kumpulan Node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layaknya 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. Note terbagi menjadi himpunan himpunan yang saling tak terhubung satu sama lain ( Disebut SubTree). Untuk lebih jelasnya,
Dibawah akan di uraikan istilah Istilah umum dalam tree:
Predecesor adalah Node yang berada diatas node tertentu.
Successor adalah Node yang berada dibawah Node Tertentu.
Ancestor Adalah Seluruh Node yang terletak sebelum Node tertentu.
Descendant Adalah Seluruh Node yang terletak setelah Node tertentu dan terletak pada jalur yang sama.
Parent Adalah Predecessor satu level di atas suatu Node.
Child Adalah Successor satu Level di bawah suatu Node.
Sibling Adalah Node – Node yang memiliki parent yang sama.
Size Adalah Banyaknya Node dalam suatu Tree.
Height Adalah Banyaknya Tingkatan dalam suatu Tree.
Root Adalah Node Khusus yang tidak memiliki predecessor.
Leaf Adalah Node-node dalam Tree yang tidak meiliki Successor.
Degree adalah Banyaknya Child dalam suatu Node.
Jenis Jenis Tree
Tree dengan syarat bahwa tiap node Hanya boleh memiliki maksimal dua sub pohon dan kedua sub pohon harus terpisah.
Jenis Jenis Binary Tree:
- Full Binary Tree
Jenis ini tiap Nodenya (Kembali Leaf) Memiliki dua child dan tiap SubTree harus mempunyai panjang part yang sama.
- Complete Binary Tree
- Skewed Binary Tree
Operasi Operasi pada binary Tree:
- Create : Membentuk Binary tree baru yang masih kosong.
- Clear : Menggosokkan Binary Tree yang sudah ada.
- Empty : Function Untuk memeriksa apakah binary tree masih kosong.
- Insert : Memasukan sebuah node ke dalam Tree. Ada Tiga Pilihan.
- Insert : Sebagai Root, Left Child, Atau Right child. Khusus inset sebagai Root, Tree harus dalam kosong.
- Find : Mencari Root, Parent, Left Child, Atau Right Child dari suatu Node. (Tree Tak boleh kosong)
- Update: Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree Tidak boleh kosong)
- Retrieve : Mengetahui isi dari node yang ditunjukan poiter current (Tree Tidak boleh kosong)
- DeleteSub: Menghapus sebuah subtree (Node beserta seluruh descendantnya) yang di tunjukan current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.
- Characteristic: Mengetahui karakteristik dari suatu tree, Yakni : Size, Height, Serta Average leghtnya. Tree tidak boleh kosong. (Average Leght = [jumlahNodeLvl1*1+jml NodeLvl2*2+…+jmlNodeLvln*n/Size)
- Traverse: Mengunjungi seluruh node-node pada Tree. Masing-masing Sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada Tida cara traverse : Pre Order, In Order, Dan Post Order.
- PreOrder: Cetak isi node yang dikunjungi, Kunjungi Left Child, Kunjungi Reght Child.
- InOrder: Kunjungi Left Child, Cetak isi node yang dikunjungi, Kunjungi Reight Child.
- PostOrder: Kunjungi Left Child, Kunjungi Right Child, Cetak isi node yang dikunjungi.
AVL Tree
Ingin membuat Program ini
