Studi Kasus Tree

STUDI KASUS 1 — SISTEM FOLDER KOMPUTER MENGGUNAKAN GENERAL TREE

Pendahuluan

Struktur folder pada komputer merupakan salah satu contoh nyata penerapan struktur data Tree. Setiap folder dapat memiliki subfolder lain sehingga membentuk hubungan hierarki antara parent dan child.

Contoh struktur folder pada sistem operasi:

C:\
├── Users
│   ├── Galuh
│   └── Public
├── Program Files
└── Windows

Karena satu folder dapat memiliki banyak subfolder, maka struktur data yang digunakan adalah:

General Tree

---

Tujuan Studi Kasus

Pada studi kasus ini, program harus mampu:

• Membuat folder baru

• Menghapus folder

• Menampilkan struktur direktori

• Mencari folder tertentu

• Menghitung jumlah folder

• Menampilkan path folder

• Melakukan traversal preorder dan postorder

---

Konsep General Tree

Apa Itu General Tree?

General Tree adalah tree yang memungkinkan setiap node memiliki banyak child.

Berbeda dengan binary tree yang maksimal memiliki dua child, general tree lebih fleksibel untuk struktur hierarki seperti sistem folder komputer.

Contoh:

Root
├── Documents
│   ├── Kuliah
│   └── Tugas
├── Pictures
└── Music

Penjelasan:

• Root memiliki 3 child

• Documents memiliki 2 child

• Pictures dan Music tidak memiliki child

---

Struktur Node pada General Tree

Pada aplikasi ini:

• Setiap node merepresentasikan folder

• Setiap folder memiliki:

  • Nama folder

  • Parent folder

  • Daftar child/subfolder

---

Implementasi Node dalam C++

class Node {
public:
    string name;
    Node* parent;
    vector<Node*> children;

    Node(string folderName, Node* p = NULL) {
        name = folderName;
        parent = p;
    }
};

---

Penjelasan Struktur Node

Bagian	Fungsi
name	Menyimpan nama folder
parent	Menyimpan alamat parent
children	Menyimpan daftar child
vector<Node*>	Digunakan karena child bisa banyak

---

Parent-Child Relationship

Hubungan utama pada tree adalah parent dan child.

Contoh:

Root
├── Documents
│   ├── Kuliah
│   └── Tugas

Hubungan:

Parent	Child
Root	Documents
Documents	Kuliah
Documents	Tugas

---

Tree Hierarchy

Pengertian Hierarki

Hierarki adalah struktur bertingkat.

Contoh level folder:

Root
├── Documents
│   ├── Kuliah
│   └── Tugas

Folder	Level
Root	0
Documents	1
Kuliah	2
Tugas	2

---

Dynamic Memory Allocation

Pengertian

Dynamic memory allocation adalah proses alokasi memori saat program berjalan menggunakan keyword:

new

---

Mengapa Dibutuhkan?

Karena:

• Jumlah folder tidak diketahui sejak awal

• User dapat menambah folder kapan saja

• Struktur tree bersifat dinamis

---

Contoh Pembuatan Node

Node* folder = new Node("Documents");

Artinya:

• Membuat node baru

• Node disimpan di heap memory

• Pointer digunakan untuk mengakses node

---

Operasi Utama pada Sistem Folder

Beberapa operasi utama yang digunakan:

• Add Folder

• Delete Folder

• Print Tree

• Search Folder

• Count Folder

• Show Path

• Traversal

---

Implementasi Program Lengkap C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// =====================================
// CLASS NODE
// =====================================

class Node {
public:
    string name;
    Node* parent;
    vector<Node*> children;

    Node(string folderName, Node* p = NULL) {
        name = folderName;
        parent = p;
    }
};

// =====================================
// CLASS GENERAL TREE
// =====================================

class FolderTree {

private:
    Node* root;

public:

    // Constructor
    FolderTree() {
        root = new Node("Root");
    }

    // =====================================
    // GET ROOT
    // =====================================

    Node* getRoot() {
        return root;
    }

    // =====================================
    // MENAMBAH FOLDER
    // =====================================

    void addFolder(Node* parent, string folderName) {

        Node* newFolder = new Node(folderName, parent);

        parent->children.push_back(newFolder);

        cout << "Folder '" << folderName
             << "' berhasil ditambahkan ke '"
             << parent->name << "'\n";
    }

    // =====================================
    // MENAMPILKAN TREE
    // =====================================

    void printTree(Node* node, int level = 0) {

        if(node == NULL)
            return;

        // Indentasi
        for(int i = 0; i < level; i++) {
            cout << "│   ";
        }

        // Tampilan tree
        if(level > 0)
            cout << "├── ";

        cout << node->name << endl;

        // Rekursif ke child
        for(Node* child : node->children) {
            printTree(child, level + 1);
        }
    }

    // =====================================
    // PREORDER TRAVERSAL
    // Root -> Child
    // =====================================

    void preorder(Node* node) {

        if(node == NULL)
            return;

        cout << node->name << endl;

        for(Node* child : node->children) {
            preorder(child);
        }
    }

    // =====================================
    // POSTORDER TRAVERSAL
    // Child -> Root
    // =====================================

    void postorder(Node* node) {

        if(node == NULL)
            return;

        for(Node* child : node->children) {
            postorder(child);
        }

        cout << node->name << endl;
    }

    // =====================================
    // SEARCH FOLDER
    // DFS Recursive
    // =====================================

    Node* search(Node* node, string target) {

        if(node == NULL)
            return NULL;

        // Jika ditemukan
        if(node->name == target)
            return node;

        // Cari di child
        for(Node* child : node->children) {

            Node* result = search(child, target);

            if(result != NULL)
                return result;
        }

        return NULL;
    }

