Membuat Binary Tree dengan Java - ARTANA

Membuat Binary Tree dengan Java

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarki antara elemen-elemen. Tree didefinisikan sebagai kumpulan simpul (node) dengan salah satu simpul yang dijadikan akar (root). Simpul lainnya terbagi menjadi himpunan yang saling tak berhubungan satu sama lain (subtree).

Beberapa istilah dalam tree :
Predecessor : Node yang berada di atas node tertentu
Successor : Node yang berada dibawah node tertentu
Ancestor : Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
Descendant : Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
Parent : Predecessor satu level di atas suatu node
Child : Successor satu level di bawah suatu node
Sibling : Node-node yang memiliki parent yang sama dengan suatu node
Subtree : Bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
Size : Banyaknya node dalam suatu tree Height : Banyaknya tingkatan / level dalam suatu tree
Root : Satu-satunya node khusus dalam tree yang tak punyakpredecessor
Leaf : Node-node dalam tree yang tak memiliki successor
Degree : Banyaknya child yang dimiliki suatu node

Pada postingan ini saya akan membahas salah satu bentuk tree yakni binary tree. Binary Tree adalah bentuk khusus dari tree dimana setiap node hanya dapat memiliki maksimum dua buah node child. 

Berikut gambaran dari binary tree:

  

Dalam binary tree dikenal dengan operasi traverse yaitu mengunjungi seluruh node-node pada tree masing-masing sekali. Hasilnya adalah urutan informasi secara linear yang tersimpan dalam tree. Ada tiga cara traverse yaitu PreOrder, InOrder dan PostOrder.

PreOrder : cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child
InOrder : kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right Child
PostOrder : kunjungi Left Child, kunjungi Right Child cetak isi node yang dikunjungi.

Cukup panjang penjelasannya. Nah, selanjutnya adalah membuat binary tree dalam bahasa java. Berikut saya bagikan source codenya. Saya sarankan mengetik ulang source code di bawah ini daripada mencopas, supaya agan lebih paham.

Pertama buat kelas dengan nama TreeNode
/**
*
* @author Wim Sonevel
*/
public class TreeNode {
int data;
TreeNode left;
TreeNode right;

public TreeNode(int data) {
this.data = data;
}
}


Selanjutnya buat kelas dengan nama BinaryTree. Kelas ini berisi method-method yang akan digunakan untuk mengoperasikan Binary Tree.
/**
*
* @author Wim Sonevel
*/
public class BinaryTree {
TreeNode root;

public boolean isEmpty(){
return (root==null);
}

//method insert data
public void insert(TreeNode input) {
if (isEmpty()) {
root = input;
} else {
// cari parent yg sesuai dan (kiri/kanan)
TreeNode current = root;
TreeNode parent = null;
boolean diKiri = true;
while (current != null) {
parent = current;
// kalau data yang akan diinputkan lebih besar,
// bergerak ke kanan
if (current.data < input.data) {
current = current.right;
diKiri = false;
// else gerak ke kiri
} else if(current.data > input.data){
current = current.left;
diKiri = true;
}else{
System.out.println("data "+input.data+" sudah ada");
break;
}
}
// hubungkan ke parent
if (diKiri) {
parent.left = input;
} else {
parent.right = input;
}
}
}
public void preOrder(){
preOrder(root);
}
public void inOrder(){
inOrder(root);
}
public void postOrder(){
postOrder(root);
}

public void preOrder(TreeNode akar){
if(akar != null){
System.out.print(akar.data+" ");
preOrder(akar.left);
preOrder(akar.right);
}
}
public void inOrder(TreeNode akar){
if(akar != null){
inOrder(akar.left);
System.out.print(akar.data+" ");
inOrder(akar.right);
}
}

public void postOrder(TreeNode akar){
if(akar != null){
postOrder(akar.left);
postOrder(akar.right);
System.out.print(akar.data+" ");
}
}

//method mencari data
public TreeNode search(int key) {
TreeNode node = null;
TreeNode current = root;
// lakukan pencarian selama current bukan null
while (current != null) {
if (current.data == key) {
return node;
} else {
if (current.data < key) {
current = current.right;
} else {
current = current.left;
}
}
}
return node;
}
}

Setelah itu buat kelas dengan nama BinaryTreeApp. Kelas ini berfungsi untuk memanggil objek kelas BinaryTree.
/**
*
* @author Wim Sonevel
*/
public class BinaryTreeApp {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();

TreeNode node;

node = new TreeNode(5);
tree.insert(node);

node = new TreeNode(3);
tree.insert(node);

node = new TreeNode(4);
tree.insert(node);

System.out.print("Traversal dengan preorder :");
tree.preOrder();
System.out.print("\nTraversal dengan inorder :");
tree.inOrder();
System.out.print("\nTraversal dengan postorder :");
tree.postOrder();
System.out.println();

}
}

Output :









Sekian dari saya, semoga bermanfaat.
Happy coding :)

Berlangganan update artikel terbaru via email:

close