Tree

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

Notde lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan
satu sama lain (disebut Subtree). Untuk lebih jelasnya, di bawah akan diuraikan istilah-
istilah umum dalam tree.

Predecessor : Node yang berada di atas node tertentu
Successor : Node yang berada dibawah node tertentu
Ancestor : Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
Descendant : Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
Parent : Predecessor satu level di atas suatu node
Child : Successor satu level di bawah suatu node
Sibling : Node-node yang memiliki parent yang sama dengan suatu node
Subtree : Bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
Size : Banyaknya node dalam suatu tree
Height : Banyaknya tingkatan / level dalam suatu tree
Root : Satu-satunya node khusus dalam tree yang tak punyak predecessor
Leaf : Node-node dalam tree yang tak memiliki successor
Degree : Banyaknya child yang dimiliki suatu node



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.