Predecessor : node yang berada di atas node tertentu
Successor : node yang dibawah node tertentu
Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak sesudah pada jalur yang sama
Descendant : seluruh node yang terletak sesudah node tertentu dan terletak sesudah pada jalur yang sama
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
Soal Latihan Tree (Struktur Data C/C++)
1. Jelaskan secara lengkap definisi Tree?
2. Jelaskan Istilah-istilah umum dalam Tree :
a. Prodecessor
b. Successor
c. Ancestor
d. Descendant
e. Parent
f. Child
g. Sibling
h. Subtree
i. Size
j. Height
k. Root
l. Leaf
m. Degree
3. Sebutkan jenis-jenis Tree? Apa definisi dari Binary Tree, Full Binary Tree, Complete Binary Tree, Skewed Binary Tree?
Jawaban Soal Latihan Tree (Struktur Data C/C++)
1. Definisi tree : “Kumpulan elemen yang salah satu elemennya disebut dengan root (akar) dan sisa elemen yang lain disebut sebagai simpul (node/vertex) yang terpecah menjadi sejumlah himpunan yang tidak saling berhubungan satu sama lain, yang disebut subtree/cabang”.
2. a. Predecessor adalah simpul yang berada di atas simpul yang ditinjau. Contoh : Predecessor D adalah B.
b. Successor adalah simpul yang berada di bawah simpul yang ditinjau. Contoh : Successor D adalah I.
c. Ancestor suatu simpul adalah semua simpul yang terletak dalam satu jalur dengan simpul tersebut, dari akar sampai simul yang ditinjaunya. Contoh Ancestor L adalah A,C dan G.
d. Descendant adalah seluruh simpul yang terletak sesudah simpul tertentu dan terletak pada jalur yang sama. Contoh : Descendant E adalah J dan K.
e. Parent adalah simpul yang berada satu level di atas simpul yang ditinjau. Contoh : Parent J adalah E
f. Child, suatu node adalah semua node yang dapat dicapai oleh node tersebut dengan sebuah path saja. Sebagai contoh, child dari N1 adalah N2, N3, dan N4;
child dari N4 adalah N5 dan N6; dan sebagainya.
g. Sibling adalah simpul-simpul yang memiliki parent yang sama dengan simpul yang ditinjau. Contoh : Sibling J adalah K
h. Subtree, sisa elemen yang lain (yang disebut node) terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu sama
lain (disjoint),
i. Size : banyaknya node dalam suatu tree
j. Height, Tinggi (height) atau kedalaman (depth) suatu tree adalah tingkat maksimum dari tingkat dalam tree tersebut dikurangi 1. Contoh dalam tree di atas, mempunyai depth 4.
k. Root : satu-satunya node khusus dalam tree yang tak punya predecssor
l. Leaf, simpul yang memiliki derajat 0 (nol) atau node-node dalam tree yang tak memiliki seccessor.
m. Degree, menyatakan banyaknya anak/turunan di simpul tersebut. Contoh : Simpul A memiliki derajat 2 (B dan C), simpul yang memiliki derajat 0 (nol) disebut leaf (daun) seperti : I, J, K, L, N, dan O.
3. Jenis-jenis tree
a. 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, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.
b. Full Binary Tree, Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
c. Complete Binary Tree, Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
d. Skewed Binary Tree yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.