Home > Ren's Free Time > Binary Tree dengan C++

Binary Tree dengan C++

November 18, 2010 Leave a comment Go to comments

Salah satu jenis struktur data yang cukup populer adalah Binary Tree atau Pohon Biner. Menurut saya Binary Tree mempunyai kemampuan / efisiensi yang sama baik dengan binary search dalam hal searching. Tapi lebih baik dalam hal insert, delete dan traversal daripada binary search. Karena alokasi memory dari Binary Tree dinamis sedangkan alokasi binary search statis karena menggunakan array. Agar suatu struktur data tree dapat disebut dengan Binary Tree harus dipenuhi syarat sebagai berikut :

  • Setiap node / impul maksimal mempunyai dua sub-node
  • Nilai pada node sebelah kiri lebih kecil dari pada node disebelah kanan

Berikut ini code untuk Binary Tree dalam bahasa C++ dengan tool yang digunakan CodeBlock 8.02

#include <iostream>
#include <cstdlib>
using namespace std;

class BinarySearchTree
{
private:
struct nodeTree
{
nodeTree* left;
nodeTree* right;
int data;
};
nodeTree* root;

public:
BinarySearchTree()
{
root = NULL;
}

bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(nodeTree*);
void print_preorder();
void preorder(nodeTree*);
void print_postorder();
void postorder(nodeTree*);
void insert(int);
void remove(int);
};

void BinarySearchTree::insert(int d)
{
nodeTree* t = new nodeTree;
nodeTree* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;

if(isEmpty()) root = t;
else
{

nodeTree* current;
current = root;

while(current)
{
parent = current;
if(t->data > current->data) current = current->right;
else current = current->left;
}

if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}

void BinarySearchTree::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}

nodeTree* current;
nodeTree* parent;
current = root;

while(current != NULL)
{
if(current->data == d)
{
found = true;
break;
}
else
{
parent = current;
if(d>current->data) current = current->right;
else current = current->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}

// Node dengan single child
if((current->left == NULL && current->right != NULL)|| (current->left != NULL
&& current->right == NULL))
{
if(current->left == NULL && current->right != NULL)
{
if(parent->left == current)
{
parent->left = current->right;
delete current;
}
else
{
parent->right = current->right;
delete current;
}
}
else
{
if(parent->left == current)
{
parent->left = current->left;
delete current;
}
else
{
parent->right = current->left;
delete current;
}
}
return;
}

// node tidak mempunyai child node
if( current->left == NULL && current->right == NULL)
{
if(parent->left == current ) parent->left = NULL;
else parent->right = NULL;
delete current;
return;
}

//Node dengan 2 child node
// ganti node dengan nilai terkecil di subtree bagain kanan
if (current->left != NULL && current->right != NULL)
{
nodeTree* temp;
temp = current->right;
if((temp->left == NULL) && (temp->right == NULL))
{
current = temp;
delete temp;
current->right = NULL;
}
else
{

if((current->right)->left != NULL)
{
nodeTree* lcurrent;
nodeTree* lcurrp;
lcurrp = current->right;
lcurrent = (current->right)->left;
while(lcurrent->left != NULL)
{
lcurrp = lcurrent;
lcurrent = lcurrent->left;
}
current->data = lcurrent->data;
delete lcurrent;
lcurrp->left = NULL;
}
else
{
nodeTree* tmp2;
tmp2 = current->right;
current->data = tmp2->data;
current->right = tmp2->right;
delete tmp2;
}

}
return;
}

}

void BinarySearchTree::print_inorder()
{
inorder(root);
}

void BinarySearchTree::inorder(nodeTree* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if(p->right) inorder(p->right);
}
else return;
}

void BinarySearchTree::print_preorder()
{
preorder(root);
}

void BinarySearchTree::preorder(nodeTree* p)
{
if(p != NULL)
{
cout<<" "<<p->data<<" ";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}

void BinarySearchTree::print_postorder()
{
postorder(root);
}

void BinarySearchTree::postorder(nodeTree* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<" "<<p->data<<" ";
}
else return;
}

int main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. In-Order Traversal "<<endl;
cout<<" 3. Pre-Order Traversal "<<endl;
cout<<" 4. Post-Order Traversal "<<endl;
cout<<" 5. Removal "<<endl;
cout<<" 6. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Enter Number to be inserted : ";
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<<" Enter data to be deleted : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 6 :
return 0;

}
}
}

dengan referensi dari berbagai sumber. baik kode maupun materi tentang Binary Tree

Semoga membantušŸ˜€

  1. trisna
    December 28, 2010 at 09:35

    kalo kta mau sorting di linklis gimana? cara masukinnya ke node?

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: