Mengenal Algoritma Tree (Pohon)

bundet

Struktur pada tree (pohon) tidak linear seperti pada struktur linked list, stack, dan queue. Setiap node pada tree mempunyai tingkatan, yaitu orang tua (parent) dan anak (child). Struktur ini sebenarnya merupakan bentuk khusus dari struktur tree yang lebih umum, setiap orang tua hanya memiliki dua anak sehingga disebut pohon biner (binary tree), yaitu anak kiri dan anak kanan.

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree dapat didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut root dan node, disebut sub tree/sub pohon atau cabang. Sehingga secara sederhana pohon bisa didefinisikan sebagai kumpulan elemen yang salah satu elemennya disebut dengan akar (root) dan elemen yang lainnya (simpul), terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu dengan yang lainnya.

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Keterangan:

Left Child : B, D, H, …
Right Child : C, G, J, …

1. Full Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap sub tree harus mempunyai panjang path yang sama.

2. Complete Binary Tree

Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

3. Skewed Binary Tree

Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

4. Deklarasi Tree

Tree tersusun oleh node-node, maka yang perlu kita deklarasikan adalah komponen node itu sendiri. Dalam contoh dibawah, akan kita namai Node. Sebelumnya perlu kita lihat bahwa untuk mewujudkan implementasi node ke dalam bahasa pemrograman, diperlukan sebuah struktur yang memiliki susunan berikut ini:

struct Node
{
int data;
Node *kiri;
Node *kanan;
};

5. Inisialisasi Tree

Saat pertama membuat sebuah pohon biner, asumsi awal adalah pohon itu belum bertumbuh, belum memiliki node sama sekali, sehingga masih kosong. Oleh karena itu perlu kita tambahkan kode berikut pada baris awal fungsi Main:

Node *pohon;
pohon = NULL;

6. Menambah Node pada Tree

Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti aturan penambahan node pada pohon biner:

Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.
Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses pengecekan berikut:

Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

Proses penambahan ini diimplementasikan secara rekursif pada fungsi berikut:

void tambah(Node **root,int databaru)
{
if((*root) == NULL)
{
Node *baru;
baru = new Node;
baru->data = databaru;
baru->kiri = NULL;
baru->kanan = NULL;
(*root) = baru;
(*root)->kiri = NULL;
(*root)->kanan = NULL;
cout<<"Data bertambah!";
getch();
}
else
if(databaru < (*root)->data)
tambah(&(*root)->kiri,databaru);
else
if(databaru > (*root)->data)
tambah(&(*root)->kanan,databaru);
else
if(databaru == (*root)->data)
{ cout<<"Data sudah ada!";
getch();
}
}

Variabel **root menunjukkan node mana yang sedang dicek saat ini, untuk itu saat pemanggilan fungsi ini, variabel **root kita beri nilai pointer yang menunjuk ke node akar, yaitu pohon.

tambah(&pohon,data);

7. Membaca dan Menampilkan data pada Tree/Traverse

PreOrder: cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan:

1. Cetak isi (data) node yang sedang dikunjungi

2. Kunjungi kiri node tersebut,

Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.
Jika kiri kosong (NULL), lanjut ke langkah ketiga.

3. Kunjungi kanan node tersebut,

Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.
Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

void preOrder(Node *root)
{
if(root != NULL)
{
cout<<root->data<<" ";
preOrder(root->kiri);
preOrder(root->kanan);
}
}

InOrder: kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right Child.

1. Kunjungi kiri node tersebut,

Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.
Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Cetak isi (data) node yang sedang dikunjungi

3. Kunjungi kanan node tersebut,

Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.
Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

void inOrder(Node *root)
{
if(root != NULL)
{
inOrder(root->kiri);
cout<<root->data<<" ";
inOrder(root->kanan);
}
}

PostOrder: kunjungi Left Child, kunjungi Right Child, cetak isi node yang dikunjungi.

