Pertemuan 10 - Tree

 

Tree di C++

Nama: Hadryan Rizky Dimas Saputra

NRP: 5025251027

Kelas: Struktur Data (D) 2026

Pertemuan: 10

Source Code: pertemuan_10

Implementasi Tree pada C++

Deskripsi (Fungsi) Program: 

Tree adalah struktur data non-linear yang merepresentasikan hubungan hierarkis (bertingkat) antar elemen. Elemen-elemen ini disebut Node (Simpul).

• Root (Akar): Node paling atas dari tree.

• Parent & Child: Node yang berada di atas disebut Parent, dan node yang bercabang di bawahnya disebut Child.

• Leaf (Daun): Node paling ujung bawah yang tidak memiliki child atau cabang lagi.

• Binary Tree: Jenis spesifik tree di mana setiap node maksimal hanya boleh memiliki dua cabang, yaitu left (kiri) dan right (kanan).

Kode program bertujuan untuk membangun sebuah Binary Tree dan kemudian mendemonstrasikan 4 cara berbeda untuk menelusuri (Traversals) semua node di dalam tree tersebut agar bisa dicetak ke layar.

Di fungsi main(), terdapat tree dengan bentuk seperti ini:

        A
      /   \
     B     C
    / \   /
   D   E F

Setelah tree terbentuk, program memanggil 4 fungsi penelusuran (traversal). Perbedaan keempatnya terletak pada urutan kunjungan ke Node saat ini (Root), cabang Kiri (Left), dan cabang Kanan (Right).

A. Preorder Traversal (Root - Left - Right)

• Cara kerja: Kunjungi node saat ini dulu, lalu telusuri seluruh cabang kiri, baru telusuri seluruh cabang kanan.

• Hasil cetak: A B D E C F

• Penggunaan: Biasanya digunakan untuk membuat salinan (copy) dari sebuah tree.

B. Inorder Traversal (Left - Root - Right)

• Cara kerja: Telusuri seluruh cabang kiri sampai mentok, lalu kunjungi node saat ini, baru telusuri seluruh cabang kanan.

• Hasil cetak: D B E A F C

• Penggunaan: Pada jenis tree tertentu (seperti Binary Search Tree), inorder akan mencetak data secara berurutan dari terkecil hingga terbesar.

C. Postorder Traversal (Left - Right - Root)

• Cara kerja: Telusuri seluruh cabang kiri, lalu seluruh cabang kanan, baru terakhir kunjungi node saat ini (root selalu dicetak paling akhir).

• Hasil cetak: D E B F C A

• Penggunaan: Sering digunakan untuk menghapus tree dari memori karena kita harus menghapus anak-anaknya terlebih dahulu sebelum menghapus induknya.

D. Level Order Traversal (Menyamping / Breadth-First)

• Cara kerja: Menelusuri tree lapis demi lapis (level by level) dari atas ke bawah, dan dari kiri ke kanan menggunakan bantuan antrean (queue).

• Hasil cetak: A B C D E F (Lapis 1: A. Lapis 2: B, C. Lapis 3: D, E, F).

Code:

Hasil/Output Program:

Penjelasan Program:

Bagian	Baris Kode	Penjelasan
1. Persiapan & Struktur Node	#include <bits/stdc++.h>	Mengimpor semua library standar C++ yang dibutuhkan (termasuk untuk antrean/queue).
	using namespace std;	Menggunakan penamaan standar bawaan C++ agar kodenya lebih ringkas tanpa perlu mengetik std::.
	struct Node {	Membuat kerangka/cetakan bernama Node untuk membangun struktur Tree.
	char data;	Variabel untuk menyimpan nilai berupa satu huruf (misal: 'A', 'B').
	Node* left;	Pointer (penunjuk) ke cabang/anak sebelah kiri.
	Node* right;	Pointer (penunjuk) ke cabang/anak sebelah kanan.
	Node(char value) {	Constructor, fungsi yang otomatis berjalan saat satu Node baru dibuat.
	data = value;	Mengisi node yang baru dibuat dengan huruf yang dikirimkan.
	left = nullptr; right = nullptr;	Menetapkan bahwa node baru ini secara bawaan belum punya anak kiri maupun kanan (kosong).
2. Penelusuran Rekursif (Contoh: Preorder)	void preorder(Node* root) {	Membuat fungsi penelusuran yang menerima titik awal (root).
	if (root == nullptr) return;	Kondisi Berhenti: Jika cabang yang dicek kosong, berhentilah mundur ke langkah sebelumnya.
	cout << root->data << " ";	Mengambil dan mencetak huruf pada node saat ini ke layar. (Pada inorder/postorder, urutan baris ini digeser).
	preorder(root->left);	Menyuruh program menelusuri terus ke cabang kiri sampai mentok.
	preorder(root->right);	Menyuruh program menelusuri terus ke cabang kanan sampai mentok.
3. Penelusuran Level Order	void levelOrder(Node* root) {	Membuat fungsi untuk penelusuran per tingkat/level (dari atas ke bawah, kiri ke kanan).
	queue<Node*> q;	Membuat antrean bernama q untuk mengatur urutan kunjungan node.
	q.push(root);	Memasukkan node akar (paling atas) ke dalam antrean sebagai langkah pertama.
	while (!q.empty()) {	Lakukan perulangan pengecekan terus-menerus selama antrean belum kosong.
	Node* current = q.front();	Mengambil node yang berada di paling depan antrean saat ini.
	q.pop();	Mengeluarkan node tersebut dari antrean karena sudah giliran diproses.
	cout << current->data << " ";	Mencetak huruf dari node yang sedang diproses.
	if (current->left != nullptr) ...	Jika node ini punya anak sebelah kiri, masukkan anaknya ke barisan antrean.
	if (current->right != nullptr) ...	Jika node ini punya anak sebelah kanan, masukkan anaknya ke barisan antrean juga.
4. Fungsi Utama (Main)	int main(void) {	Titik awal berjalannya keseluruhan program komputer.
	Node* root = new Node('A');	Membuat node akar (paling atas) dengan huruf 'A'.
	root->left = new Node('B');	Membuat node 'B' dan memasangnya sebagai anak kiri dari 'A'.
	... = new Node('C'); (dst)	Menyambungkan node 'C', 'D', 'E', dan 'F' ke posisi yang sesuai untuk membentuk Tree.
	cout << "Preorder...";	Mencetak teks label ke layar agar output mudah dibaca.
	preorder(root);	Memanggil fungsi penelusuran preorder yang sudah dibuat, dimulai dari titik root. (Berlaku juga untuk Inorder, Postorder, Level Order).
	return 0;	Memberi tahu komputer bahwa program telah selesai berjalan tanpa ada error.