Bab 13 tree tujuan
Download 200.11 Kb.
|
- Navigate this page:
- Pohon Biner Ek ui valent
- Pohon Biner Miring (Skewed Tree)
- Sifat Utama Pohon Berakar
- Aplikasi Pohon Biner
- Contoh P ro g
- Latihan DAFTAR PUSTAKA
Pohon Biner Similer Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda. 
Pohon Biner Ekuivalent Dua pohon yang memiliki struktur dan informasi yang sama. 
Pohon Biner Miring (Skewed Tree) Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun. 
Sifat Utama Pohon Berakar Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1). Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0. Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1. Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke - n pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling. Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi. Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon. Banyaknya Simpul Maksimum sampai Level N adalah :
Banyaknya Simpul untuk setiap Level I adalah :
Kunjungan pada Pohon Biner Kunjungan pohon biner terbagi menjadi 3 bentuk binary tree yaitu : Kunjungan secara preorder (Depth First Order), mempunyai urutan : Cetak isi simpul yang dikunjungi (simpul akar) Kunjungi cabang kiri Kunjungi cabang kanan 
Kunjungan secara inorder (symetric order), mempunyai urutan : Kunjungi cabang kiri Cetak isi simpul yang dikunjungi (simpul akar) Kunjungi cabang kanan 
Kunjungan secara postorder, mempunyai urutan : Kunjungi cabang kiri Kunjungi cabang kanan Cetak isi simpul yang dikunjungi (simpul akar) 
Aplikasi Pohon Biner Pada bagian ini akan dibahas tentang bagaimana menyusun sebuah Pohon Biner yang apabila dikunjungi secara PreOrder akan menghasilkan Notasi Prefix, kunjungan secara InOrder menghasilkan Notasi Infix, dan kunjungan PostOrder menghasilkan Notasi Postfix. Prefix Yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada didepan operand. Contoh : A + B * C (Infix) Maka notasi prefixnya adalah +A*BC Pemecahannya : A + B * C Diketahui ada 3 operand yaitu : A, B, C, dan 2 operator yaitu + dan *. Proses dimulai dengan melihat dari hirarkhi operator. Contoh di atas operator yang tertinggi adalah * kemudian +. Tanda * diapit oleh dua operand yaitu B dan C yaitu B * C, prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand, sehingga fungsi B * C, notasi prefixnya menjadi *BC. Sehingga hasil sementara dari notasi prefix adalah A + *BC
Selanjutnya mencari prefix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan *BC, gabungkan operand, sehingga menjadi A*BC, lalu pindahkan operator ke depan operand, sehingga hasil akhir menjadi + A * B C Contoh yang lain : 1. A + B – C * D 2 3 1 hirarkhi level A + B – *CD 1 + AB – *CD 2 – +AB *CD 3 2. A * B ^ C – D 2 1 3 hirarkhi A * ^BC – D 1 *A^BC – D 2 -*A^BCD 3 3. A + ( B – C ) * D 3 1 2 hirarkhi A + -BC * D 1 (karena diapit tanda paranthesis atau kurung buka/tutup, ( ) ) A + *-BCD 2 + A *-BCD 3 Infix Yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada diantara operand. Notasi ini hanya dikenal oleh manusia dan selalu digunakan dalam perhitungan aritmatika. Contoh : A + B * C ( A + B ) * C A – ( B + C ) * D ^ E Postfix Yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada dibelakang operand. Notasi ini hanya dikenal oleh processor dan dipahami dalam ALU. Contoh : A + B * C (Infix). Maka notasi postfixnya adalah ABC*+ Contoh Program Implementasi Tree // C program for different tree traversals #include #include and a pointer to right child */ struct node { int data; struct node* left; struct node* right; };
given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); }
"bottom-up" postorder traversal. */ void printPostorder(struct node* node) { if (node == NULL) return; // first recur on left subtree printPostorder(node->left); // then recur on right subtree printPostorder(node->right); // now deal with the node printf("%d ", node->data); }
void printInorder(struct node* node) { if (node == NULL) return; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ printf("%d ", node->data); /* now recur on right child */ printInorder(node->right); }
void printPreorder(struct node* node) { if (node == NULL) return; /* first print data of node */ printf("%d ", node->data); /* then recur on left sutree */ printPreorder(node->left); /* now recur on right subtree */ printPreorder(node->right); }
int main() { struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); printf("\nPreorder traversal of binary tree is \n"); printPreorder(root); printf("\nInorder traversal of binary tree is \n"); printInorder(root); printf("\nPostorder traversal of binary tree is \n"); printPostorder(root); getchar(); return 0; } Latihan ??????????????? DAFTAR PUSTAKA Algorithm Data Structures and Problem Solving with C++. 1997. Addison Wesley. Moh. Sjukani, Algoritma dan Struktur Data. Mitra Wacana Media Inggriani Liem, Diktat Catatan Singkat Bahasa C Agustus 2003. ITB Inggriani Liem, Diktat Kuliah Dasar Pemrograman April 2007. ITB Rinaldi Munir, Algoritma dan Pemrograman. Informatika Bandung Schaum, Programming with C++ 2nd. 2000. McGraw-Hill Schaum. Teach yourself C++ in 21 days. 2007. McGraw-Hill Download 200.11 Kb. Share with your friends:
|