Modul Java Binary Tree dan Binary Search Tree

Binary search tree(BST) merupakan sebuah pohon biner yang boleh kosong. Setiap node dari BST harus memiliki value. Value tersebut digunakan untuk menentukan posisi dari node tersebut. Semua node subpohon sebelah kiri memiliki value yang lebih kecil dari root, sedangkan value node subpohon sebelah kanan selalu lebih besar dari root.

Dalam BST terdapat tiga cara untuk menampilkan node-nodenya, yaitu preorder, inorder dan postorder. Preorder adalah mencetak isi node dari root, kemudian ke kiri, dan ke kanan(root, kiri, kanan). Inorder adalah mencetak isi node dari kiri, kemudian ke root, dan ke kanan(kiri, root, kanan). Postorder adalah mencetak isi node dari kiri, kemudian ke kanan, dank ke root(kiri, kanan, root).

CONTOH SOAL

Buatlah sebuah program Binary Search Tree dalam java dan view menggunakan preorder dengan menu :

• insert,
• View,
• Exit

ALGORITMA

Class node
Main program
1. Start
2. Deklarasi variable : left : sebagai node sebelah kiri dari tree,
    right : sebagai node sebelah kanan dari tree,
    value : sebagai isi dari node,
    menu : sebagai pilihan menu,
    root : sebagai root pada tree
3. Buat objek tr dari class tree
4. Buat objek root dari class node
5. Inisialisasi variable menu=1
6. Inisialisasi variable r=1
7. Jika menu!= 3 benar lanjut ke langkah 8, jika salah lanjut ke langkah 20
8. Masukkan nilai dengan variable menu
9. Jika menu==1 benar lanjut ke langkah 10, jika salah lanjut ke langkah 15
10. Masukkan nilai dengan variable a
11. Jika r==1 benar lanjut ke langkah 12, jika salah lanjut ke langkah 14
12. Panggil method input dari objek root dengan parameter a
13. Kurangi nilai variable r, r=r-1, kembali ke langkah 7
14. Panggil menu insert dari objek tr dengan index root dan a, kembali ke langkah 7
15. Jika menu==2 benar lanjut ke langkah 16, jika salah lanjut ke langkah 17
16. Panggil method view dari objek tr dengan parameter root, kembali ke langkah 7
17. Jika menu==3 benar lanjut ke langkah 18, jika salah lanjut ke langkah 19
18. Tampilkan keluar, kembali ke langkah 7
19. Tampilkan salah, kembali ke langkah 7
20. End

Method input
1. Start(int a)
2. Isi niali variable value, value=a
3. End

Class tree
Method insert
1. Start(node a, int b)
2. Jika b<a.value benar lanjut ke langkah 3, jika salah lanjut ke langkah 7
3. Jika a.left!=null benar lanjut ke langkah 4, jika salah lanjut ke langkah 5
4. Panggil method insert dengan parameter a.left dan b, lanjut ke langkah 12
5. Buat objek baru dari a.left dari class node
6. Panggil method input dari objek a.left
7. Jika b>a.value benar lanjut ke langkah 8, jika salah lanjut ke langkah 7
8. Jika a.right=null benar lanjut ke langkah 4, jika salah lanjut ke langkah 5
9. Panggil method insert dengan parameter a. right dan b, lanjut ke langkah 12
10. Buat objek baru dari a. right dari class node
11. Panggil method input dari objek a.right
12. End

Method view(node a)
1. Start
2. Panggil method preOrder dengan paramere a
3. End

Method preOrder
1. Start(node a)
2. Jika a!=null benar lanjut ke langkah 3, jika salah lanjut ke langkah 6
3. Tampilkan nilai variable value dari objek a
4. Panggil method inOrder dengan parameter a.left
5. Panggil method postOrder dengan parameter a.left
6. End