pohon berakar

Terminologi pada Pohon Berakar

Berikut merupakan daftar terminologi yang penting pada pohon berakar.Simpul - simpul pada pohon diberi label untuk mengacu simpu mana yang dimaksudkan.Kebanyakan terminologi pohon yang ditulis di bawah ini diadopsi dari terminologi botani dan silsilah keluarga.

·         Child atau children (Anak) dan parent (orangtua)

·         Path (lintasan)

·         Descendant (Keturunan) dan ancestor (leluhur)

·         Sibling (saudara kandung)

·         Subtree (subpohon)

·         Degree (derajat)

·         Leaf (daun)

·         Internal nodes (simpul dalam)

·         Level (tingkat)

·         Height (tinggi) atau depth (kedalaman)

Child atau children (Anak) dan parent (orangtua)

Simpul y disebut anak apabila simpul x jika ada sisi dari simpul x ke y dan Orangtua dari simpul y adalah simpul x.
Pada gambar G1 : 

·         Simpul b, c dan d --> anak dari simpul a 

·         Simpul e dan f,  anak dari simpul b 

·         Simpul a, orangtua dari simpul b, c dan d 

·         Simpul b,orangtua dari simpul e dan f  

Path (lintasan)

Lintasan dari simpul v_i ke simpul v_k merupakan  runtunan simpul-simpul v₁, v₂ ,…, v_k sedemikian hingga v_i adalah orangtua dari v_i+1 untuk 1 <= i <= K.
Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan, yaitu k – 1. 
Pada gambar G1 : 

·         Lintasan dari a ke j adalah a, b, e dan j 

·         Panjang lintasan dari a ke j adalah 3

Descendant (Keturunan) dan ancestor (leluhur)

x adalah leluhur dari simpul y jika terdapat lintasan dari simpul x ke simpul y di dalam pohon dan keturunan dari simpul x adalah simpul y.
Pada gambar G1 :

·         Simpul b adalah leluhur dari simpul h

·         Simpul h adalah keturunan dari simpul b

Sibling (saudara kandung)

Sibling atau saudara kandung adalah simpul yang berorangtua sama
Pada gambar G1 :

·         Simpul f saudara kandung dari e

·         Simpul g bukan saudara kandung dari e karena orangtua berbeda 

Subtree (subpohon) 

Subtree dengan x merupakan akarnya adalah subgraf T’ = (V’,E’) sedemikian hingga V’ mengandung x dan semua keturunannya dan E’ mengandung sisi-sisi dalam semua lintasan yang berasal dari x
Pada gambar G2 :

·         V’ = {b, e, f, h, i, j}

·         E’ = {(b, e), (b, f), (e, h), (e, i), (e, j)}

·         b adalah simpul akar 

Degree (derajat) 

Derajat sebuah simpul pohon berakar ialah jumlah subtree (jumlah anak) pada simpul tersebut. Derajat pohon berakar merupakan derajat keluar
Pada gambar G1 :

·         Derajat simpul a : 3, simpul b : 2, simpul c : 0 dan simpul d : 1

·         Derajat tertinggi (maksimum) : 3 

Leaf (daun)

Adalah simpul yang berderajat nol (tidak mempunyai anak) 
Pada gambar G1 :

·         Merupakan daun : simpul c, f, h, i, j, l dan m.

Internal nodes (simpul dalam) 

Adalah simpul yang mempunyai anak
Pada gambar di samping :

·         Merupakan simpul dalam : simpul b, d, e, g dan k

Level (tingkat) 

Akar mempunyai level = 0
Level simpul lainnya = 1 + panjang lintasan dari akar ke simpul tersebut (gambar G3).

Height (tinggi) atau depth (kedalaman)

Adalah level maksimum dari suatu pohon
Nama lain : panjang maksimum lintasan dari akar ke daun
Pada gambar di samping :

·         Pohon mempunyai tinggi atau kedalaman : 4

Ordered Tree (Pohon Berakar Terurut)

Adalah pohon berakar yang urutan anak-anaknya penting.

Pohon m-ary

Pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buah anak disebut pohon m-ary.

Pohon Biner

Adalah himpunan terbatas yang:

- mungkin kosong, atau

- terdiri dari sebuah simpul yang disebut akar

dan dua buah himpunan lain yang disjoint yang merupakan pohon biner, yang disebut

sebagai sub pohon kiri dan sub pohon kanan dari pohon biner tersebut

Perhatikanlah perbedaan pohon biner dengan pohon biasa : pohon biner mungkin kosong,

sedangkan pohon n-aire tidak mungkin kosong.

Pohon Seimbang (Balanced Tree)

Pohon seimbang terdiri dari :

• Pohon seimbang tingginya: perbedaan tinggi sub pohon kiri dengan sub pohon kanan

maksimum 1.

• Pohon seimbang banyaknya simpul: perbedaan banyaknya simpul sub pohon kiri

dengan sub pohon kanan maksimum 1.

Berikut ini adalah algoritma untuk pohon yang seimbang banyaknya simpulnya.

Pohon Biner Terurut (Binary Search Tree)

Pohon biner terurut P memiliki sifat seperti berikut  :

• Semua simpul subpohon kiri selalu < dari Info(P)

• Semua simpul subpohon kiri selalu > dari Info(P)

Untuk simpul yang sama nilainya : disimpan berapa kali muncul. Maka sebuah node P

akan menyimpan informasi : Info(P), Left(P), Right(P) , Count(P) yaitu banyaknya

kemunculan Info(P).

Macam – macam Binary Tree Traversal

Terdapat tiga macam binary tree traversal, yaitu:

Preorder Traversal,dimana: 

1. Mengunjungi simpul akar (root),
2. Melakukan traversal subpohon kiri (left subtree),
3. Melakukan traversal subpohon kanan (right subtree).

Inorder Traversal,dimana:

1. Melakukan traversal subpohon kiri (left subtree),
2. Mengunjungi simpul akar (root),
3. Melakukan traversal subpohon kanan (right subtree).

Postorder Traversal,dimana:

1. Melakukan traversal subpohon kiri (left subtree),
2. Melakukan traversal subpohon kanan (right subtree),
3. Mengunjungi simpul akar (root).

preorder 
letak operator di depan operand:
 * + a /b c - d * e f (Prefix)

Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.

inorder 
letak operator diantara operand :
 a + b / c * d - e * f (Infix )

Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).

postorder 
letak operator dibelakang operand :
 a b c / + d e f * - *  (Postfix) 

Contoh penulisan sufix adalah AB + , AB + C – , AB + CD -*.

Salah satu contoh proses pengubahan infix menjadi postfix dari karakter:

( A + B ) / (( C – D ) * E ^ F)

Karakter dibaca	Isi Stack	Karakter tercetak	Postfix yang terbentuk
(	(
A	(	A	A
+	( +
B		B	A B
)		+	A B +
/	/
(	/ (
(	/ ( (
C	/ ( (	C	A B + C
–	/ ( ( –
D	/ ( ( –	D	A B + C D
)	/ (	–	A B + C D –
*	/ ( *
E	/ ( *	E	A B + C D – E
^	/ ( * ^
F	/ ( * ^	F	A B + C D – E F
)	/ ( *	^	A B + C D – E F ^
	/ (	*	A B + C D – E F ^ *
	/
		/	A B + C D – E F ^ * /