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

                       }