LAPORAN PRAKTIKUM RESMI

POHON BINER

Disusun oleh :

Unggul Budi Suryanto

201301011

Dosen pengampu :

Yosef Murya Kusuma Ardhana.S.T., M.Kom

JURUSAN SISTEM INFORMASI

SEKOLAH TINGGI ILMU KOMPUTER YOS SUDARSO

PURWOKERTO

2014

BAB I

TEORI DASAR

POHON BINER (BINARY TREE)

Pengantar

Pohon biner adalah sebuah tree yang pada masing-masing simpulnya hanya dapat memiliki

maksimum 2 (dua) simpul anak, tidak boleh lebih. Pada pohon biner, umumnya kedua node

anak (child) disebut dengan posisinya, yaitu subordinat kiri (left child) dan subordinat kanan

(right child).

Ada banyak cara dalam mengilustrasikan struktur sebuah node binary tree, namun yang

paling umum adalah ilustrasi seperti pada gambar diatas.

STRICLY BINARY TREE

.

Sebuah stricly binary tree bila mempunyai n leaf maka akan mempunyai 2n-1 buah node.

Perhatikan contoh gambar stricly binary tree diatas, maka dapat dihitung:

Jumlah leaf : 8

Jumlah node : 2*8-1 = 15

COMPLETELY BINARY TREE

Completely binary tree dengan depth = d adalah pohon biner stricly binary tree

dimana semua leaf hanya berada pada level d.

Maka pada completely binary tree berlaku:

Pada level k jumlah node ......: n = 2^k

Untuk tree dengan depth d, maka jumlah node .: n = 2^(d+1)-1

Untuk tree dengan depth d, maka jumlah node leaf ...: n = 2^d

Untuk tree dengan depth d, maka jumlah node bukan leaf..: n = (2^d)-1

Bila jumlah node seluruh node = n, maka depth tree adalah...: d = log2(n+1)-1

Complete binary tree dengan depth = d, memiliki ciri-ciri:

Setiap node yang berada dibawah d-1, memiliki dua subordinat.

Jika pada level d-1 subtree kanan ada node yang mempunyai subordinat, maka setiap

node pada level d-1 subtree kiri harus memiliki subordinat kiri dan kanan.

Balanced Binary Tree

(pohon biner seimbang) atau biasa disebut dengan pohon AVL adalah pohon biner yang

ketinggian sub-tree kiri dan sub-tree kanan untuk setiap node superordinat paling banyak

selisih 1.

Berikut ini adalah contoh Balance Binary Tree dan Unbalance Binary Tree :

PENOMORAN NODE POHON BINER

Untuk melakukan konversi telah disepakati cara penomoran setiap node dalam binary tree

sebagai berikut :

Jika sebuah node bernomor n, maka subordinat kiri bernomor 2n dan subordinat

kanan bernomor 2n+1.

Node root diberi nomor 1.

Dengan mengetahui dari nomor setiap node maka sebuah binary tree dapat direpresentasikan

kedalam sebuah array satu dimensi. Lihat contoh berikut ini ketika binary tree

direpresentasikan ke dalam array satu dimensi.

Untuk depth=d maka perlu dipersiapkan array satu dimensi minimal 2^(d+1).

Contoh untuk d=3 perlu dipersiapkan minimal 2^4=16 elemen.

Misal dengan :

int A[16];

BAB II

PENJELASAN PROGRAM

.

/* * pohon.cpp * * Created on: 17 Sep 2014 * Author: unggul budi suryanto */ #include #include #include #define Nil NULL using namespace std;

