Pages

Rabu, 06 Maret 2013

TREE (Pohon)


       
           Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen.

            Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root.

Contoh : 

             Direktori/folder pada windows atau linux.




A.Istilah – Istilah Pada Tree



                         Contoh Tree :


B.OPERASI DASAR


v  Create: membentuk sebuah tree baru yang kosong.
v  Clear: menghapus semua elemen tree.
v  Empty: mengetahui apakah tree kosong atau tidak
v  Insert: menambah node ke dalam Tree secara rekursif.  Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri.  Untuk data pertama akan menjadi elemen root.
v  Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu.  Syaratnya adalah tree tidak boleh kosong.
v  Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.
v  Count: menghitung jumlah node dalam Tree
v  Height : mengetahui kedalaman sebuah Tree
v  Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree
v  Child : mengetahui anak dari sebuah node (jika punya)



C.BST (Binary Search Tree)

      Suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah.
Tiap node dalam binary tree hanya boleh memiliki paling banyak dua child. 

     Contoh BST :



D.Tree Traversal
       Teknik menyusuri tiap node dalam sebuah tree secara sistematis, sehingga semua node dapat dan hanya satu kali saja dikunjungi
Ada tiga cara traversal
l  preorder
l  inorder
l  postorder
Untuk tree yang kosong, traversal tidak perlu dilakukan


1.Preorder (SLR)
  1. Simpul / Node nya
  2. Subtree sebelah kiri (Left)
  3. Subtree sebelah kana (Right) 
         Contoh :

      Implementasi dalam bahasa C
      struct node {
                         struct node *left;
                         struct node *right;
                         char                 label;
                         }
                          void preorder(struct node *p)
                         {
                          if (p==NULL)  return;       jika empty-tree, tidak perlu lakukan
                          printf(“visit %c ”, p->label);  tampilkan label node yang dikunjungi
                          preorder(p->left);            traverse the left subtree
                          preorder(p->right);    traverse the right subtree
                          }

2.Inorder (LSR)

  1. Subtree sebelah kiri (Left)
  2. Simpul / Node nya
  3. Subtree sebelah kana (Right)
          contoh :


     Implementasi dalam bahasa C
     struct node {
                        struct node *left;
                        struct node *right;
                        char                 label;
                       }
                        void inorder(struct node *p)
                       {
                        if (p==NULL)  return;       jika empty-tree, tidak perlu lakukan
                        inorder(p->left);            traverse the left subtree
                        printf(“visit %c ”, p->label);  tampilkan label node yang dikunjungi
                        inorder(p->right);    traverse the right subtree
                        }

3.Postorder (LRS)

  1. Subtree sebelah kiri (Left)
  2. Subtree sebelah kana (Right)
  3. Simpul /Node nya 
          contoh :
     Implementasi dalam bahasa C
     struct node {
                        struct node *left;
                        struct node *right;
                        char                 label;
                       }
                         void postorder(struct node *p)
                       {
                         if (p==NULL)  return;       jika empty-tree, tidak perlu lakukan
                         postorder(p->left);            traverse the left subtree
                         postorder(p->right);    traverse the right subtree
                         printf(“visit %c ”, p->label);  tampilkan label node yang dikunjungi
                       }





Tidak ada komentar:

Posting Komentar