Tree merupakan salah satu
bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat
hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan
sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan
node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang
tidak mengandung loop.
Sebuah binary
search tree (bst) adalah sebuah pohon biner yang boleh kosong, dan setiap
nodenya harus memiliki identifier/value. Value pada semua node subpohon sebelah
kiiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon
di sebelah kanan adalah sama atau lebih besar dari value pada root,
masing-masing subpohon tersebut (kiri dan kanan) itu sendiri adalah juga binary
search tree.
Struktur data
bst sangat penting dalam struktur pencarian, misalkan dalam kasus pencarian
dalam
sebuah list,
jika list sudah dalam keadaan terurut maka proses pencarian akan semakin cepat,
jika kita menggunakan list contigue dan melakukan pencarian
biner,akan tetapi jika kita ingin melakukan perubahan isi list
(insert atau delete), menggunakan list contigue akan sangat lambat, karena
prose insert dan delete dalam list contigue butuh memindahkan linked-list, yang
untuk operasi insert atau delete tinggal mengatur- atur pointer,akan tetapi
pada n-linked list, kita tidak bisa melakukan pointer sembarangan setiap saat,
kecuali hanya satu kali dengan kata lain hanya secara squential.
dibawah akan diuraikan
istilah-istilah dalam tree :
a) Prodecessor :
node yang berada diatas node tertentu.b) Successor : node yang berada
di bawah node tertentu.c) Ancestor : seluruh node yang terletak sebelum node tertentu dan
terletak pada jalur yang sama.d) Descendant :
seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang
sama.e) Parent : predecssor satu level di atas suatu node.f) Child :
successor satu level di bawah suatu node.g) Sibling : node-node yang
memiliki parent yang sama dengan suatu node.h) Subtree :
bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki
semua karakteristik dari tree
tersebut.i) Size : banyaknya node dalam suatu tree.j) Height :
banyaknya tingkatan/level dalam suatu tree.k) Root :
satu-satunya node khusus dalam tree yang tak punya predecssor.l) Leaf :
node-node dalam tree yang tak memiliki seccessor.m) Degree :
banyaknya child yang dimiliki suatu node.
Beberapa jenis
tree yang memiliki sifat khusus :
1) Binary Tree
Binary Tree adalah tree dengan
syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua
subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka
tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.
2) Binary Search
Tree
Binary Tree
dengan sifat bahwa semua left child harus lebih kecil daripada right child dan
parentnya. Juga semua right child harus lebih besar dari left child serta
parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree
biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary
tree.
#include <iostream>
#include <cstdlib>
using namespace std;
class BinaryTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;
public:
BinaryTree()
{
root = NULL;
}
bool isEmpty() const { return
root==NULL; }
void print_inorder();
void inorder(tree_node*);
void print_preorder();
void preorder(tree_node*);
void print_postorder();
void postorder(tree_node*);
void insert(int);
void remove(int);
};
// element yang lebih kecil ke kiri
// element yang lebih besar ke kanan
void BinaryTree::insert(int d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// merupakan pohon baru (new tree)
if(isEmpty()) root = t;
else
{
//Catatan: Semua yang dimasukkan
adalah sebagai cabang pohon node
tree_node* curr;
curr = root;
// Mencari induknya node
while(curr)
{
parent = curr;
if(t->data >
curr->data) curr = curr->right;
else curr =
curr->left;
}
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
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;
}
}
void BinaryTree::print_inorder()
{
inorder(root);
}
void BinaryTree::inorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<"
"<<p->data<<" ";
if(p->right) inorder(p->right);
}
else return;
}
void BinaryTree::print_preorder()
{
preorder(root);
}
void BinaryTree::preorder(tree_node* p)
{
if(p != NULL)
{
cout<<"
"<<p->data<<" ";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}
void BinaryTree::print_postorder()
{
postorder(root);
}
void BinaryTree::postorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right)
postorder(p->right);
cout<<"
"<<p->data<<" ";
}
else return;
}
int main()
{
BinaryTree b;
int ch,tmp,tmp1;
while(1)
{
cout<<"\n\t\a\a1---Masukan Node Di
Sepasang Pohon (Binary Tree)\a\a";
cout<<"\n\t\a\a2---In-Order
Traversal
\a\a";
cout<<"\n\t\a\a3---Pre-Order
Traversal
\a\a";
cout<<"\n\t\a\a4---Post-Order
Traversal
\a\a";
cout<<"\n\t\a\a5---Delete
\a\a";
cout<<"\n\t\a\a6---Exit
\a\a";
cout<<"\n";
cout<<"\n";
cout<<"
Masukkan pilihanmu : ";
cin>>ch;
switch(ch)
{
case 1 :
cout<<" Masukkan Node Di Sepasang Pohon (Binary Tree) : ";
cin>>tmp;
b.insert(tmp);
break;
case 2 :
cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_inorder();
break;
case 3 :
cout<<endl;
cout<<" Pre-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_preorder();
break;
case 4 :
cout<<endl;
cout<<" Post-Order Traversal "<<endl;
cout<<" --------------------"<<endl;
b.print_postorder();
break;
case 5 :
cout<<" Masukkan data yang dihapus : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 6 :
return 0;
}
}
}
