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 :)

Membuat Double Linked List dengan Java

Pada postingan sebelumnya saya telah membahas bagaimana membuat single linked list dengan java. Nah, postingan kali ini saya akan membahas double linked list. Salah satu kelemahan dari single linked list adalah pointer hanya dapat bergerak satu arah saja, maju atau mundur, dan kiri atau kanan sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, kita dapat menggunakan metode double linked list. 

Pada double linked list menggunakan dua pointer. Dengan memiliki dua buah pointer, maka double linked list dapat diakses dengan dua arah, depan dan belakang. 

Berikut gambaran dari double linked list :

Nah, selanjutnya adalah membuat double linked list 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 Node

/**
 *
 * @author Wim Sonevel
 */
public class Node {
    int data;
    Node next;
    Node prev;

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

    public void tampil(){
        System.out.print("{"+data+"}");
    }
}

Selanjutnya buat kelas dengan nama DoubleLinkedList. Kelas ini berisi method-method yang akan digunakan untuk mengoperasikan Double Linked List.

/**
 *
 * @author Wim Sonevel
 */
public class DoubleLinkedList {
    Node first;
    Node last;

    //kontruktor
    //set nilai awal adalah null
    public DoubleLinkedList() {
        first = null;
        last = null;
    }

    //mengecek apakah linked list kosong atau tidak
    public boolean isEmpty(){
        return (first==null);
    }

    //method untuk menginsert data dari pertama
    public void insertFirst(int data){
        Node node = new Node(data);
        if(isEmpty()){
            last = node;
        }else{
            first.prev = node;
        }

        node.next = first;
        first = node;
    }

    //method untuk menginsert data dari terakhir
    public void insertLast(int data){
        Node node = new Node(data);
        if( isEmpty() )
            first = node;
        else{
            last.next = node;
            node.prev = last;
        }
        last = node;
    }

    //method untuk menginsert data pertama
    public Node deleteFirst(){
        Node temp = first;
        if(first.next == null)
            last = null;
        else
            first.next.prev = null;
        first = first.next;
        return temp;
    }

    //method untuk menghapus data terakhir
    public Node deleteLast(){
        Node temp = last;
        if(first.next == null)
            first = null;
        else
            last.prev.next = null;
        last = last.prev;
        return temp;
    }

    //method untuk menginsert data di tengah
    public boolean insertAfter(int key, int data){
        Node current = first;
        while(current.data != key){
            current = current.next;
            if(current == null)
            return false;
        }
        Node node = new Node(data);

        if(current==last){
            node.next = null;
            last = node;
        }else{
            node.next = current.next;
         
            current.next.prev = node;
        }
        node.prev = current;
        current.next = node;
        return true;
    }

    //method untuk menghapus data yang dipilih
    public Node deleteKey(int key){
        Node current = first;
        while(current.data != key){
            current = current.next;
        if(current == null)
            return null;
        }
        if(current==first)
            first = current.next;
        else
            current.prev.next = current.next;
        if(current==last)
            last = current.prev;
        else
            current.next.prev = current.prev;
            return current;
    }

    //menampilkan data dari pertama - terakhir
    public void displayForward(){
        System.out.print("List (first-->last): ");
        Node current = first;

        while(current != null){
            current.tampil();
            current = current.next;
        }
        System.out.println("");
    }

    //menampilkan data dari terakhir - pertama
    public void displayBackward(){
        System.out.print("List (last-->first): ");
        Node current = last;
        while(current != null){
            current.tampil();
            current = current.prev;
        }
        System.out.println("");
    }
}

Setelah itu buat kelas dengan nama DoubleLinkedListApp. Kelas ini berfungsi untuk memanggil objek kelas DoubleLinkedList.

/**
 *
 * @author Wim Sonevel
 */
public class DoubleLinkedListApp {
    public static void main(String[] args){
        DoubleLinkedList theList = new DoubleLinkedList();
        theList.insertFirst(22);
        theList.insertFirst(44);
        theList.insertFirst(66);
        theList.insertLast(11);
        theList.insertLast(33);
        theList.insertLast(55);
        theList.displayForward();
        theList.displayBackward();
        theList.deleteFirst();
        theList.deleteLast();
        theList.deleteKey(11);
        theList.displayForward();
        theList.insertAfter(22, 77);
        theList.insertAfter(33, 88);
        theList.displayForward();
    }
}

Output :

Sekian dari saya, semoga bermanfaat.
Happy coding :)

Membuat Single Linked List dengan Java

