Membuat Binary Tree dengan Java

Friday, January 08, 2016
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 :)

Share this :

Previous
Next Post »
7 Komentar
avatar

terimakasih bro,ini sangat bermanfaat bagi saya yang sedang belajar programming, thanks bro :D

Balas
This comment has been removed by the author. - Hapus
avatar

trimakasih atas artikelnya, sangat bermanfaat

Balas
avatar

gan kalau mau menampilkan leaf sama route rootnya gmn ya gan?

Balas
avatar

Terimakasih mas, artikelnya sangat membantu....

bisa kita lanjut pembicaraan lewat email mas, ada yang ingin saya tanyakan seputar blogspot, jika berkenan bisa hubungi saya di fauzuliman9d@gmail.com, terimakasih atas perhatiannya, saya harap mas bisa menghubungi saya...

Balas

Penulisan markup di komentar
  • Silakan tinggalkan komentar sesuai topik. Komentar yang menyertakan link aktif, iklan, atau sejenisnya akan dihapus.
  • Untuk menyisipkan kode gunakan <i rel="code"> kode yang akan disisipkan </i>
  • Untuk menyisipkan kode panjang gunakan <i rel="pre"> kode yang akan disisipkan </i>
  • Untuk menyisipkan quote gunakan <i rel="quote"> catatan anda </i>
  • Untuk menyisipkan gambar gunakan <i rel="image"> URL gambar </i>
  • Untuk menyisipkan video gunakan [iframe] URL embed video [/iframe]
  • Kemudian parse kode tersebut pada kotak di bawah ini
  • © 2015 Simple SEO ✔