struktur data pohon

Kuliah ke-9

Struktur Data Pohon/Tree (Bab 6)

Informatics Engineering Dept.

TRUNOJOYO UNIVERSITY

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

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

DERAJAT SIMPULDERAJAT SIMPUL

Derajat 2

Derajat 2

Derajat 0

Derajat 3

Derajat = jumlah anak yang dimiliki sebuah simpul

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

NOTASI POHONNOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Diagram PohonDiagram Pohon

NOTASI POHONNOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Diagram VennDiagram Venn

(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

NOTASI POHONNOTASI POHON

Cara penulisan / penggambaran suatu pohon

Struktur Data Pohon

Notasi TingkatNotasi Tingkat

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

POHON BINERPOHON BINER

Struktur Data Pohon yang maksimal memiliki 2 anak.

Struktur Data Pohon

JUMLAH MAKS NODEJUMLAH MAKS NODE

Jumlah maksimum node pada setiap tingkat adalah

2 pangkat n

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

FISIK POHON BINERFISIK POHON BINERStruktur Data Pohon

FISIK POHON BINERFISIK POHON BINERStruktur 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

POHON BINER TERURUT POHON BINER TERURUT Struktur Data Pohon

12 22 8 19 10 9 20 4 2 6

POHON BINER TERURUT POHON BINER TERURUT Struktur Data Pohon

12 22 8 19 10 9 20 4 2 6

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

BUAT POHON BINER TERURUT BUAT POHON BINER TERURUT Struktur Data Pohon

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

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

PENELUSURAN POHON BINERPENELUSURAN POHON BINERStruktur 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

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

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

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

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

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 :

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