Langsung ke konten utama

Pengertian dan Contoh Program Tentang Struktur Data Tree


Pengertian Struktur Data Tree
Tree atau pohon merupakan struktur data yang tidak linear yang digunakan untuk mempresentasikan data yang bersifat hirarki antara elemen-elemennya. Definisi tree yaitu kumpulan elemen yang salah satu elemennya disebut root (akar) dan elemen yang lain disebut simpul ( node) yang terpecah menjadi sejumlah kumpulan yang tidak saling berhubungan satu sama lain yang disebut sub-tree atau cabang.[1]
Gambar 4.1 Ilustrasi tree
Tabel berikut menjelaskan beberapa istilah yang terdapat pada tree [7]:
 

Tabel 4 .1 Istilah-istilah pada treea. Jenis-jenis Tree

Jenis - Jenis Tree
1) Binary Tree
pengertian binary tree dalam struktur data
Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child. contoh implementasi binary tree.[10]
Gambar 4.2 Ilustrasi binary tree
Jenis-jenis binary tree :
  • Full Binary Tree
Full binary tree adalah binary tree yang tiap node-nya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.[7]
Gambar 4.3 Ilustrasi full binary tree
  • Complete Binary Tree
Complete binary t ree adalah binary tree yang mirip dengan full binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.[7]
Gambar 4.4 Ilustrasi complete binary tree
  • Skewed Binary Tree
Skewed binary t ree adalah binary tree yang semua node nya (kecuali leaf) hanya memiliki satu child.[7]


Gambar 4.5 Ilustrasi skewed binary tree
  • Binary search tree (BST)
Binary search t ree (BST) adalah jenis pohon terurut yang digunakan untuk menyimpan data sehingga memudahkan pencarian kembali data tersebut.[10]
Gambar 4.6 Ilustrasi binary search tree

b. Operasi pada Tree[1]
  • Create
Create digunakan untuk membentuk binary tree baru yang masih kosong.
  • Clear
Clear digunakan untuk mengosongkan binary tree yang sudah ada.
  • Empty
Empty digunakan untuk memeriksa apakah binary tree masih kosong.
  • Insert
Insert digunakan untuk memasukkan sebuah node ke dalam tree.
  • Find
Find digunakan untuk mencari root, parent, left child , atau right child dari suatu node dengan syarat tree tidak boleh kosong.
  •  Update
Update digunakan untuk mengubah isi dari node yang ditunjuk oleh pointer current dengan syarat tree tidak boleh kosong.
  • Retrieve
Retrieve digunakan untuk mengetahui isi dari node yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.
  • Delete Sub
DeleteSub digunakan untuk menghapus sebuah sub-tree (node beserta seluruh descendant-nya) yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.
  • Characteristic
Characteristic digunakan untuk mengetahui karakteristik dari suatu tree, yakni size, height, serta average length-nya.
  • Traverse
Traverse digunakan untuk mengunjungi seluruh node-node pada tree, masing-masing sekali.


Tree Traversal
Tree traversal merupakan sebuah kunjungan yang berawal dari root, mengunjungi setiap node dalam tree masing-masing sekali. Kunjungan atau traversing dapat dilakukan dengan 3 cara yaitupre order, in order dan post order. [10]
a. Preorder
Algoritma preorder :
  1. Mencetak info pada node yang dikunjungi.
  2. Mengunjungi cabang kiri.
  3. Mengunjungi cabang kanan.

b. Inorder
Algoritma inorder :
  1. Mengunjungi cabang kiri.
  2. Mencetak info pada node yang dikunjungi.
  3. Mengunjungi cabang kanan.

c. Postorder
Algoritma postorder :
  1.  Mengunjungi cabang kiri.
  2. Mengunjungi cabang kanan.
  3. Mencetak info pada node yang dikunjungi.
  4. Breadth-first search (BFS) dan Depth-First-Search (DFS)
  • Breadth-first search (BFS)
Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hierarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya.[1]
Gambar 4.7 Ilustrasi breadth-first search
  • Depth-First-Search (DFS)
Depth-First-Search (DFS) adalah salah satu algoritma penelusuran struktur tree berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya (misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri]), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam. Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya. [1]

                                                  
Gambar 4.7 Ilustrasi deapth-first search (DFS)



Berikut adalah coding dari program binary tree :

package binary_tree;
class Node{
    Node left, right, parent;
    int data;
}
public class Binary_Tree {
// FUNCTIONS & GLOBAL VARIABLES
    static Node root;

    static void insert(int data){
        // buat node baru
        Node new_node = new Node();
        new_node.data = data;
        if(root == null){ // tree kosong
            root = new_node;
        }else{
            Node position = root;
            boolean found = false;
            while(!found){
                if(new_node.data < position.data){
                    if(position.left == null){
                        found = true;
                        new_node.parent = position;
                        position.left = new_node;
                    }else{
                        position = position.left;
                    }
                }else{
                    if(position.right == null){
                        found = true;
                        new_node.parent = position;
                        position.right = new_node;
                    }else{
                        position = position.right;
                    }
                }
            }
        }
    }

