Binary Tree C++

 Pengertian Tree

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.

Sebuah binary search tree (bst) adalah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. Value pada semua node subpohon sebelah kiiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing-masing subpohon tersebut (kiri dan kanan) itu sendiri adalah juga binary search tree.

Pengertian Binary Tree

    Binary Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkanhubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya ( disebut subtree). Dalam tree terdapat jenis-jenis tree yang memiliki sifat khusus, diantaranya adalah binary tree.

   Binary tree adalah suatu tree dengan syarat bahwa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.

      Sebuah pohon biner adalah grafik asiklis yang terhubung  dimana setiap tingkatan  dari susut tidak lebih dari 3. Ini dapat ditunjukkan bahwa dalam pohon biner manapun, terdapat persis dua atau lebih simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga, tetapi bisa terdapat angka apa saja dari simpul dengan tingkat dua.

    Sebuah jalan lain untuk mendefinisikan pohon biner melalui definisi rekursif pada grafik langsung.Sebuah pohon biner dapat berarti :

-   Sebuah sudut tunggal.

-  Sebuah graf yang dibentuk dengan mengambil dua pohon biner, menambahkan sebuah sudut, dan menambahkan sebuah panah langsung dari sudut yang baru ke akar dalam setiap pohon biner.

Istilah-istilah dalam pohon biner

1. Predesesor

Node yang berada diatas node tertentu. 

(contoh :  B predesesor dari E dan F) 

2. Succesor

Node yang berada dibawah node tertentu.

(contoh :  E dan F merupakan succesor dari B)

3. Ancestor

Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama. 

(contoh :  A dan B merupakan ancestor dari F)

4.Descendant

Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama. 

(contoh :  F dan B merupakan ancestor dari A)

5.Parent

Predesesor satu level diatas satu node

(contoh : B merupakan parent dari F)

6.Child

Succesor satu level dibawah satu node

(contoh : F merupakan child dari B)

7.Sibling

Node yang memiliki parent yang sama dengan satu node (contoh : E dan F adalah sibling)

8.Subtree

Bagian dari tree yang berupa suatu node beserta descendant-nya

(contoh : Subtree B, E, F dan Subtree  D, G, H)

9.Size

Banyaknya node dalam suatu tree 

(contoh : gambar tree diatas memiliki size = 8)

10.Height 

Banyaknya tingkat/level dalam suatu tree 

(contoh : gambar tree diatas memiliki height = 3)

11.Root (Akar)

Node khusus dalam tree yang tidak memiliki predesesor (Contoh : A)

12.Leaf (Daun)

Node-node dalam tree yang tidak memiliki daun

(contoh : Node E,F,C,G,H)

13.Degree (Derajat)

Banyaknya child yang dimiliki oleh suatu node

(contoh : Node A memiliki derajat 3, node B memiliki derajat 2) 

Kunjungan pada pohon Biner

Kunjungan pohon biner terbagi menjadi  3 bentuk binary tree :

1.  Kunjungan secara preorder ( Depth First Order),

mempunyai urutan :

a.  Cetak isi simpul yang dikunjungi ( simpul akar ),

b.  Kunjungi cabang kiri,

c.  Kunjungi cabang kanan .

void Preorder(Node* root) 

{ 

    if (root == NULL) 

        return; 

    cout << root->data << " ";  

    Preorder(root->left);      

    Preorder(root->right); 

}  

2.  Kunjungan secara inorder ( symetric order),

mempunyai urutan :

a.  Kunjungi cabang kiri,

b.  Cetak isi simpul yang dikunjungi (simpul akar),

c.   Kunjungi  cabang kanan . 

void inOrder(Node* root) 

{ 

    if (root != NULL) 

    { 

        inOrder(root->left); 

        cout << root->data <<" "; 

        inOrder(root->right); 

    } 

} 

3.  Kunjungan secara postorder,

mempunyai urutan :

a.    Kunjungi cabang kiri,

b.    Kunjungi cabang kanan,

c.     Cetak isi simpul yang dikunjungi ( simpul akar ). 

void Postorder(Node* root) 

{ 

    if (root == NULL) 

        return; 

  

    Postorder(root->left); 

    Postorder(root->right);   

    cout << root->data << " "; 

} 

Pengertian Tree dalam Struktur Data

Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemen khusus yang disebut root dan Node lainnya terbagi menjadi Himpunan-Himpunan yang tak saling berhubungan Satu sama lainnya (disebut subtree).

Untuk jelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree.

• Parent : predecssor satu level di atas suatu node.
• Child : successor satu level di bawah suatu node.
• Sibling : node-node yang memiliki parent yang sama dengan suatu node.
• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
• Size : banyaknya node dalam suatu tree.
• Height : banyaknya tingkatan/level dalam suatu tree.
• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
• Leaf : node-node dalam tree yang tak memiliki seccessor.
• Degree : banyaknya child yang dimiliki suatu node.

Contoh Program dalam C++;

#include <iostream> 

#include <bits/stdc++.h> 

using namespace std; 

struct Node 

{ 

    int data; 

    Node* left, * right; 

}; 

  

Node* newNode(int data) 

{ 

    Node* node = (Node*)malloc(sizeof(Node)); 

    node->data = data; 

    node->left = node->right = NULL; 

    return (node); 

} 

  

Node* insertLevelOrder(int arr[], Node* root, 

                       int i, int n) 

{ 

    if (i < n) 

    { 

        Node* temp = newNode(arr[i]); 

        root = temp; 

  

        root->left = insertLevelOrder(arr, 

                   root->left, 2 * i + 1, n); 

  

        root->right = insertLevelOrder(arr, 

                  root->right, 2 * i + 2, n); 

    } 

    return root; 

} 

  

void inOrder(Node* root) 

{ 

    if (root != NULL) 

    { 

        inOrder(root->left); 

        cout << root->data <<" "; 

        inOrder(root->right); 

    } 

} 

void Preorder(Node* root) 

{ 

    if (root == NULL) 

        return; 

    cout << root->data << " ";  

    Preorder(root->left);      

    Preorder(root->right); 

}  

void Postorder(Node* root) 

{ 

    if (root == NULL) 

        return; 

  

    Postorder(root->left); 

    Postorder(root->right);   

    cout << root->data << " "; 

} 

  

int main() 

{ 

    int arr[] = { 27, 14, 35, 10, 19, 31, 42}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

    Node* root = insertLevelOrder(arr, root, 0, n); 

    

    cout << "\nPreorder binary tree is \n"; 

    Preorder(root); 

  

    cout << "\nInorder binary tree is \n"; 

    inOrder(root);  

cout << "\nPostorder binary tree is \n"; 

    Postorder(root);    

}