Tree C++

 TREE DALAM C++

Pengertian Tree

Tree adalah struktur data non-linear yang berbentuk hierarki dan terdiri dari kumpulan node yang saling terhubung melalui edge (garis penghubung). Berbeda dengan struktur data linear seperti array atau linked list, tree memungkinkan data disusun dalam bentuk bercabang sehingga lebih efisien untuk proses pencarian dan pengelolaan data.

Pada struktur tree:

• Node → menyimpan data

• Edge → penghubung antar node

• Root → node paling atas

• Child → node turunan

• Leaf → node tanpa child

---

Mengapa Tree Dibutuhkan?

Struktur data linear seperti:

• Array

• Linked List

• Stack

• Queue

menyimpan data secara berurutan sehingga ketika data semakin besar:

• proses pencarian menjadi lebih lambat,

• insert dan delete kurang efisien,

• serta sulit merepresentasikan hubungan hierarki.

Tree hadir sebagai solusi karena memiliki struktur non-linear yang lebih fleksibel.

---

Keunggulan Tree

Beberapa kelebihan tree:

• Penyimpanan data lebih terstruktur

• Pencarian data lebih cepat

• Manipulasi data lebih efisien

• Mendukung struktur hierarki

• Digunakan dalam banyak sistem seperti:

  • File Explorer

  • Database

  • AI Decision Tree

  • Struktur HTML DOM

---

Struktur Node pada Tree

Setiap node pada binary tree biasanya memiliki:

Bagian	Fungsi
data	Menyimpan nilai
left	Pointer ke child kiri
right	Pointer ke child kanan

---

Implementasi Node ke dalam C++

Berikut struktur node pada tree:

struct Node {
    char data;
    Node* left;
    Node* right;

    Node(char val) {
        data = val;
        left = right = NULL;
    }
};

---

Ilustrasi Tree

Tree yang digunakan pada program:

        A
       / \
      B   C
     / \   \
    D   E   F

Keterangan:

• A → Root

• B dan C → Child dari A

• D, E, F → Leaf node

---

Implementasi Tree Lengkap dalam C++

Berikut program lengkap implementasi tree beserta traversal:

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    char data;
    Node* left;
    Node* right;

    Node(char val) {
        data = val;
        left = right = NULL;
    }
};

// Preorder Traversal
void preorder(Node* root) {
    if (root == NULL) return;

    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

// Inorder Traversal
void inorder(Node* root) {
    if (root == NULL) return;

    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

// Postorder Traversal
void postorder(Node* root) {
    if (root == NULL) return;

    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

// Level Order Traversal
void levelOrder(Node* root) {
    if (root == NULL) return;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {

        Node* current = q.front();
        q.pop();

        cout << current->data << " ";

        if (current->left != NULL)
            q.push(current->left);

        if (current->right != NULL)
            q.push(current->right);
    }
}

int main() {

    // Membuat Tree
    Node* root = new Node('A');

    root->left = new Node('B');
    root->right = new Node('C');

    root->left->left = new Node('D');
    root->left->right = new Node('E');

    root->right->right = new Node('F');

    cout << "Preorder : ";
    preorder(root);

    cout << "\nInorder : ";
    inorder(root);

    cout << "\nPostorder : ";
    postorder(root);

    cout << "\nLevel Order : ";
    levelOrder(root);

    return 0;
}

Output Program

Source code:Implementasi Tree

Program di atas membuat sebuah binary tree dengan enam node, kemudian melakukan traversal menggunakan beberapa metode penelusuran tree.

Traversal digunakan untuk mengunjungi seluruh node dalam tree dengan urutan tertentu.

---

Jenis Traversal pada Tree

Traversal adalah proses mengunjungi setiap node pada tree.

Beberapa traversal yang umum digunakan:

• Preorder

• Inorder

• Postorder

• Level Order

---

Preorder Traversal

Preorder memiliki urutan:

Root → Left → Right

Contoh kode:

void preorder(Node* root) {
    if (root == NULL) return;

    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

Hasil traversal:

A B D E C F

---

Inorder Traversal

Inorder memiliki urutan:

Left → Root → Right

Contoh kode:

void inorder(Node* root) {
    if (root == NULL) return;

    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

Hasil traversal:

D B E A C F

---

Postorder Traversal

Postorder memiliki urutan:

Left → Right → Root

Contoh kode:

void postorder(Node* root) {
    if (root == NULL) return;

    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

Hasil traversal:

D E B F C A

---

Level Order Traversal

Level Order menelusuri node berdasarkan level menggunakan Queue.

Urutan traversal:

A B C D E F

Contoh kode:

queue<Node*> q;
q.push(root);

Traversal ini juga dikenal sebagai:

Breadth First Search (BFS)

---

Operasi Dasar pada Tree

Dalam struktur data tree terdapat beberapa operasi dasar:

Operasi	Fungsi
Traversal	Menelusuri node
Insertion	Menambahkan node
Deletion	Menghapus node
Searching	Mencari node tertentu
Updating	Mengubah data node