Data Structure Chapter 5b
TREE & BINARY TREE
Dahlia Widhyaestoeti, S.Kom
Agenda Hari Ini
Simpul Pohon Biner Proses (Operasi) pada Pohon Biner Penelusuran Pohon Biner
2
Simpul Pohon Biner ?
Sebuah pohon biner, salah satu simpulnya bernomor = 75, ditanya nilai simpul superordinat simpul tersebut adalah …
75
2n + 1 = 75 2n = 74 n = 37 A
Diketahui sebuah pohon biner dengan kedalaman = 3, maka a) Maksimum jumlah simpul pada level 3 = 15 b) Minimum jumlah simpul pada level 3 = 1 c) Maksimum jumlah seluruh simpul sampai dengan level 3 = 15 d) Minimum jumlah seluruh simpul sampai dengan level 3 = 4
B
C
D H
E I
J
F K
L
G M
N
O
3
Proses (Operasi) Pohon Biner Proses pada pohon biner merupakan satu rangkaian proses (atau fungsi-fungsi) yang dapat dibagi menjadi : 1. Inisialisasi 2. Pembuatan sebuah simpul 3. Pembuatan simpul akar 4. Penambahan (insert) simpul ke dalam sebuah pohon 5. Pembacaan / penelusuran pohon biner
4
Proses (Operasi) Pohon Biner
Inisialisasi dan pembutan sebuah simpul Fungsi untuk inisialisasi :
Fungsi untuk pembuatan sebuah simpul :
Void Inisialisasi() { Root = Null; P = Null; }
Void BuatSimpul(char X) { P = (Simpul *) malloc(sizeof(simpul)); If (P! = NULL) { P>INFO = X; P>Left = NULL; P>Right = NULL; } Else { printf(“Memory Heap Full”); Exit(1); } }
P A
5
Proses (Operasi) Pohon Biner
Menjadikan sebuah simpul sebagai simpul akar suatu pohon P
Fungsi untuk menjadikan sebuah simpul sebagai simpul akar :
Root
A
Void BuatSimpulAkar() { If(Root == NULL) {if(P! = NULL) { Root = P; Root>Left = NULL; Root>Right = NULL; } Else printf(“\n Simpul belum dibuat”); } Else Printf(“pohon sudah ada”); }
6
Proses (Operasi) Pohon Biner
Insert sebuah simpul ke pohon yang sudah ada 1. Insert urut nomor simpul (insert level per level)
1. Sudah ada simpul akar
3. Setelah simpul baru diinsert pada pohon yang sudah ada
Root
Root
A
2. Sudah dibuat simpul baru yang akan diinsert
A Simpul baru, diinsert pada pohon di pointer LEFT simpul akar P
P
B
B
7
Proses (Operasi) Pohon Biner
Insert sebuah simpul ke pohon yang sudah ada 1. Insert urut nomor simpul (insert level per level) Root
Gambar disederhanakan : Root
P
P
A
Menginsert simpul B sebagai subordinat kiri simpul A, instruksinya : Root>Left = P;
A
B
B Root
Menginsert simpul B sebagai subordinat kanan simpul A, instruksinya : Root>Right = P;
A
P
B 8
Proses (Operasi) Pohon Biner
Insert sebuah simpul ke pohon yang sudah ada 2. Insert simpul pada nomor simpul tertentu
Root P
A K B
D
C
E H
F
G I 9
Proses (Operasi) Pohon Biner
Insert sebuah simpul ke pohon yang sudah ada 2. Insert simpul pada nomor simpul tertentu
Root
A B
D
C
E H
P
K
F
G I
Untuk menginsert simpul baru (K) menjadi subpohon kiri simpul F, dilakukan dengan instruksi :
Root>Right>Left>Left = P 10
Proses (Operasi) Pohon Biner
Insert sebuah simpul ke pohon yang sudah ada 2. Insert simpul pada nomor simpul tertentu Root
1
A
3
B
D H P
C 6
E I
Q
K S
G
F
V
12 L
W
P
X
M Y
N
O
Z
25
a
50
11
Proses (Operasi) Pohon Biner Penelusuran pohon biner
Penelusuran (tranverse atau tranversal) pohon biner, maksudnya membaca atau mengunjungi (visit) simpul-simpul pohon biner dengan urutan tertentu. Ada 3 penelusuran yang bila di tambah dengan kebalikannya menjdi 6 macam penelusuran : 1. Preorder (atau depthfirst order) 2. Inorder (atau symetric order) 3. Postorder
Bila ditelusuri secara Hasil penelusuran
+ A
4. Inverse Preorder 5. Inverse Inorder 6. Inverse Postorder
B
Preorder
+ A B (bentuk PREFIX)
Inorder
A + B (bentuk INFIX)
Postorder
A B + (bentuk POSTFIX)
12
Proses (Operasi) Pohon Biner Penelusuran pohon biner
Bila ditelusuri secara Hasil penelusuran
A B
C
Preorder
A B C
Inorder
B A C
Postorder
B C A
Karena bukan merupakan arithmetic statement, jadi tidak diistilahkan dengan bentuk INFIX,PREFIX dan POSTFIX.
Penelusuran Preorder: Ambil akar Telusuri secara preorder subpohon kiri Telusuri subpohon kanan
13
Proses (Operasi) Pohon Biner Penelusuran pohon biner
Preorder → AKAR, KIRI, KANAN Inorder → KIRI, AKAR, KANAN Postorder → KIRI, KANAN, AKAR A B
Pre : A B In : B A Post: B A 14
Proses (Operasi) Pohon Biner Penelusuran pohon biner A B
Pre : A B C In : B A C Post: B C A
C
A B
D
C
E
F
Pre : A B D E C F In : D B E A F C Post: D E B F C A 15
Proses (Operasi) Pohon Biner Penelusuran pohon biner A B
C
D H
E J
F K
G M
Pre : A B D H E J K C F M G In : H D B J E K A F M C G Post: H D J K E B M F G C A 16
