Tree (Pohon)

Diposkan oleh Risa , Label: , Thursday, March 7, 2013 8:36 PM

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. Terminologi Pada Tree

         
      Contoh Tree :

B. Operasi Dasar
  • Create: membentuk sebuah tree baru yang kosong.
  •  Clear: menghapus semua elemen tree.
  • Empty: mengetahui apakah tree kosong atau tidak.
  •  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.
  • Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu.  Syaratnya adalah tree tidak boleh kosong.
  •  Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.
  • Count: menghitung jumlah node dalam Tree.
  • Height : mengetahui kedalaman sebuah Tree
  • Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree
  • 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
preorder
inorder
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
                       }
             Contoh Preorder, Postorder, Inorder

4 Response to "Tree (Pohon)"

  1. Unknown says:
    August 9, 2016 at 4:51 AM

    makasih kang sangat membantu

  2. Unknown says:
    December 18, 2016 at 8:17 PM

    Yang simpulnya lebih dadi 2 gimana ya. Bingung

  3. Sardo says:
    October 23, 2017 at 2:07 AM

    terima kasih sangat membantu

  4. pipit muna ashofah says:
    December 2, 2020 at 1:00 AM

    Tolong bantu aku jawab soal ini soalnya mau aku kumpulin

    Gambarkan BST dari: a.12,35,9,11,3,17,23,35,15,31,20,11 dan
    b, 44,55,12,42,94,18,6,67,12,42 lakukan traversal secara inorder,post order dan pre order

Post a Comment

Subscribe to: Post Comments (Atom)