struktur data pohon

29
Kuliah ke-9 Struktur Data Pohon/Tree (Bab 6) Informatics Engineering Dept. TRUNOJOYO UNIVERSITY

Upload: muhammad-luqman-hakim-haiqal

Post on 20-Oct-2015

126 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Struktur Data Pohon

Kuliah ke-9

Struktur Data Pohon/Tree (Bab 6)

Informatics Engineering Dept.

TRUNOJOYO UNIVERSITY

Page 2: Struktur Data Pohon

POHON / TREEPOHON / TREEStruktur Data

Struktur data yang terdiri dari akar (root), dan subpohon-subpohon dalam susunan berhirarki

ROOT/AKAR

Simpul /

Node / Vertex

Simpul /

Node / Vertex

Page 3: Struktur Data Pohon

TINGKAT (LEVEL) DAN KEDALAMAN TINGKAT (LEVEL) DAN KEDALAMAN (DEPTH) POHON(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

Page 4: Struktur Data Pohon

DERAJAT SIMPULDERAJAT SIMPUL

Derajat 2

Derajat 2

Derajat 0

Derajat 3

Derajat = jumlah anak yang dimiliki sebuah simpul

Struktur Data Pohon

Page 5: Struktur Data Pohon

NODE INTERNAL & EKSTERNALNODE 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

Page 6: Struktur Data Pohon

NOTASI POHONNOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Diagram PohonDiagram Pohon

Page 7: Struktur Data Pohon

NOTASI POHONNOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Diagram VennDiagram Venn

Page 8: Struktur Data Pohon

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

atau

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

NOTASI POHONNOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Notasi KurungNotasi Kurung

Page 9: Struktur Data Pohon

NOTASI POHONNOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Notasi TingkatNotasi Tingkat

Page 10: Struktur Data Pohon

LATIHAN NOTASI POHONLATIHAN NOTASI POHON

Buat dalam diagram venn, notasi kurung dan notasi tingkat

Struktur Data Pohon

XX

YY RR SS

QQ TT WWUU ZZ

PP MM NN

Page 11: Struktur Data Pohon

POHON BINERPOHON BINER

Struktur Data Pohon yang maksimal memiliki 2 anak.

Struktur Data Pohon

Page 12: Struktur Data Pohon

JUMLAH MAKS NODEJUMLAH MAKS NODE

Jumlah maksimum node pada setiap tingkat adalah

2 pangkat n

Struktur Data Pohon

Page 13: Struktur Data Pohon

KAMUS DATA POHON BINERKAMUS DATA POHON BINERStruktur Data Pohon

Kamus Data

Type BTree = record <

Kiri : BTree

Info : char

Kanan : BTree >

P : BTree

Kiri Info Kanan

Page 14: Struktur Data Pohon

FISIK POHON BINERFISIK POHON BINERStruktur Data Pohon

Page 15: Struktur Data Pohon

FISIK POHON BINERFISIK POHON BINERStruktur Data Pohon

Page 16: Struktur Data Pohon

OPERASI DASAR OPERASI DASAR Struktur Data Pohon

CreateTree(P) CreateTree(P) : membuat pohon biner baru: membuat pohon biner baru

EmptyTree(P) EmptyTree(P) : memeriksa apakah pohon biner kosong ?: memeriksa apakah pohon biner kosong ?

InsertTree(P,N)InsertTree(P,N) : menyisipkan simpul baru: menyisipkan simpul baru

DeleteTree(P,N)DeleteTree(P,N) : menghapus simpul: menghapus simpul

Info(P)Info(P) : mengetahui/mencetak isi simpul P: mengetahui/mencetak isi simpul P

Traversal Traversal : penelusuran pohon biner: penelusuran pohon biner

Page 17: Struktur Data Pohon

POHON BINER TERURUT POHON BINER TERURUT Struktur Data Pohon

12 22 8 19 10 9 20 4 2 6

Page 18: Struktur Data Pohon

POHON BINER TERURUT POHON BINER TERURUT Struktur Data Pohon

12 22 8 19 10 9 20 4 2 6

Page 19: Struktur Data Pohon

POHON BINER TERURUT 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 menyisipkan simpul dgn aturan : simpul yang lebih kecil diletakkan di sebelah kiri simpuldiletakkan di sebelah kiri simpul

Page 20: Struktur Data Pohon

BUAT POHON BINER TERURUT BUAT POHON BINER TERURUT Struktur Data Pohon

2, 3, 4, 5, 50, 10, 15, 13, 20, 12, 10, 5, 7

Page 21: Struktur Data Pohon

LATIHAN NOTASI POHONLATIHAN NOTASI POHONStruktur Data Pohon

22

2, 3, 4, 5, 50, 10, 15, 13, 20, 12, 10, 5, 7

33

44

55

50

50

10

10 1

5

15

13

13

20

20

12

12

10

10

55

77

Page 22: Struktur Data Pohon

PENELUSURAN POHON BINERPENELUSURAN POHON BINERStruktur Data Pohon

Page 23: Struktur Data Pohon

PENELUSURAN POHON BINERPENELUSURAN POHON BINERStruktur Data Pohon

Preorder (S L R) ???

Postorder (L R S) ???

Inorder (L S R)???

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

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

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

Page 24: Struktur Data Pohon

KONVERSI POHON KONVERSI POHON KE POHON BINERKE POHON BINER

Anak pertama menjadi anak kiri, anak ke-2 menjadi cucu kanan, ke-3 jadi cicit kanan dst

Page 25: Struktur Data Pohon

LATIHAN KONVERSI KE POHON BINERLATIHAN KONVERSI KE POHON BINER

Konversi pohon umum ini ke pohon biner

Struktur Data Pohon

XX

YY RR SS

QQ TT WWUU ZZ

PP MM NN

Page 26: Struktur Data Pohon

LATIHAN KONVERSI KE POHON UMUMLATIHAN KONVERSI KE POHON UMUM

Konversi pohon biner ini ke pohon umum

Struktur Data Pohon

AA

BB

CC

DD

XX

YY

XX EEII

JJ

Page 27: Struktur Data Pohon

PEMBENTUKAN POHONPEMBENTUKAN POHONDARI HASIL TRAVERSAL DAN DERAJAT SIMPULDARI HASIL TRAVERSAL DAN DERAJAT SIMPUL

Preorder : U V W X Y

Derajat : 2 2 0 0 0

Hasilnya :

Cari yang derajat bukan NOL

Page 28: Struktur Data Pohon

PEMBENTUKAN POHONPEMBENTUKAN POHONDARI HASIL TRAVERSAL DAN DERAJAT SIMPULDARI HASIL TRAVERSAL DAN DERAJAT SIMPUL

Preorder : U V W X Y

Derajat : 2 2 0 0 0

Hasilnya :

Page 29: Struktur Data Pohon

Kita lanjutkan Kita lanjutkan untuk yang satu ini …..untuk yang satu ini …..