TUGAS LATIHAN PERTEMUAN 14

PERTEMUAN 14

MATA KULIAH  : STRUKTUR DATA

POHON BINER

Pohon (Tree) adalah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung maka pada pohon selalu terdapat path atau jalur yang menghubungkan kedua simpul di dalam pohon. Pohon dilengkapi dengan Root (akar).

I. Ilustrasi

II. Istilah

a. Pohon :susunan dari satu atau lebih simpul (node) yang terdiri dari satu simpul khusus yang disebut akat (root) sedang sisanya membentuk subtree dari akar.

b. Simpul/Vertex/Node : A, B,…, N

c. Busur/Edge/Arc : garis yang menghubungkan antar simpul

d. Superordinat/Father/Parent dan Subordinat/Son/Children.

    i. Simpul A merupakan superordinat bagi simpul B, C, D

    ii. Simpul B, C,D merupakan subordinat bagi simpul A

e. Root/Akar : simpul yang tidak mempunyai superordinat. Pada gambar diatas : A.

f. Leaf/Daun : simpul yang tidak mempunyai subordinat. Pada gambar diatas : C, E, G, I, J, K, L, M, N.

g. Level/Tingkat : Simpul A berada pada level 0, simpul B, C, D berada pada level 1, dst.

h. Depth/kedalaman : Level tertinggi dari suatu pohon. Pada gambar 1, depth = 3.

i. Derajat/Degree sebuah simpul jumlah simpul subordinat dari simpul tersebut.

j. Derajat/degree sebuah pohon adalah derajat tertinggi dari derajat simpul yang ada pada pohon tersebut.

III. M-ary Tree dan Binary Tree

M-ary atau K-ary. M atau K menyatakan derajat dari pohon.

Contoh pohon 3-ary :

Binary Tree. Khusus untuk K = 2 disebut pohon Binary Tree atauphon biner.

Contoh pohon biner :

IV. Struktur Pohon

struct Node

{ 

int INFO; 

  struct Node *Link1; 

  struct Node *Link2; 

  struct Node *Link3; 

};

struct Node{ 

  int INFO; 

  struct Node *LEFT; 

  struct Node *RIGHT; 

};

V. LINK

Link : Pointer yang digunakan untuk menunjuk simpul subordinat

Null-Link : link yang bernilai Null, yaitu link yang tidak menunjuk subordinat

Bukan Null-Link/Busur : link yang menunjuk simpul subordinat.

Jika :

n : jumlah simpul

k : derajat pohon

maka berlaku hubungan :

Jumlah Link : n x k

Jumlah Null-Link : n(k-1)+1

Jumlah Bukan Null-Link : n-1

Dari gambar 4, diperoleh :

n = 7, k = 3

Jumlah Link : 7 x 3 = 21

Jumlah Null-Link : 7(2)+1 = 15

Jumlah Bukan Null-Link : 7-1 = 6

V. Konversi K-ary ke Binary

Aturan yang digunakan :

• Cabang kiri Binary = anak paling kiri K-ary
• Cabang kanan Binary = saudaranya pada K-ary

Contoh :

VI. Pohon Biner

Pada pohon Full Binary Tree berlaku :

1. Pada level k, jumlah simpul = 2k

2. Pohon dengan kedalaman d, jumlah simpul = 2^((d+1)) -1

3. Pohon dengan level k,

    a. Jumlah simpul daun = 2^k

    b. Jumlah simpul bukan daun = 2^k - 1

4. Bilajumlah seluruh simpul = n,

    a. Kedalaman pohon = log2(n+1)-1

Complete Binary Tree

Pada Complete Binary Tree :

1. Setiap simpul yang berada dibawah level d-1, mempunyai dua subordinat

2. Bila pada level d-1 subpohon kanan ada simpul yang mempunyai subordinat maka setiap simpulpada level d-1 subpohon kiri harus mempunyai subordinat kiri dan kanan.

Contoh bukan Complete Binary Tree :

VII. Penomoran Simpul Pohon Biner

1. Bila sebuah simpul bernomor n, maka subordinat kiri bernomor 2n dan subordinat kanan bernomor 2n+1

2. Simpul awal diberi nomor 1

Representasi pohon biner kedalam array :