Pengertian dan Contoh Program Struktur Data Tree

Konsep Struktur Data Tree

Hierarki pada struktur tree dapat diibaratkan seperti sebuah pohon keluarga di mana terdapat hubungan antara orang tua dan anak. Titik yang lebih atas disebut simpul induk sedangkan simpul di bawahnya adalah simpul anak.
Konsep Struktur data yang terdiri dari akar dan simpul simpul yang berada dibawahnya. Struktur data yang menunjukkan hubungan bertingkat (hirarki). Merupaka struktut data yang non linier.
Contoh : struktut organisasi, silsilah keluarga, struktur folder.
Untuk melakukan operasi apapun dalam operasi apapun dalam struktut linier, kompleksitas waktu meningkat seiring dengan peningkatan ukutan data. tapi itu tidak dapat diterima di dunia komputasi saat ini.
Struktur data tree memungkinkan akses lebih cepat dan mudah ke data karena merupakan struktur data non linier.

Terminologi Tree

Penjelasan:

1. Node: node adalah entitas yang berisi kunci atau nilai dan pointer ke node anaknya. Simpul paling atas adalah root. Node adalah simpul dari masing masing data dari suatu tree. Sebuah simpul dapat mengandung sebuah nilai atau suatu kondisi atau menggambarkan sebuah struktur data yang terpisah atau bagian dari pohon itu sendiri. Dari gambar diatas dapat disimpulkan nodenya adalah: node = A, B, C, D, E, F, G, H

2. Root: Node teratas tidak punya parent. root = A

3. Edge: Link adalah yang menghubungkan node dengan node lainnya.

4. Daun/ Leaf: Sebuah simpul yang berada pada tingkat terendah dari pohon dinamakan daun(leaf node). Sejak mereka terletak pada tingkat paling bawah maka mereka tidak memiliki anak satupun. Leaf = D, E, F, G, H.

5. Subtree: Subtree adalah suatu bagian dari pohon struktur data yang dapat dilihat sebagai sebuah pohon lain yang berdiri sendiri.

6. Level: Bilangan yang menunjukkan hirarki dari suatu node, node root memiliki level 0, node cabang root memiliki level 1, node cabang berikutnya dari node level 1 memiliki level 2, dan seterusnya.

7. Hutan: Kumpulan pohon pohon yang terpisah pisah disebut pohon. Anda dapat membuat hutan dengan memotong akar pohon.

8. Parent: Node yang tepat berada di atas node lain. Parent(D) = B.

9. Child: Cabang dari sebuah node. Child(B) = D dan E.

10. Sibling: Node lain yang memiliki parent yang sama. Sibling(B) = C.

11. Ancestor: Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama. Ancestor(G) = F, C, dan A

12. Descendant: Seluruh node terletak sesudah node tertentu dan terletak pada jalur yang sama. Descendant (C) = F, G, H.

13. Size: Jumlah node dalam suatuu tre. Size = 8

14. Depth: Adalah jumlah tingkatan/level dalam sebuah tree. Depth = 4.

BInary Tree

Struktur data tree dimana setiap nodenya hanya memiliki satu atau dua subtree. Kedua subtree harus terpisah yang terdiri dari left atau right subtree. Kelebihan binary tree adalah mudah dalam penyusunan algoritma sorting, searching data relative cepat serta fleksibel dalam penambahan dan penghapusan data.

Transversal Tree

Operasi Traversal adalah operasi kunjungan dan juga menampilkan node node yang ada didalam tree dimana setiap node akan dikunjungi hanya sekali saja. Dalam operasi traversal terdapat 3 macam cara yaitu:

1)    PreOrder
Algoritma:
•    Kunjungi node root
•    Lakukan traverse subtree kiri secara rekursif
•    Lakukan traverse subtree kanan
2)    InOrder
Algorithma
•    ranverse subtree kiri
•    Kunjungi node root
•    Tranverse subtree kanan
3)    PostOrder
Algoritmha
•    Tranverse subtree kiri
•    Tranver subtree kanan
•    Kunjungi root
 

Contoh Program

#include
using namespace std;

struct Node{
    char label;
    Node *kiri, *kanan, *parent;
};

Node *root, *nodebaru;

buatTreeBaru(char label){
    if(root != NULL){
        cout<<"Tree Sudah Dibuat"<     }else{
        root = new Node();
        root->label = label;
        root->kiri = NULL;
        root->kanan = NULL;
        root->parent = NULL;
        cout<< label <<" Tree Baru Berhasil Dibuat"<     }
}

Node *masukKiri(Node *node, char label){
    if (root == NULL){
        cout<         return NULL;
    }else{
        if (node->kiri != NULL){
            cout<<"Sudah Terisi"<             return NULL;
        }else{
            nodebaru = new Node();
            nodebaru->kiri = NULL;
            nodebaru->kanan = NULL;
            nodebaru->label = label;
            nodebaru->parent = node;
            node->kiri = nodebaru;
            coutlabel<             return nodebaru;
        }
    }
}
Node *masukKanan(Node *node, char label){
    if (root == NULL){
        cout<         return NULL;
    }else{
        if (node->kanan != NULL){
            cout<<"Sudah Terisi"<             return NULL;
        }else{
            nodebaru = new Node();
            nodebaru->kiri = NULL;
            nodebaru->kanan = NULL;
            nodebaru->label = label;
            nodebaru->parent = node;
            node->kanan = nodebaru;
            coutlabel<             return nodebaru;
        }
    }
}

void PreOrder(Node *node = root){
    if(root == NULL ){
        cout<     }else{
        if(node != NULL){
            cout<< node->label <<" -> ";
            PreOrder(node->kiri);
            PreOrder(node->kanan);
        }
    }
}
void InOrder(Node *node = root){
    if (root == NULL){
        cout<     }else{
        

if(node != NULL){
            InOrder(node->kiri);
            cout<< node->label <<" -> ";
            InOrder(node->kanan);
    }
}
}

int main(){
    Node *nodeB, *nodeC, *nodeD, *nodeE, *nodeF, *nodeG, *nodeH, *nodeI, *nodeJ;
    buatTreeBaru('A');
    nodeB = masukKiri(root, 'B');
    nodeC = masukKanan(root, 'C');
    nodeD = masukKiri(nodeB, 'D');
    nodeE = masukKanan(nodeB, 'E');
    nodeF = masukKiri(nodeC, 'F');
    nodeG = masukKanan(nodeC, 'G');
    cout<     PreOrder();
    cout<     InOrder();
    }