Pertemuan – 8

Struktur Data Pohon/Tree Dipersiapkan oleh : Boldson Herdianto S., S.Kom., MMSI.

POHON / TREE Struktur Data

Struktur data yang terdiri dari akar (root), dan

subpohon-subpohon dalam susunan berhirarki

ROOT/AKAR

Simpul

/ Node

/ Vertex

TINGKAT (LEVEL) DAN KEDALAMAN

(DEPTH) POHON

Tingkat dimulai dari 0, 1, 2 dst

Kedalaman dimulai dari 1, 2, 3, dst (tingkat + 1)

TINGKAT 0

TINGKAT 1

TINGKAT 2

TINGKAT 3

Struktur Data Pohon

DERAJAT SIMPUL

Derajat 2

Derajat 2

Derajat 0

Derajat 3

Derajat = jumlah anak yang dimiliki sebuah

simpul

Struktur Data Pohon

NODE INTERNAL & EKSTERNAL

Node Internal

Node Internal

Node Eksternal

Node Internal = node yang memiliki anak

Node eksternal = node yang tidak memiliki anak (daun)

Struktur Data Pohon

NOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Diagram Pohon

NOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Diagram Venn

(A(B(D,E(I,J)),C(F,G,H)))

atau

(A (B(D)(E(I)(J))) (C(F)(G)(H)))

NOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Notasi Kurung

NOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Notasi Tingkat

LATIHAN NOTASI POHON

Buat dalam diagram venn, notasi kurung dan notasi

tingkat

Struktur Data Pohon

X

Y R S

Q T W U Z

P M N

POHON BINER

Struktur Data Pohon yang maksimal memiliki 2 anak.

Struktur Data Pohon

JUMLAH MAKS NODE

Jumlah maksimum node pada setiap tingkat adalah

2 pangkat n

Struktur Data Pohon

KAMUS DATA POHON BINER Struktur Data Pohon

Kamus Data

Type BTree = record <

Kiri : BTree

Info : char

Kanan : BTree >

P : BTree

Kiri Info Kanan

FISIK POHON BINER Struktur Data Pohon

FISIK POHON BINER Struktur Data Pohon

OPERASI DASAR Struktur Data Pohon

CreateTree(P) : membuat pohon biner baru

EmptyTree(P) : memeriksa apakah pohon biner kosong ?

InsertTree(P,N) : menyisipkan simpul baru

DeleteTree(P,N) : menghapus simpul

Info(P) : mengetahui/mencetak isi simpul P

Traversal : penelusuran pohon biner

POHON BINER TERURUT Struktur Data Pohon

12 22 8 19 10 9 20 4 2 6

POHON BINER TERURUT Struktur Data Pohon

12 22 8 19 10 9 20 4 2 6

POHON BINER TERURUT

Procedure SisipUrutBTree(input/output P:BTree, input N:integer)

If EmptyTree(P) then

CreateTree(P)

InsertTree(P,N) {untuk info(P)}

Else If N < info(P) then

SisipUrutBTree(P .kiri,N)

else

SisipUrutBTree(P .kanan,N)

Endif

Endif

menyisipkan simpul dgn aturan : simpul yang lebih kecil

diletakkan di sebelah kiri simpul

BUAT POHON BINER TERURUT Struktur Data Pohon

2, 3, 4, 5, 50, 10,

15, 13, 20, 12, 10,

5, 7

LATIHAN NOTASI POHON Struktur Data Pohon

2

2, 3, 4, 5, 50, 10, 15,

13, 20, 12, 10, 5, 7

3

4

5

5

0 1

0 1

5

1

3

2

0

1

2 1

0

5

7

PENELUSURAN POHON BINER Struktur Data Pohon

PENELUSURAN POHON BINER Struktur Data Pohon

Preorder (S L R) ???

Postorder (L R S) ???

Inorder (L S R)???

Pre : H F B A C G L J I M

Post : A C B G F I J M L H

In : A B C F G H I J L M

KONVERSI POHON

KE POHON BINER

Anak pertama menjadi anak kiri, anak ke-2 menjadi

cucu kanan, ke-3 jadi cicit kanan dst

LATIHAN KONVERSI KE POHON BINER

Konversi pohon umum ini ke pohon biner

Struktur Data Pohon

X

Y R S

Q T W U Z

P M N

LATIHAN KONVERSI KE POHON UMUM

Konversi pohon biner ini ke pohon umum

Struktur Data Pohon

A

B

C

D

X

Y

X E I

J

PEMBENTUKAN POHON

DARI HASIL TRAVERSAL DAN DERAJAT SIMPUL

Preorder : U V W X Y

Derajat : 2 2 0 0 0

Hasilnya :

Cari yang derajat bukan NOL

PEMBENTUKAN POHON

DARI HASIL TRAVERSAL DAN DERAJAT SIMPUL

Preorder : U V W X Y

Derajat : 2 2 0 0 0

Hasilnya :

Kita lanjutkan

untuk yang satu ini …..