Politeknik Elektronika Negeri Surabaya
PRAKTIKUM 25-26 BINARY TREEDAN TRAVERSAL BINARY TREE A. TUJUAN Mahasiswa diharapkan mampu : 1. Memahami konsep dari BinaryTree danTraversalBinary Tree 2. Memahami proses traversal pada Binary Tree 3. Memahami perbedaan setiap traversal dan implementasinya
B. DASAR TEORI Binary Tree adalah struktur data yang hampir mirip juga dengan Linked List untuk menyimpan koleksi dari data. Linked List dapat dianalogikan sebagai rantai linier sedangkan Binary Tree bisa digambarkan sebagai rantai tidaklinier. Binary Tree dikelompokkan menjadi unordered Binary Tree (tree yang tidak berurut) dan ordered Binary Tree (tree yang terurut). Binary Tree dapat digambarkan berdasarkan kondisinya, sebagai berikut
Binary Tree kosong Gambar 1. Binary Tree dalam kondisi kosong
Pointer ke akar (root) dari tree
Gambar 2. Binary Tree berisi satu node yaitu root Binary Tree sebagai root sekaligus sebagai daun (leaf)
190
Politeknik Elektronika Negeri Surabaya
Gambaran dari Binary Tree yang terdiri dari 3 (tiga) node:
Pointer ke root dari tree
Leaf dari tree
Gambar 3. Binary Tree Node pada binary tree Jumlah maksimum node pada setiap tingkat adalah 2n
Gambar 4. Jumlah Node di Binary Tree Node pada binary tree maksimum berjumlah 2n-1 Algoritma Binary Tree Traversal Tiga teknik rekursif untuk binary tree traversals ,yaitu: 1.
Mengunjungi simpul akar (root),
2.
Melakukan traversal subpohon kiri (left subtree), dan
3.
Melakukan traversal subpohon kanan (right subtree).
Yang membedakan antara teknik satu dengan yang lain adalah proses pengurutan tugas mereka.
Proses traversal adalah proses melakukan kunjungan pada setiap node pada suatu binary tree tepat satu kali. Dengan melakukan kunjungan secara lengkap, maka akan
191
Politeknik Elektronika Negeri Surabaya
didapatkan urutan informasi secara linier yang tersimpan dalam sebuah binary tree. Terdapat tiga cara untuk melakukan kunjungan itu, yaitu: 1. Traversal preorder (depth first order) Dilaksanakan dengan jalan mencetak isi node yang dikunjungi lalu melakukan kunjungan ke subtree kiri dan selanjutnya ke subtree kanan. Algoritma umum traversal preorder adalah sebagai berikut: Jika tree kosong, maka keluar Proses node root. Traverse subtree kiri secara preorder. Traverse subtree kanan secara preorder. 2. Traversal inorder (symmetric order) Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, mencetak isi node yang dikunjungi, lalu melakukan kunjungan ke subtree kanan. Algoritma umum traversal inorder adalah sebagai berikut: Jika tree kosong, maka keluar. Traverse subtree kiri secara inorder. Proses node root. Traverse subtree kanan secara inorder. 3. Traversal postorder Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, lalu ke subtree kanan, dan selanjutnya mencetak isi node yang dikunjungi. Algoritma umum traversal inorder adalah sebagai berikut: Jika tree kosong, maka keluar. Traverse subtree kiri secara postorder. Traverse subtree kanan secara postorder. Proses node root. Semua algoritma traversal (preorder, inorder, postorder) yang diberikan di atas berupa algoritma rekursif, dan sebenarnya dapat dikerjakan secara iteratif dengan bantuan stack. 192
Politeknik Elektronika Negeri Surabaya
Contoh: diberikan ekspresi matematika ((A * B) - (C ^ D)) + (E / F), apabila digambarkan dalam bentuk binary tree. Apabila binary tree di atas dikunjungi: •
secara preorder akan menghasilkan: + - * A B ^ C D / E F
•
secara inorder akan menghasilkan: A * C - C ^ D + E / F
•
secara postorder akan menghasilkan: A B + C D ^ - E F / +
C. TUGAS PENDAHULUAN Buatlah resume 1 halaman mengenai Binary Tree dan berikan penjelasannya.!
D. PERCOBAAN Node.java 1. 2. 3. 4. 5. 6.
class Node { int iData; // data yang digunakan sebagai nilai kunci. Node leftChild; // Simpul rujukan ke anak sebelah kiri. Node rightChild; // Simpul rujukan ke anak sebelah kanan. }
BinaryTree.java 1. class BinaryTree { 2. 3. private Node root; // Membentuk akar (root) BinaryTree 4. 5. public Object find(int key) { 6. Node current = root; // Mulai dari akar (root) 7. while (current.iData != key) // Selama tidak sesuai 8. { 9. if (key < current.iData) // Pergi ke cabang kiri? 10. { 11. current = current.leftChild; 12. } else { 13. current = current.rightChild; // Atau pergi ke cabang kanan. 14. } 15. if (current == null) // Jika tidak memiliki anak. 16. { 17. return null; 18. } 19. } 20. return current; // Data yang dicari ditemukan. 21. } 22. 23. public void insert(int id) { 24. {
193
Politeknik Elektronika Negeri Surabaya 25.
Node newNode = new Node(); // Membuat Node yang akan disisipkan.
26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48.
newNode.iData = id; // Menyisipkan data. if (root == null) // Jika tidak ada Node di akar (root). { root = newNode; } else { Node current = root; // Mulai dari akar (root). Node parent; while (true) // hadir secara internal. { parent = current; if (id < current.iData) // Pergi ke kiri. { current = current.leftChild; if (current == null) // Akhir cabang kiri. { // Sisipkan di kiri. parent.leftChild = newNode; return; } } // Akhir perjalanan ke kiri. else // Atau pergi ke kanan. { current = current.rightChild; if (current == null) // Akhir perjalanan cabang kanan. 49. { // Sisipkan di kanan. 50. parent.rightChild = newNode; 51. return; 52. } 53. } // Akhir perjalanan ke kanan. 54. } // Akhir while 55. } // Akhir bukan akar (root). 56. } // Akhir insert() 57. } 58. 59. public boolean delete(int id) { // (Asumsi pohon tidak kosong) 60. Node current = root; 61. Node parent = root; 62. boolean isLeftChild = true; 63. while (current.iData != id) // Mencari Node yang akan dihapus. 64. { 65. parent = current; 66. if (id < current.iData) // Pergi ke kiri? 67. { 68. isLeftChild = true; 69. current = current.leftChild; 70. } else // Atau pergi ke kanan? 71. { 72. isLeftChild = false; 73. current = current.rightChild; 74. } 75. if (current == null) // Akhir baris 76. { 77. return false; // Node yang dicari tidak ditemukan. 78. }
194
Politeknik Elektronika Negeri Surabaya 79. } // end while 80. // Node yang akan dihapus ditemukan. 81. // Jika Node tidak memiliki anak, hapus! 82. if (current.leftChild == null 83. && current.rightChild == null) { 84. if (current == root) // Jika Node yang dihapus merupakan akar (Node). 85. { 86. root = null; // Pohon biner menjadi kosong. 87. } else if (isLeftChild) // Jika Node yang dihapus adalah anak sebelah kiri. 88. { 89. parent.leftChild = null; // Pemutusan koneksi. 90. } else // Jika Node yang akan dihapus adalah anak sebelah kanan. 91. { 92. parent.rightChild = null; 93. } 94. } // Jika tidak ada anak kanan, ganti dengan subpohon kiri. 95. else if (current.rightChild == null) { 96. if (current == root) { 97. root = current.leftChild; 98. } else if (isLeftChild) // Anak sebelah kiri induk. 99. { 100. parent.leftChild = current.leftChild; 101. } else // Anak sebelah kanan induk. 102. { 103. parent.rightChild = current.leftChild; 104. } 105. } // Jika tak ada anak kiri, gantikan dengan subpohon sebelah kanan. 106. else if (current.leftChild == null) { 107. if (current == root) { 108. root = current.rightChild; 109. } else if (isLeftChild) // Anak sebelah kiri induk. 110. { 111. parent.leftChild = current.rightChild; 112. } else // Anak sebelah kanan induk. 113. { 114. parent.rightChild = current.rightChild; 115. } 116. } else // Dua anak, gantikan dengan successor inorder. 117. { 118. // Mendapatkan successor Node untuk dihapus (current) 119. Node successor = getSuccessor(current); 120. // Menghubungkan induk Node saat ini ke successor. 121. if (current == root) { 122. root = successor; 123. } else if (isLeftChild) { 124. parent.leftChild = successor; 125. } else { 126. parent.rightChild = successor; 127. } 128. // connect successor to current's left child 129. successor.leftChild = current.leftChild; 130. } // end else two children
195
Politeknik Elektronika Negeri Surabaya 131. // (successor tidak mempunyai anak sebwlah kiri) 132. return true; 133. } // end delete() 134. // Mengembalikan Node yang memiliki nilai terbesar berikuntnya setelah delNode, 135. // pergi ke anak kanan, kemudian turunan kiri anak sebalah kanan. 136. private Node getSuccessor(Node delNode) { 137. Node successorParent = delNode; 138. Node successor = delNode; 139. Node current = delNode.rightChild; // Pergi ke anak sebelah kanan. 140. while (current != null) // Hingga habis. 141. { // Anak kiri. 142. successorParent = successor; 143. successor = current; 144. current = current.leftChild; // Pergi ke anak sebelah kiri. 145. } 146. // Jika successor bukan anak seblah kanan. 147. if (successor != delNode.rightChild) { // Buat hubungan. 148. successorParent.leftChild = successor.rightChild; 149. successor.rightChild = delNode.rightChild; 150. } 151. return successor; 152. } 153. //Mencari simpul (Node) yang memiliki nilai terkecil. 154. public Node minimum() { 155. Node current, last = null; 156. // Mulai dari akar (root). 157. current = root; 158. // Hingga dasar pohon biner. 159. while (current != null) { 160. // Mencatat Node 161. last = current; 162. // Pergi ke anak kiri. 163. current = current.leftChild; 164. } 165. return last; 166. } 167. } // end class BinaryTree
E. LATIHAN Latihan 1 : Buat class BinaryNode.java untuk mendefinisikan data member dari class binary Tree node.
Latihan 2 : Buat class BinaryTree.java untuk mendefinisikan setiap method yang ada pada Binary Tree sesuai dengan berikut : public class BinaryTree
{ private BinaryNode root;//akar dari bst public BinaryTree() {...}//konstruktor
196
Politeknik Elektronika Negeri Surabaya public public public public public public public public
BinaryNode insert(T x, BinaryNode t) {...} BinaryNode remove(T x, BinaryNode t) {...} BinaryNode find(T x, BinaryNode t){...} BinaryNode findMin(BinaryNode t) {...} BinaryNode findMax(BinaryNode t) {...} void preOrder(...) {...} void inOrder(...) {...} void postOrder(...) {...}
}
Latihan 3 : buat class TestBinaryTree,java untuk melakukan testing dari setiap method yang dibuat pada latihan 2.
Latihan 4 : Modifikasi percobaan diatas dengan menambahkan operasi berikut: a. Menghitung jumlah/size node dalam tree. b. Menghitung height(kedalaman) tree. c. Mencari semua data pada node yang berposisi sebagai leaf(daun).
F. LAPORAN RESMI Kerjakan hasil percobaan(D) dan latihan(E) di atas dan tambahkan analisa.
197
