Tree, pertemuan 10

 Nama : Fakhrian Elanta

NRP : 5025251019

Tree

Merupakan struktur data non-linear yang digunakan untuk menyimpan data. Perbedaan struktur data linear dan non-linear terletak pada urutan elemen dan hubungan antar elemen itu sendiri. Pada struktur data linear data diurutkan secara sekuensial (berurutan), namun pada non-linear menyusun data secara hierarkis atau saling berhubungan, tidak berurutan.

Traverse

Pada tree dilakukan traversal untuk melihat isi data yang tersimpan pada tree tersebut. Pada cara traversal sendiri, terdapat beberapa cara tergantung bagaimana kita mau mengecek elemennya.

DFS (depth first search)

Metode ini menyelam sedalam mungkin ke dalam satu cabang sebelum berpindah ke cabang berikutnya. Metode ini paling sering diimplementasikan menggunakan rekursi.

In-order traversal (Kiri, Akar, Kanan): Mengunjungi subpohon kiri, kemudian simpul saat ini, lalu subpohon kanan. Penggunaan: Untuk Pohon Pencarian Biner (Binary Search Tree/BST), ini mengembalikan nilai dalam urutan menaik.

Pre-order traversal (Akar, Kiri, Kanan): Mengunjungi simpul saat ini terlebih dahulu, kemudian subpohon kiri dan kanan. Penggunaan: Berguna untuk membuat salinan pohon.

Post-order traversal (Kiri, Kanan, Akar): Mengunjungi kedua subpohon sebelum simpul saat ini. Penggunaan: Digunakan untuk menghapus pohon atau menghasilkan ekspresi postfix.

Berikut merupakan contoh implementasinya

#include <bits/stdc++.h>

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

    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\t: ";

    preorder(root);

    cout << "\nInorder\t\t: ";

    inorder(root);

    cout << "\nPostorder\t: ";

    postorder(root);

    cout << "\nLevelOrder\t: ";

    levelOrder(root);

    return 0;

}

Source code : github