BINERY TREE

        Tree merupakan salah satu bentuk struktur data bukan linier yang menggambarkan bentuk hierarki antara elemen-elemen. Tree biasanya terdiri dari root (akar) dan node-node (simpul-simpul) yang berada di bawah root. Struktur seperti tree sangat banyak sekali dgunakan dalam dunia nyata, misalnya: struktur organisasi suatu perusahaan, pengaturan filesystem, daftar isi sebuah buku, dan masih banyak lagi.

http://tutorialpemrograman.files.wordpress.com/2009/03/fullbinarytree.jpg


* Program membuat binary tree yang memiliki 2 anak dimana insertion
 * dilakukan secara terurut, dimana data yang lebih kecil diletakkan di kiri
 * dan yang lebih besar diletakkan di kanan.
 * @author : Jeffrey Hermanto Halimsetiawan
 * Selasa, 1 April 2008
 **/

import java.util.*;

class Node{
 int data;
 Node left;
 Node right;
 Node(int x){
  this.data = x;
 }
}

public class BinTree{
 private Node root;

 /**
  * Mengecek apakah tree masih kosong
  **/
 private boolean isEmpty(){
  return (root == null);
 }
 /**
  * Memasukkan suatu nilai ke dalam tree.
  * Jika nilai tersebut lebih kecil dari nilai node, maka bergerak ke kiri terus
  * hingga menjadi child, begitu juga sebaliknya.
  **/
 public void insert(int input){
  Node temp = new Node(input);
  if (isEmpty())
   root = temp;
  else {
   Node cursor = root,
     parent = null;
   while (cursor != null){
    parent = cursor;
    if (input < cursor.data)
     cursor = cursor.left;
    else
     cursor = cursor.right;
   }
   /**
    * Menambahkan Node baru pada kiri/kanan Node parent bergantung
    * pada nilai input dan nilai yang disimpan Node parent
    **/
   if (input < parent.data){
    parent.left = temp;
    return;
   }
   else {
    parent.right = temp;
    return;
   }
  }
 }
 /**
  * Mencari suatu nilai dalam tree berdasarkan prinsip :
  * Selama belum menemukan nilai yang sama,
  * Jika nilai yang dicari lebih kecil dari nilai yang disimpan dalam Node
  * maka bergerak ke left Child begitu juga sebaliknya.
  **/
 public Node find(int key){
  Node cursor = root;
  while (cursor != null){
   if (cursor.data == key)
    return cursor;
   else if (key < cursor.data)
    cursor = cursor.left;
   else
    cursor = cursor.right;
  }
  return null;
 }
 public boolean delete(int key){
  Node cursor = root,
    parent = null;
  boolean found = false,
       isLeftChild = true; //menandai apakah Node yang dihapus merupakan left child
  if (!isEmpty()){
   while (cursor != null){
    parent = cursor;
    if (key == cursor.data){
     found = true;
     break;
    }
    else if (key < cursor.data){
     isLeftChild = true;
     cursor = cursor.left;
    }
    else {
     isLeftChild = false;
     cursor = cursor.right;
    }
   }
   if (!found)
    return false;
   else {

    /**
     * Untuk menghapus leaf (tidak punya child)
     **/
    if (cursor.left == null && cursor.right == null){
     if (cursor == root)
      root = null;
     else if (isLeftChild)
      parent.left = null;
     else
      parent.right = null;
    }
    /**
     * Jika node yang akan dihapus hanya memiliki salah satu subtree
     * maka tinggal memindahkan subtree menggantikan node yang dihapus
     **/
    else if (cursor.left == null){
     if (cursor == root)
      root = cursor.right;
     else if (isLeftChild)
      parent.left = cursor.right;
     else
      parent.right = cursor.right;
    }
    else if (cursor.right == null){
     if (cursor == root)
      root = cursor.left;
     else if (isLeftChild)
      parent.left = cursor.left;
     else
      parent.right = cursor.left;
    }

    /**
     * Jika node yang akan dihapus memiliki 2 child, maka cari successornya
     * dengan fungsi getSuccessor kemudian hubungkan subtree bagian kanan
     * dari node yang dihapus dengan successor
     **/
    else {
     Node successor = getSuccessor(cursor);
     if (cursor == root)
      root = successor;
     else if (isLeftChild)
      parent.left = successor;
     else
      parent.right = successor;
     //menyambung successor dengan cursor.right
     successor.right = cursor.right;
    }
   }
  }
  return true;
 }

No comments:

Post a Comment

indra