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