Pertemuan 10 (Tree)

Rinaltra Nabasa S

5025251024

Struktur Data D

---

Konsep Dasar Tree

Tree adalah struktur data hierarki non-linear. Berbeda dengan array atau linked list yang bersifat linear, tree memiliki struktur bercabang seperti pohon terbalik — akar di atas, daun di bawah.

Terminologi Penting

Istilah	Penjelasan
Node	Elemen/simpul dalam tree
Root	Node paling atas (tidak punya parent)
Edge	Garis penghubung antar node
Parent	Node yang memiliki anak
Child	Node yang berada di bawah parent
Leaf	Node yang tidak punya anak
Height	Jarak dari root ke leaf terdalam

---

Struktur Kode

1. Struct Node

struct Node {
   char data;     // nilai yang disimpan
   Node* left;    // pointer ke anak kiri
   Node* right;   // pointer ke anak kanan
};

Ini adalah Binary Tree — setiap node maksimal punya 2 anak (kiri dan kanan).

2. Cara Membangun Tree (main)

Kode menggunakan Level-Order Insertion dengan queue. Setiap node baru diisi ke posisi paling kiri yang kosong, baris per baris:

Input: A B C D E F G
```---

## 4 Jenis Traversal (Penelusuran)

Traversal adalah cara mengunjungi semua node dalam tree. Kode mengimplementasikan 4 jenis:---

## Cara Kerja Traversal (Rekursi)

Ketiga traversal pertama menggunakan **rekursi**. Pola dasarnya sama, yang membedakan hanyalah *kapan* node dicetak:

```cpp
void preorder(Node* root) {
    if (root == NULL) return;   // base case
    cout << root->data;         // ← cetak DULU (Pre)
    preorder(root->left);       // lalu rekursi kiri
    preorder(root->right);      // lalu rekursi kanan
}

void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);        // rekursi kiri dulu
    cout << root->data;         // ← cetak DI TENGAH (In)
    inorder(root->right);
}

void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data;         // ← cetak PALING AKHIR (Post)
}

Level Order berbeda — menggunakan queue (antrian), bukan rekursi:

1. Masukkan root ke queue
2. Ambil node depan, cetak, lalu masukkan anak-anaknya
3. Ulangi sampai queue kosong

---

Output Program

Jika input 7 node dengan nilai A B C D E F G, outputnya:

Preorder  : A B D E C F G
Inorder   : D B E A F C G
Postorder : D E B F G C A
LevelOrder: A B C D E F G

---

Ringkasan

Tree adalah fondasi dari banyak struktur data lanjutan seperti BST, AVL Tree, Heap, dan Trie. Memahami traversal (Preorder, Inorder, Postorder, Level Order) adalah kemampuan dasar yang wajib dikuasai karena digunakan dalam pencarian, pengurutan, dan evaluasi ekspresi.

Kode

Tree (pohon) adalah struktur data non-linear yang berbentuk hierarki dan terdiri dari kumpulan elemen yang disebut node (simpul). Setiap node dalam tree dihubungkan oleh garis yang disebut edge (sisi), yang bisa bersifat terarah (directed) maupun tidak terarah (undirected).

Implementasi Kode: 

#include <iostream>

#include <queue>

using namespace std;

struct Node {

   char data;

   Node* left;

   Node* right;

   Node(char val) {

      data = val;

      left = right = NULL;

   }

};

void preorder(Node* root) {

   if (root == NULL) return;

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

   preorder(root->left);

   preorder(root->right);

}

void inorder(Node* root) {

   if (root == NULL) return;

   inorder(root->left);

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

   inorder(root->right);

}

void postorder(Node* root) {

   if (root == NULL) return;

   postorder(root->left);

   postorder(root->right);

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

}

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() {

   int n;

   char data;

   cin >> n;

   Node* root = NULL;

   queue<Node*> q;

   int i = 0;

   while (n--) {

      cout << "Values: ";

      cin >> data;

      Node* newNode = new Node(data);

        if (root == NULL) {

            root = newNode;

            q.push(root);

        } else {

            Node* current = q.front();

            if (current->left == NULL) {

                current->left = newNode;

                q.push(newNode);

            }

            else if (current->right == NULL) {

                current->right = newNode;

                q.push(newNode);

                q.pop();

            }

        }

    }

    cout << "Preorder : ";

    preorder(root);

    cout << "\nInorder : ";

    inorder(root);

    cout << "\nPostorder : ";

    postorder(root);

    cout << "\nLevelOrder: ";

    levelOrder(root);

    return 0;

}