struct nod { struct nod *left; char data; struct nod *right; }; typedef struct nod NOD; typedef NOD POKOK; NOD *NodBaru(char item) { NOD *n; n=(NOD *)malloc (sizeof(NOD)); if (n != Nil) { n->data=item; n->left=Nil; n->right=Nil; } return n; } void binapokok (POKOK **T) { *T=Nil; } typedef enum {FALSE=0, TRUE=1 } BOOL; BOOL pokokKosong (POKOK *T) { return ((BOOL) (T==Nil)); } void tambahNod (NOD **p, char item) { NOD *n; n=NodBaru(item); *p=n; } void preorder(POKOK *T) { if(!pokokKosong(T)) { coutleft); cout

inorder(T->right); } } void postorder (POKOK *T) { if (!pokokKosong (T)) { postorder(T->left); postorder(T->right); coutright, buah='I'); tambahNod(&kelapa->left->right->right, buah='L'); tambahNod(&kelapa->right, buah='O'); tambahNod(&kelapa->right->left, buah='D'); cout

Berikut penjelasan dari Listing program_1.cpp :

1. Tanda yang diawali dengan */ dan diakhiri dengan /* adalah script yang digunakan untuk

membuat sebuah komentar pada pemrograman C++ dan tidak berpengaruh dengan program

yang akan dijalankan

2. #include atau disebut sebagai pengarah preprocessor #include berfungsi untuk menginstruksikan compiler untuk menyertakan berkas C++ sumber yang lain sebelum

kompilasi dimulai.

3. adalah sebuah library yang dibutuhkan untuk fungsi input seperti cin>>var dan output seperti coutleft->right, buah='I'); tambahNod(&kelapa->left->right->right, buah='L'); tambahNod(&kelapa->right, buah='O');

tambahNod(&kelapa->right->left, buah='D');

adalah suatu coding yang bertujuan untuk menentukan tempat dalam program agar

sesuai yang kita perlukan dalam membuat pohon biner.

14. cout

adalah pemanggilan fungsi menu preorder yang sudah ada didalam program menu dan ditampilkan dalam output programnya. cout

if (n != Nil) { n->data=item; n->left=Nil; n->right=Nil; } return n; } void binasilsilah (silsilah **T) { *T=Nil; } typedef enum {FALSE=0, TRUE=1 } BOOL; BOOL silsilahKosong (silsilah *T) { return ((BOOL) (T==Nil)); } void tambahNod (NOD **p, string item) { NOD *n; n=NodBaru(item); *p=n; } void preorder(silsilah *T) { if(!silsilahKosong(T)) { coutleft); coutright); cout

} int main() { silsilah *keluarga; string kakek; string ayah; string om; string saya; string adik; string saudara1; string saudara2; coutkakek; coutayah; coutom; coutsaya; coutadik; coutsaudara1; coutsaudara2; coutright, om); tambahNod(&keluarga->left->left, saya); tambahNod(&keluarga->left->right, adik); tambahNod(&keluarga->right->left, saudara1); tambahNod(&keluarga->right->right, saudara2); cout

inorder(keluarga); cout

8. void bina silsilah (silsilah **T) adalah pendeklarasian suatu menu yang akan dipanggil dalam program utama bernama binapokok.

9. void tambahNod (NOD **p, string item) adalah pendeklarasian suatu menu yang akan dipanggil dalam program utama bernama tambah nod.

10. void preorder(silsilah *T) adalah pendeklarasian suatu menu yang akan dipanggil dalam program utama bernama preorder.

11. Void inorder (silsilah *T) adalah pendeklarasian suatu menu yang akan dipanggil dalam program utama bernama inorder.

12. Void postorder (silsilah *T) adalah pendeklarasian suatu menu yang akan dipanggil dalam program utama bernama postorder.

13. coutkakek; coutayah; coutom; coutsaya; coutadik; coutsaudara1;

coutsaudara2; coutright, om); tambahNod(&keluarga->left->left, saya); tambahNod(&keluarga->left->right, adik); tambahNod(&keluarga->right->left, saudara1); tambahNod(&keluarga->right->right, saudara2);

15. adalah suatu coding yang bertujuan untuk menentukan tempat dalam program agar sesuai yang kita perlukan dalam membuat pohon biner.

16. cout

adalah pemanggilan fungsi menu postorder yang sudah ada didalam program menu dan ditampilkan dalam output programnya.

cout