    // =====================================
    // HITUNG JUMLAH FOLDER
    // =====================================

    int countFolder(Node* node) {

        if(node == NULL)
            return 0;

        int total = 1;

        for(Node* child : node->children) {
            total += countFolder(child);
        }

        return total;
    }

    // =====================================
    // MENAMPILKAN PATH
    // =====================================

    void showPath(Node* node) {

        if(node == NULL)
            return;

        vector<string> path;

        Node* current = node;

        while(current != NULL) {
            path.push_back(current->name);
            current = current->parent;
        }

        cout << "Path : ";

        for(int i = path.size() - 1; i >= 0; i--) {

            cout << path[i];

            if(i != 0)
                cout << "/";
        }

        cout << endl;
    }

    // =====================================
    // DELETE SUBTREE
    // =====================================

    void deleteSubtree(Node* node) {

        if(node == NULL)
            return;

        for(Node* child : node->children) {
            deleteSubtree(child);
        }

        delete node;
    }

    // =====================================
    // HAPUS FOLDER
    // =====================================

    void deleteFolder(string folderName) {

        Node* target = search(root, folderName);

        if(target == NULL) {
            cout << "Folder tidak ditemukan!\n";
            return;
        }

        // Root tidak boleh dihapus
        if(target == root) {
            cout << "Root tidak dapat dihapus!\n";
            return;
        }

        Node* parent = target->parent;

        // Hapus dari vector child parent
        for(auto it = parent->children.begin();
            it != parent->children.end(); it++) {

            if(*it == target) {
                parent->children.erase(it);
                break;
            }
        }

        // Hapus subtree
        deleteSubtree(target);

        cout << "Folder berhasil dihapus!\n";
    }
};

// =====================================
// MAIN PROGRAM
// =====================================

int main() {

    FolderTree tree;

    // Root
    Node* root = tree.getRoot();

    // =====================================
    // MEMBUAT STRUKTUR FOLDER
    // =====================================

    tree.addFolder(root, "Documents");
    tree.addFolder(root, "Pictures");
    tree.addFolder(root, "Music");

    // Cari Documents
    Node* documents = tree.search(root, "Documents");

    // Tambah child Documents
    tree.addFolder(documents, "Kuliah");
    tree.addFolder(documents, "Tugas");

    // =====================================
    // TAMPILKAN TREE
    // =====================================

    cout << "\n===== STRUKTUR FOLDER =====\n";
    tree.printTree(root);

    // =====================================
    // PREORDER
    // =====================================

    cout << "\n===== PREORDER TRAVERSAL =====\n";
    tree.preorder(root);

    // =====================================
    // POSTORDER
    // =====================================

    cout << "\n===== POSTORDER TRAVERSAL =====\n";
    tree.postorder(root);

    // =====================================
    // SEARCH
    // =====================================

    cout << "\n===== SEARCH FOLDER =====\n";

    Node* result = tree.search(root, "Tugas");

    if(result != NULL) {

        cout << "Folder ditemukan : "
             << result->name << endl;

        tree.showPath(result);

    } else {

        cout << "Folder tidak ditemukan\n";
    }

    // =====================================
    // COUNT FOLDER
    // =====================================

    cout << "\n===== JUMLAH FOLDER =====\n";

    cout << "Total Folder : "
         << tree.countFolder(root)
         << endl;

    // =====================================
    // DELETE FOLDER
    // =====================================

    cout << "\n===== HAPUS FOLDER =====\n";

    tree.deleteFolder("Pictures");

    // =====================================
    // TAMPILKAN TREE SETELAH DELETE
    // =====================================

    cout << "\n===== STRUKTUR SETELAH DELETE =====\n";

    tree.printTree(root);

    return 0;
}

---

Output Program

Source Code:Studi kasus tree

---

Penjelasan Operasi Program

1. Menambah Folder

Folder baru ditambahkan sebagai child dari folder tertentu.

Contoh:

parent->children.push_back(newFolder);

---

2. Menampilkan Struktur Folder

Tree ditampilkan secara hierarki menggunakan rekursi.

Contoh:

Root
├── Documents
│   ├── Kuliah
│   └── Tugas

---

3. Preorder Traversal

Urutan traversal:

Root → Child

Hasil:

Root
Documents
Kuliah
Tugas
Pictures
Music

---

4. Postorder Traversal

Urutan traversal:

Child → Root

Hasil:

Kuliah
Tugas
Documents
Pictures
Music
Root

---

5. Search Folder

Pencarian dilakukan menggunakan DFS rekursif.

Contoh:

Node* result = search(child, target);

---

6. Menghitung Jumlah Folder

Semua node dihitung menggunakan rekursi.

Contoh:

total += countFolder(child);

---

7. Menampilkan Path Folder

Path menunjukkan jalur dari root menuju folder tujuan.

Contoh:

Root/Documents/Tugas

---

8. Menghapus Folder

Jika folder dihapus:

• seluruh subtree ikut terhapus,

• child dihapus dari vector parent,

• memory dibersihkan menggunakan rekursi.

---

Kompleksitas Algoritma

Operasi	Kompleksitas
Traversal	O(n)
Search	O(n)
Count Folder	O(n)
Insert Child	O(1)

---

Kelebihan General Tree

• Fleksibel

• Dapat memiliki banyak child

• Cocok untuk struktur folder

• Representasi hierarki lebih natural

• Mudah dikembangkan

---

Kekurangan General Tree

• Traversal lebih kompleks

• Membutuhkan dynamic memory

• Pengelolaan pointer lebih sulit

• Search bisa lambat pada tree besar