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

POHON / TREEStruktur DataStruktur data yang terdiri dari akar (root), dan subpohon-subpohon dalam susunan berhirarkiROOT/AKARSimpul / Node / Vertex

TINGKAT (LEVEL) DAN KEDALAMAN (DEPTH) POHONTingkat dimulai dari 0, 1, 2 dstKedalaman dimulai dari 1, 2, 3, dst (tingkat + 1)TINGKAT 0TINGKAT 1TINGKAT 2TINGKAT 3Struktur Data Pohon

DERAJAT SIMPULDerajat 2Derajat 2Derajat 0Derajat 3Derajat = jumlah anak yang dimiliki sebuah simpulStruktur Data Pohon

NODE INTERNAL & EKSTERNALNode InternalNode InternalNode EksternalNode Internal = node yang memiliki anakNode eksternal = node yang tidak memiliki anak (daun)Struktur Data Pohon

NOTASI POHONCara penulisan / penggambaran suatu pohonStruktur Data PohonDiagram Pohon

NOTASI POHONCara penulisan / penggambaran suatu pohonStruktur Data PohonDiagram Venn

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

(A (B(D)(E(I)(J))) (C(F)(G)(H))) Cara penulisan / penggambaran suatu pohonStruktur Data PohonNotasi Kurung

NOTASI POHONCara penulisan / penggambaran suatu pohonStruktur Data PohonNotasi Tingkat

LATIHAN NOTASI POHONBuat dalam diagram venn, notasi kurung dan notasi tingkatStruktur Data PohonXYRSQTWUZPMN

POHON BINERStruktur Data Pohon yang maksimal memiliki 2 anak.Struktur Data Pohon

JUMLAH MAKS NODEJumlah maksimum node pada setiap tingkat adalah 2 pangkat nStruktur Data Pohon

KAMUS DATA POHON BINERStruktur Data Pohon

FISIK POHON BINERStruktur Data Pohon

FISIK POHON BINERStruktur Data Pohon

OPERASI DASAR Struktur Data PohonCreateTree(P) : membuat pohon biner baruEmptyTree(P) : memeriksa apakah pohon biner kosong ?InsertTree(P,N): menyisipkan simpul baruDeleteTree(P,N): menghapus simpulInfo(P): mengetahui/mencetak isi simpul PTraversal : penelusuran pohon biner

POHON BINER TERURUT Struktur Data Pohon12 22 8 19 10 9 20 4 2 6

POHON BINER TERURUT Struktur Data Pohon12 22 8 19 10 9 20 4 2 6

POHON BINER TERURUT Procedure SisipUrutBTree(input/output P:BTree, input N:integer)If EmptyTree(P) thenCreateTree(P)InsertTree(P,N){untuk info(P)}Else If N < info(P) then SisipUrutBTree(P.kiri,N)else SisipUrutBTree(P.kanan,N)EndifEndifmenyisipkan simpul dgn aturan : simpul yang lebih kecil diletakkan di sebelah kiri simpul

BUAT POHON BINER TERURUT Struktur Data Pohon2, 3, 4, 5, 50, 10, 15, 13, 20, 12, 10, 5, 7

LATIHAN NOTASI POHONStruktur Data Pohon22, 3, 4, 5, 50, 10, 15, 13, 20, 12, 10, 5, 73455010151320121057

PENELUSURAN POHON BINERStruktur Data Pohon

PENELUSURAN POHON BINERStruktur Data PohonPreorder (S L R) ???Postorder (L R S) ???Inorder (L S R)???Pre : H F B A C G L J I MPost : A C B G F I J M L HIn : A B C F G H I J L M

KONVERSI POHON KE POHON BINERAnak pertama menjadi anak kiri, anak ke-2 menjadi cucu kanan, ke-3 jadi cicit kanan dst

LATIHAN KONVERSI KE POHON BINERKonversi pohon umum ini ke pohon binerStruktur Data PohonXYRSQTWUZPMN

LATIHAN KONVERSI KE POHON UMUMKonversi pohon biner ini ke pohon umumStruktur Data PohonABCDXYXEIJ

PEMBENTUKAN POHONDARI HASIL TRAVERSAL DAN DERAJAT SIMPULPreorder : U V W X YDerajat: 2 2 0 0 0Hasilnya :Cari yang derajat bukan NOL

PEMBENTUKAN POHONDARI HASIL TRAVERSAL DAN DERAJAT SIMPULPreorder : U V W X YDerajat: 2 2 0 0 0Hasilnya :

Kita lanjutkan untuk yang satu ini ..

Latihan :Kiri(100)Kanan(100)Kiri(Kanan(100))Kanan(kiri(100))Kiri(Kiri(100))Kanan(kanan(100))

Kiri(Kanan(200))Kanan(Kiri(200))

INFO(Kiri(100))INFO(Kanan(100))INFO(Kiri(Kanan(100)))INFO(Kanan(kiri(100)))INFO(Kiri(Kiri(100)))INFO(Kanan(kanan(100)))