    static void view(){
        node_view(root, "");
    }
    static void node_view(Node node, String spaces){
        if(node == null){
            System.out.println(spaces + "EMPTY");
        }else{
            System.out.println(spaces + node.data);
            node_view(node.left, spaces+"    ");
            node_view(node.right, spaces + "    ");
        }
    }

    static void postfix (Node localroot){
        if(localroot != null){
            System.out.print("(");
            postfix(localroot.left);
            postfix(localroot.right);
            System.out.print(" "+localroot.data+" ");
            System.out.print(")");
        }
    }

    static void delete(int deleted){
        boolean found = false;
        Node x = root;
        while(x != null){
            if(x.data == deleted){
                found = true;
                break;
            }else if(x.left != null  && deleted < x.data){
                x = x.left;
            }else if(x.right != null && deleted > x.data){
                x = x.right;
            }else{
                found = false;
                break;
            }
        }
        if(!found){
            // do nothing, node not found
        }else{
            boolean is_root = x.parent == null;
            boolean is_right = !is_root && x == x.parent.right;
            boolean is_left = !is_root && x == x.parent.left;
            // jika tidak punya anak
            if(x.left == null && x.right == null){
                if(is_root){ //  tdk punya anak & adalah root
                    root = null;
                }else{ // tdk punya anak & bukan root
                    if(is_left){ // tdk punya anak & adalah anak kiri
                        x.parent.left = null;
                    }else if(is_right){ // tdk punya anak & adalah anak kanan
                        x.parent.right = null;
                    }
                    x.parent = null; // putuskan hubungan dengan parent
                }
            }else if(x.left != null && x.right == null){ // hanya punya anak kiri
                if(is_root){
                    root = x.left;
                    root.parent.left = null;
                    root.parent = null;
                }else{
                    if(is_left){
                        x.parent.left = x.left;
                    }else if(is_right){
                        x.parent.right = x.left;
                    }
                    x.left.parent = x.parent;
                    x.parent = null;
                    x.left = null;
                }
            }else if(x.left == null && x.right != null){ // hanya punya anak kanan
                if(is_root){ // root
                    root = x.right;
                    root.parent.right = null;
                    root.parent = null;
                }else{ // bukan root
                    if(is_left){
                        x.parent.left = x.right;
                    }else if(is_right){
                        x.parent.right = x.right;
                    }
                    x.right.parent = x.parent;
                    x.parent = null;
                    x.right = null;
                }
            }else{ // punya 2 anak
                Node replacement = x.right; // kanan sekali
                while(replacement.left != null){ // kiri sekiri-kirinya
                    replacement = replacement.left;
                }
                if(replacement.right != null){ // kalau replacement punya anak kanan
                    replacement.parent.left = replacement.right;
                    replacement.right.parent = replacement.parent;
                }else{ // kalau replacement tidak punya anak
                    replacement.parent.left = null;
                }
                // replace x
                if(is_root){
                    replacement.parent = null;
                    root = replacement;
                }else if(is_left){
                    replacement.parent = x.parent;
                    x.parent.left = replacement;
                }else if(is_right){
                    replacement.parent = x.parent;
                    x.parent.right = replacement;
                }               
                replacement.left = x.left;
                replacement.right = x.right;
                if(replacement.left != null){
                    replacement.left.parent = replacement;
                }
                if(replacement.right != null){
                    replacement.right.parent = replacement;
                }
                // hapus x dari tree
                x.parent = null;
                x.left = null;
                x.right = null;
            }
        }
    }

    public static void main(String[] args) {
        insert(5);
        insert(7);
        insert(6);
        insert(8);
        insert(2);
        insert(4);
        insert(1);
        view();
        delete(5);
        view();
        postfix(root);
    }   
}

Komentar

Posting Komentar

Postingan populer dari blog ini

program java

import java.util.Scanner; public class uts{     int id;     String nama, kategori;     uts next;     static Scanner in=new Scanner(System.in);     static Scanner str=new Scanner(System.in);     public void input(){        System.out.print("Masukkan NIM    : ");        id=in.nextInt();        System.out.print("Masukkan Nama   : ");        nama=str.nextLine();        System.out.print("Masukkan Kelas : ");        kategori=str.nextLine();        next=null;     }     public void read(){         System.out.println("||   "+id+"\t ||   "+nama+" \t || "+kategori+" \t||"); ...
Posting Komentar
Baca selengkapnya

Pengertian Queue dalam Struktur Data

  Pengertian Struktur Data Queue Queue adalah kumpulan data dengan penambahan data melalui satu sisi, yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head). Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur. Queue disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue jika diartikan secara harfiah, queue berarti antrian. Operasi – operasi pada Queue atau Antrian: 1. tambah(menambah item pada belakang antrian) 2. hapus ...
Posting Komentar
Baca selengkapnya