Skip to content
22 Maret 2009 / Jeffrey Hermanto Halimsetiawan

Struktur Data Tree/Pohon dalam Bahasa Java


Download PDF Version : Struktur Data Tree/Pohon dalam Bahasa Java

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.

Ilustrasi struktur data tree:

Ilustrasi Tree

Ilustrasi Tree

Degree (derajat) adalah jumlah edge yang keluar dan masuk dari sebuah node.
Contoh : node E memiliki in degree 1 dan out degree 2
Root (akar) adalah node yang memiliki derajat keluar >=0 dan derajat masuk = 0.
Contoh : node A adalah root
Subtree / child adalah bagian salah satu node dibawah root sampai ke bawah.
Contoh : tree C adalah right subtree dari A dan tree B merupakan left subtree dari A
node G dan F merupakan child dari node C
node F merupakan parent dari node J dan K
Ancestor adalah Node yang berada di atas node lain.
Contoh : node B adalah ancestor dari node E
Descendant adalah node yang berada di bawah node lain.
Contoh : node E adalah descendant dari node A.
Leaf (daun) adalah semua node yang derajat masuknya 1 dan derajat keluarnya 0.
Contoh : node D, H, I, J, K, dan G adalah leaf
Sibling adalah node yang mempunyai level yang sama dan parent yang sama.
Contoh : node D adalah sibling dari node A
Height (ketinggian) adalah level tertinggi dari tree ditambah 1.
Contoh : height dari tree A adalah 3 + 1 = 4
Weight (bobot) adalah jumlah leaf(daun) pada tree.
Contoh : weight dari tree A adalah 6

BINARY TREE
Sebuah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai subpohon kiri(left subtree) dan subpohon kanan (right subtree) dan kedua subtree tersebut harus terpisah, atau dengan kata lain tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.

Binary tree terdiri dari :

  1. Full Binary Tree : semua node (kecuali leaf pasti memiliki 2 anak dan tiap subtree memiliki panjang path yang sama)

    Full Binary Tree

    Full Binary Tree

  2. Complete Binary Tree : mirip dengan full binary tree, tetapi tiap subtree boleh memiliki panjang path yang berbeda dan tiap node (kecuali leaf memiliki 2 anak)

    Complete Binary Tree

    Complete Binary Tree

  3. Skewed Binary Tree : binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak

    Skewed Binary Tree

    Skewed Binary Tree

BINARY SEARCH TREE
Binary tree dengan sifat bahwa nilai dari semua left child harus lebih kecil daripada nilai dari right child dan parentnya.
Contoh :

Binary Search Tree

Binary Search Tree

Contoh Implementasi Binary Search Tree :