1. Kunjungi kiri node tersebut,

Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.
Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Kunjungi kanan node tersebut,

Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.
Jika kanan kosong (NULL), lanjut ke langkah ketiga.

3. Cetak isi (data) node yang sedang dikunjungi. Proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

void postOrder(Node *root)
{
if(root != NULL)
{
postOrder(root->kiri);
postOrder(root->kanan);
cout<<root->data<<" ";
}
}

Program Lengkap

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
struct Node
{
int data;
Node *kiri;
Node *kanan;
};
void tambah(Node **root,int databaru)
{
if((*root) == NULL)
{
Node *baru;
baru = new Node;
baru->data = databaru;
baru->kiri = NULL;
baru->kanan = NULL;
(*root) = baru;
(*root)->kiri = NULL;
(*root)->kanan = NULL;
cout<<"Data bertambah!";
getch();
}
else
if(databaru < (*root)->data)
tambah(&(*root)->kiri,databaru);
else
if(databaru > (*root)->data)
tambah(&(*root)->kanan,databaru);
else
if(databaru == (*root)->data)
{ cout<<"Data sudah ada!";
getch();
}
}
void preOrder(Node *root)
{
if(root != NULL)
{
cout<<root->data<<" ";
preOrder(root->kiri);
preOrder(root->kanan);
}
}
void inOrder(Node *root)
{
if(root != NULL)
{
inOrder(root->kiri);
cout<<root->data<<" ";
inOrder(root->kanan);
}
}
void postOrder(Node *root)
{
if(root != NULL)
{
postOrder(root->kiri);
postOrder(root->kanan);
cout<<root->data<<" ";
}
}
void main()
{
int data;
Node *pohon;
pohon = NULL;
char pil;
do
{
clrscr();
cout<<"1. Tambah\n";
cout<<"2. Lihat Pre-order\n";
cout<<"3. Lihat In-order\n";
cout<<"4. Lihat Post-order\n";
cout<<"5. Keluar\n";
cout<<"Masukkan pilihan anda (1-5) : ";
cin>>pil;
if(pil!='1' && pil !='2' && pil !='3' && pil!='4' && pil!='5' )
cout<<"\n\nAnda salah pilih...\n";
else
{
if(pil=='1')
{
cout<<"\n";
cout<<"\nData baru : ";
cin>>data;
tambah(&pohon,data);
}
else
{
if(pil=='2')
{
cout<<"\n";
if(pohon!=NULL)
preOrder(pohon);
else
cout<<"Masih kosong!";
getch();
}
else
{
if(pil=='3')
{
cout<<"\n";
if(pohon!=NULL)
inOrder(pohon);
else
cout<<"Masih kosong!";
getch();
}
else
{
if(pil=='4')
{
cout<<"\n";
if(pohon!=NULL)
postOrder(pohon);
else
cout<<"Masih kosong!";
getch();
}
}
}
}
}
}
while(pil!='5');
}

void BinaryTree::remove(int d)
{
//Tempat element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
tree_node* curr;
tree_node* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}
// 3 pilihan :
// 1. Kita bisa menghapus cabang node (leaf node)
// 2. Kita bisa menghapus sebuah node dengan satu anaknya
// 3. Kita bisa menghilangkan sebuah node dengan dua anaknya
// Node dengan satu anaknya (cabang dari induknya)
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // untuk cabang bagian kiri, bukan untuk cabang bagian kanan
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;

}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}
//Kita bisa melihat pada pohon node (leaf node)
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
delete curr;
return;
}
//Node dengan dua anaknya (cabang dari induknya)
// mengganti atau menempatkan lagi dengan nilai terkecil pada anak pohon bagian kanan
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // anak bagian kanan merupakan anak-anak dari induknnya (children)
{
//jika anak kanan node merupakan anak bagian kiri
//memindahkan semua bagian bawah cabang ke tempat element terkecil
if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}
}
return;
}
}

Sumber

Mata kuliah Struktur Data. STMIK EL Rahma Yogyakarta.
Disusun oleh Eko Riswanto