Di dalam struktur data ada istilah yang dikenal dengan Linked List. Linked list merupakan suatu kumpulan data yang tersusun secara sekuensial, saling tersambung dan dinamis. Suatu linked list berisi simpul (node) yang dikaitkan dengan simpul lainnya dalam urutan tertentu. 

Linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Ada beberapa bentuk dari linked list yaitu single linked list, double linked list dan circular linked list.

Pada postingan ini saya fokuskan untuk membahas single linked list. Single linked list merupakan bentuk dari linked list yang paling sederhana, dimana simpul-simpul terhubung oleh suatu pointer. Struktur ini dapat dilintasi dari simpul pertama sampai simpul terakhir. Simpul yang dibuat pertama akan menjadi head dan simpul-simpul yang dibuat setelahnya akan menjadi simpul-simpul pengikut. Berikut gambaran dari single linked list : 

Sudah paham kan? Nah, selanjutnya adalah membuat linked list 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 Node.

/**
 *
 * @author Wim Sonevel
 */
public class Node {
    
    int data;
    Node next;

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

    public void tampil(){
        System.out.print("{"+data+"}");
    }
}

Selanjutnya buat kelas dengan nama Linked List. Kelas ini berisi method-method yang akan digunakan untuk mengoperasikan Linked List.

/**
 *
 * @author Wim Sonevel
 */
public class LinkedList {

    Node first ;

    public LinkedList(){
        first = null;
    }

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

    public void addFirst(int data){
        Node node = new Node(data);
        node.next = first;
        first = node;
    }

    // Menambah data dari simpul terakhir
    public void addLast(int data){
        Node node, help;
        node = new Node(data);
        node.next = null;

        if(isEmpty()){
            first = node;
            first.next = null;
        }else{
            help = first;
            while(help.next!=null){
                help=help.next;
            }
            help.next=node;
        }
    }

    // menghapus data dari simpul pertama
    public Node deleteFirst(){
        if(!isEmpty()){
            Node temp = first;
            first = first.next;
            return temp;
        }else{
            return null;
        }
    }

    // menghapus data dari simpul terakhir
    public Node deleteLast(){
        if(!isEmpty()){
            Node temp, current;
            current=first;
            while(current.next.next != null){
                current=current.next;
            }
            temp=current.next;
            current.next=null;
            return temp;
        }else{
            Node temp = first;
            first = null;
            return temp;
        }
    }

    // menampilkan isi linked list
    public void tampilkan(){
        Node current = first;
        if(current == null){
            System.out.println("Kosong!");
        }else{
            while(current != null){
                current.tampil();
                current = current.next;
            }
            System.out.println();
        }
    }
}

Setelah itu buat kelas dengan nama LinkedListApp. Kelas ini berfungsi untuk memanggil objek kelas LinkedList.

/**
 *
 * @author Wim Sonevel
 */
public class LinkedListApp {
    public static void main(String[] args) {

        LinkedList link = new LinkedList();
        link.addFirst(1);
        link.addFirst(2);
        link.addLast(3);
        link.addLast(4);
        link.tampilkan();
        link.deleteLast();
        link.tampilkan();
       
    }
}

Output :

Sekian dari saya, semoga bermanfaat.
Happy coding :)

Membuat Queue(Antrian) dengan Java

Queue dapat diartikan sebagai antrian. Queue dalam struktur data merupakan suatu data yang tersusun dengan konsep antrian. Dalam suatu antrian, yang pertama datang itulah yang pertama dilayani. Konsep dari queue sendiri adalah FIFO (First In First Out), data yang pertama masuk akan keluar pertama kali.

Operasi – operasi dalam queue antara lain :

Enqueue : Memasukkan data ke dalam queue
Dequeue : Mengeluarkan data terdepan dari queue
Clear : Menghapus seluruh queue
IsEmpty : Memeriksa apakah queue kosong
IsFull : Memeriksa apakah queue penuh

Berikut ini adalah implementasi queue menggunakan bahasa pemrograman Java :
- Buat kelas dengan nama Queue

/**
 *
 * @author Wim Sonevel
 */
public class Queue {

    int data[];
    int head = 0;
    int tail = -1;

    public Queue(int size) {
        data = new int[size];
    }

    public boolean isEmpty(){
        if(tail==-1){
            return true;
        }else{
            return false;
        }
    }

    public boolean isFull(){
        if(tail==data.length-1){
            return true;
        }else{
            return false;
        }
    }

    public void Enqueue(int dataBaru){
        if(isEmpty()){
            tail = head;
            data[tail] = dataBaru;
        }else if(!isFull()){
            tail++;
            data[tail] = dataBaru;
        }else if(isFull()){
            System.out.println("antrian sudah penuh");
        }
    }

    public int Dequeue(){
        int temp = data[head];
        for(int i=head;i<=tail-1;i++){
            data[i] = data[i+1];
        }
        tail--;
        return temp;
    }
    
    public void tampilkan(){
        if(!isEmpty()){
            int index = head;
            while(index <= tail){
                System.out.print("|"+data[index]+"| ");
                index++;
            }
            System.out.println();
        }else{
            System.out.println("Kosong");
        }
    }

}

- Buat kelas dengan nama QueueApp, kemudian instance objek dari kelas Queue.

/**
 *
 * @author Wim Sonevel
 */
public class QueueApp {
    public static void main(String[] args) {
        Queue queue = new Queue(3);
        queue.Enqueue(1);
        queue.Enqueue(2);
        queue.Enqueue(3);
        queue.tampilkan();
        queue.Dequeue();
        queue.tampilkan();
        queue.Dequeue();
        queue.tampilkan();
        queue.Dequeue();
        queue.tampilkan();
    }
}

Output :
|1| |2| |3|
|2| |3|
|3|
Kosong

Membuat Stack(Tumpukan) dengan Java

Stack dalam struktur data merupakan suatu tumpukan dari sekumpulan data. Konsepnya adalah LIPO (Last In First Out), data yang pertama masuk akan keluar paling akhir.

Operasi - operasi dalam stack antara lain :
1. Push   : memasukkan data
2. Pop    : mengambil / mengeluarkan data
3. IsEmpty  : memeriksa apakah stack kosong
4. IsFull      : memeriksa apakah stack penuh
5. Clear      : mengosongkan stack

berikut adalah source code nya :

/**
 *
 * @author Wim Sonevel
 */
public class Stackx {
    int data[];
    int top=-1;

    Stackx(int kapasitasData){
        data=new int[kapasitasData];
    }
   
    public boolean isFull(){
        if(top==data.length-1){
            return true;
        }else{
            return false;
        }
    }

    public boolean isEmpty(){
        if(top==-1){
            return true;
        }else{
            return false;
        }
    }

    public void push(int dataBaru){
        if(!isFull()){
            top++;
            data[top]=dataBaru;
        }else{
            System.out.println("Data sudah penuh");
        }
    }

    public void pop(){
        if(!isEmpty()){
            top--;
            System.out.println("data dikeluarkan");
        }else{
            System.out.println("Stack kosong");
        }
    }

    public void tampilkan(){
         int pencacah=0;
         while(pencacah<=top){
            System.out.print("|"+data[pencacah]+"| ");
            pencacah++;
         }
         
         if(isEmpty()){
             System.out.print("Stack Kosong");
         }
         System.out.println();
    }
}


import java.io.*;
public class AplikasiStack {
    public static void main(String[]args){
        Stackx mystack=new Stackx(3);

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            System.out.println("1. Push");
            System.out.println("2. Pop");
            System.out.println("3. Tampilkan data");
            System.out.println("4. Exit");

            try{
                System.out.print("pilihan anda no :");
                int pilih = Integer.parseInt(br.readLine());

                if(pilih==1){
                    System.out.print("Masukkan data :");
                    int data = Integer.parseInt(br.readLine());
                    mystack.push(data);
                }else if(pilih==2){
                    mystack.pop();
                }else if(pilih==3){
                    mystack.tampilkan();
                }else{
                    System.exit(0);
                }
            }catch(Exception e){

            }
        }     
    }
}

output :


1. Push
2. Pop
3. Tampilkan data
4. Exit
pilihan anda no :1
Masukkan data :10
1. Push
2. Pop
3. Tampilkan data
4. Exit
pilihan anda no :1
Masukkan data :20
1. Push
2. Pop
3. Tampilkan data
4. Exit
pilihan anda no :3
|10| |20|
1. Push
2. Pop
3. Tampilkan data
4. Exit
pilihan anda no :2
data dikeluarkan
1. Push
2. Pop
3. Tampilkan data
4. Exit
pilihan anda no :3
|10|
1. Push
2. Pop
3. Tampilkan data
4. Exit
pilihan anda no :2
data dikeluarkan
1. Push
2. Pop
3. Tampilkan data
4. Exit
pilihan anda no :3
Stack Kosong
1. Push
2. Pop
3. Tampilkan data
4. Exit
pilihan anda no :4