/**
 * 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;
	}
	/**
	 * Mencari nilai terbesar yang mendekati nilai yang disimpan Node
	 * yang dihapus, Ilustrasi :
	 *
	 *					65
	 *			59				72
	 *		32		64
	 *			 62
	 * misal : nilai yang dihapus 65, maka nilai terbesar yang mendekati adalah 64.
	 * maka ambil 64 sebagai successor, kemudian gabungkan
	 *				59
	 *			32		63
	 * Kemudian satukan keduanya :
	 *						64
	 *				59
	 *			32		63
	 * Jadilah urutan tree yang masih memenuhi syarat Binary Search Tree
	 **/
	private Node getSuccessor(Node localNode){
		Node parent = null,
		 	 successor = localNode,
		 	 cursor = localNode.left;
		while (cursor != null){
			parent = successor;
			successor = cursor;
			cursor = cursor.right;
		}
		if (successor != localNode.left){
			parent.right = successor.left;
			successor.left = localNode.left;
		}
		return successor;
	}
	/**
	 * Method traverse untuk mengelilingi Node-Node dalam tree
	 **/
	public void traverse(int tipe){
		switch (tipe){
			case 1:
				System.out.print("\nPreorder traversal:\n");
                preOrder(root);
                break;
         	case 2:
         		System.out.print("\nInorder traversal:\n");
                inOrder(root);
                break;
         	case 3:
         		System.out.print("\nPostorder traversal:\n");
                postOrder(root);
                break;
		}
		System.out.println('\n');
	}
	private void preOrder(Node localRoot){
		if (localRoot == null) return;
		System.out.print(localRoot.data+" ");
		preOrder(localRoot.left);
		preOrder(localRoot.right);
	}
	private void inOrder(Node localRoot){
		if (localRoot == null) return;
		inOrder(localRoot.left);
		System.out.print(localRoot.data+" ");
		inOrder(localRoot.right);
	}
	private void postOrder(Node localRoot){
		if (localRoot == null) return;
		postOrder(localRoot.left);
		postOrder(localRoot.right);
		System.out.print(localRoot.data+" ");
	}

}
  1. inno / Mar 24 2009 15:01

    Eh, tny dunk. Gmn cara bikin method isSkewTree() boolean? Jadi tu method buat mengetahui apakah pohon biner berupa skewed ato kaga? Bales cepetan ya….

  2. Adrian / Apr 16 2009 12:30

    permisi…thx buat tutorialnya ya….aku mo tanya dunk…
    1. itu kalo misal mo buat tree dengan 4 child, gimana caranya yah…
    2. cara inserting datanya gmn ya, dengan catatan tidak ada besar/kecil data…dgn kata lain asal masi kosong bisa ditempati…

    tolong diberi penjelasan ya…penting banged si >.< thx yah ^^

    • Jeffrey Hermanto / Apr 22 2009 19:50

      y tinggal bikin nodenya aja
      public class Node{
      int data;
      Node child1;
      Node child2;
      Node child3;
      Node child4;
      }

      trus kalo caranya inserting data ky gt tinggal manfaatin queue aja, jadi sistemnya pake level order..
      1
      2 3 4

      1 dimasukkan k queue

      while (!queue.isEmpty()){
      if (child1 == null) addNodeBaru ke child1; return;
      else queue.enqueue(child1)
      if (child2== null) addNodeBaru ke child2; return;
      else queue.enqueue(child2)
      if (child3 == null) addNodeBaru ke child3; return;
      else queue.enqueue(child3)
      if (child4 == null) addNodeBaru ke child4; return;
      else queue.enqueue(child4)
      }

      kira2 seperti itu.. semoga bermanfaat..

  3. Evi / Jun 1 2009 14:30

    mau tanya donk..
    kalo bikin tree yg datanya dari database gimana caranya..
    misal tabel a
    TID Item
    1 A
    1 D
    1 C
    2 A
    2 C
    2 E

    dibuat tree dan hasilnya disimpan di tabel b
    Item Path Cout
    A root 2
    D root:A 1
    C root:A:D 1
    C root A 1
    E root:A:C 1

    minta penjelasannya dunks..makasih
    moga ilmu yg di share bisa bermanfaat dan di ganti ilmu-ilmu lain..amin

    • Jeffrey Hermanto / Jun 3 2009 13:44

      mksdnya gimana itu tabelnya??
      aq krg paham sama isinya..
      tlg djelasin lg..

      • Evi / Jun 11 2009 15:49

        misal tabel a
        TID | Item
        1 | A
        1 | D
        1 | C
        2 | A
        2 | C
        2 | E

        dibuat tree dan hasilnya disimpan di tabel b
        Item | Path | count
        A | root | 2
        D | root:A | 1
        C | root:A:D | 1
        C | root A | 1
        E | root:A:C | 1

        periksa tid 1, item paling pertama disimpan sebagai root dan countnya 1, item selanjutnya sebagai anak dari A jd root:A dan countnya 1, item selanjutnya sebagai anak dr A dan D jd root:A:D dan countnya 1…setelah selesai, baca transaksi selanjutnya.jika ada ada item pertama di transaksi berikutnya sama dengan root yg di TID 1 (A), count nya ditambah 1. jika item selanjutnya tidak ada yang sama maka item itu jd anak nya. ngerti gak, pak? saia butuh pencerahan bgt. tolong yah pak..

      • Jeffrey Hermanto / Jun 16 2009 11:08

        TID itu sbnrnya apa?
        TID 1 itu artinya Tree yang pertama gt & TID 2 brarti tree yang kedua gt?

        trus count itu mksdnya apa?
        jika ada ada item pertama di transaksi berikutnya sama dengan root yg di TID 1 (A), count nya ditambah 1.
        brarti cman dicek ke root tree2 sblmnya??

  4. Evi / Jun 1 2009 17:15

    setelah di compile dan dijalan kan dengan perintah java BinTree, keluar eror “Exception in thread “main” java.lang.NoSuchMethodError: main” apa ada yg salah? terimakasih..

    • Jeffrey Hermanto / Jun 3 2009 13:42

      y pasti error..
      soalnya d public class BinTree blum ada :
      public static void main(String[] args)

      jadi tambahin aja di dalemnya
      public class BinTree {
      //misalnya ky gini
      public static void main(String[] args){
      BinTree tree = new BinTree();
      tree.insert(5);
      tree.preorder(tree.root);
      }
      }

      • Hadiana / Mar 4 2010 11:10

        tolong minta kelas utamanya yng lengkap donk biar bisa d runing .
        sya mau liat hasil out-putnya.
        di tunggu ya!
        klo bisa bales lewat e-mail saya
        makasih…

      • Jeffrey Hermanto / Mar 7 2010 18:45

        Kelas Node dan BinTree yang diposting merupakan kelas yang sudah lengkap dan hanya perlu dicopy ke dalam file BinTree.java..
        Kemudian tinggal buat public static void main(String[] args) dan buat instance dari kelas BinTree tersebut..

        – practice makes perfect –

  5. nvi / Des 11 2009 09:31

    1. gimana cara buat fungsi untuk menghapus suatu node pada tree

    2. gimana cara buat program lengkap untuk memanipulasi dan mensimulasikan tree dengan berbasis menu?

    suma pertanyaan tlg d jawab dalam bahasa c ya.. mkasih.

    • Jeffrey Hermanto / Des 12 2009 13:54

      Untuk menghapus sebuah node pada tree telah dbahas pada method public boolean delete(int key){} di postingan tersebut.

      Untuk memanipulasi dan mensimulasikan memakan waktu yg cukup lama dan blom tentu anda dapat memahami apa yg saya buat. Jadi silahkan anda ubah class Tree yang telah saya sediakan dan dibuat animasinya..

  6. Hendarta / Mar 14 2010 15:08

    Mengenai tree…
    Yang bercabang tidak hanya 2, kira2 parameter yang digunakan untuk mengakses nodenya gimana???

    Juga mengenai pemakaian tree pada genetik programming, kira2 tau penggunaannya tidak??

    Trima Kasih sebelumnya…
    (Kalau bisa kirim lewat email y, terima kasih sekali lagi untuk itu…)

    • Jeffrey Hermanto / Mar 21 2010 18:51

      Jika untuk tiap treenyaa cabangnya tidak ada batas maksimal nya lbih baik dubah dalam bentuk graph dimana
      leftChild dan rightChild nya dubah menjadi LinkedList children..
      seperti itu..

      sedangkan untuk genetik programming saya belum pernah mendalaminya😀

      semoga bermanfaat

  7. Eka Yani / Mar 19 2010 14:26

    tolong minta kelas TestBinTree dong
    soalnya yang di atas g bisa di runing ?

    • Jeffrey Hermanto / Mar 21 2010 18:49

      Class itu bisa di running kq, tinggal bikin

      public static void main(String[] args) nya😀

  8. sisil / Apr 29 2010 07:46

    tanya donk????????
    1.dalam tree bagaimana cara implementasi programnya?
    2.kunjungan dalam tree kan ada tiga yaitu
    print orde,in orde,push orde
    bisa minta tolong penjelesannya gak dan implementasi programnya?

  9. sisil / Apr 29 2010 08:01

    tanya donk????????
    1.dalam tree bagaimana cara implementasi programnya?
    2.kunjungan dalam tree kan ada tiga yaitu
    print orde,in orde,push orde
    bisa minta tolong penjelesannya gak dan implementasi programnya?

    • Jeffrey Hermanto / Mei 9 2010 18:27

      implementasinya kan sudah saya bahas dalam postingan di atas.. Silahkan dibaca di sana😀

      – practice makes perfect –

  10. snow / Jul 18 2010 13:16

    tolong minta program lengkap public static void main(String []args) dari program diatas dong mas tolong kirim ke email saya.terima kasih

    • Jeffrey Hermanto / Sep 9 2010 18:46

      silahkan dicoba sendiri, untuk menambah pengalaman dalam membuat struktur data tree😀

  11. Hyuga Iming / Nov 26 2010 13:32

    import java.util.*;
    class Node{
    int data;
    Node left;
    Node right;
    Node(int x){
    this.data = x;
    }
    }
    public class BinarySearchTree {
    private Node root;
    private boolean isEmpty() {
    return (root == null);
    }

    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;
    }

    if (input < parent.data) {
    parent.left = temp;
    return;
    }
    else {
    parent.right = temp;
    return;
    }
    }
    }

    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 {
    if (cursor.left == null && cursor.right == null){
    if (cursor == root)
    root = null;
    else if (isLeftChild)
    parent.left = null;
    else
    parent.right = null;
    }
    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;
    }
    else {
    Node successor = getSuccessor(cursor);
    if (cursor == root)
    root = successor;
    else if (isLeftChild)
    parent.left = successor;
    else
    parent.right = successor;
    successor.right = cursor.right;
    }
    }
    }
    return true;
    }

    private Node getSuccessor(Node localNode){
    Node parent = null,
    successor = localNode,
    cursor = localNode.left;
    while (cursor != null){
    parent = successor;
    successor = cursor;
    cursor = cursor.right;
    }
    if (successor != localNode.left){
    parent.right = successor.left;
    successor.left = localNode.left;
    }
    return successor;
    }
    public void traverse(int tipe){
    switch (tipe){
    case 1:
    System.out.print("\nPreorder traversal:\n");
    preOrder(root);
    break;
    case 2:
    System.out.print("\nInorder traversal:\n");
    inOrder(root);
    break;
    case 3:
    System.out.print("\nPostorder traversal:\n");
    postOrder(root);
    break;
    }
    System.out.println('\n');
    }
    private void preOrder(Node localRoot){
    if (localRoot == null) return;
    System.out.print(localRoot.data+" ");
    preOrder(localRoot.left);
    preOrder(localRoot.right);
    }
    private void inOrder(Node localRoot){
    if (localRoot == null) return;
    inOrder(localRoot.left);
    System.out.print(localRoot.data+" ");
    inOrder(localRoot.right);
    }
    private void postOrder(Node localRoot){
    if (localRoot == null) return;
    postOrder(localRoot.left);
    postOrder(localRoot.right);
    System.out.print(localRoot.data+" ");
    }

    public static void main(String[] args) {
    BinarySearchTree a = new BinarySearchTree();
    a.insert(5);
    a.insert(4);
    a.insert(6);
    a.insert(1);
    a.insert(4);
    a.insert(9);
    a.traverse(1); //pre-order
    a.traverse(2); //in-order
    a.traverse(3); //post-order
    }
    }
    ==========================
    dari coding d atas misalkan kita mau mencari level & height..?
    tolong d lengkapi dong codingnya..!!
    thanks before…^_^

    • Jeffrey Hermanto / Nov 27 2010 14:05

      Kalau mau cari level sama heightnya, pakai BFS aja tinggal manfaatin queue..

      semoga bermanfaat😀

      • Hyuga Iming / Nov 27 2010 18:29

        ada contoh condingnya gak????

      • Jeffrey Hermanto / Nov 28 2010 13:32

        ada tp silahkan dicoba sendiri aja,
        kalau anda tinggal copy2 codingannya, kapan belajarnya?
        paling tidak dr klue td itu anda bisa kembangkan sendiri..
        practice makes perfect

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: