Tree traversal adalah cara kunjungan node-node pada pohon biner. Ada tiga cara
kunjungan dalam tree:
• Pre-order
• In-order
• Post-order
1. Pre-order
a. Cetak data pada root
b. Secara rekursif mencetak seluruh data pada subpohon kiri
c. Secara rekursif mencetak seluruh data pada subpohon kanan
2. In-order
a. Secara rekursif mencetak seluruh data pada subpohon kiri
b. Cetak data pada root
c. Secara rekursif mencetak seluruh data pada subpohon kanan
3. Post-order
a. Secara rekursif mencetak seluruh data pada subpohon kiri
b. Secara rekursif mencetak seluruh data pada subpohon kanan
c. Cetak data pada root
Contoh program tree lenjutan:
#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;
}
}
}
Selamat mencoba!!
READ MORE
kunjungan dalam tree:
• Pre-order
• In-order
• Post-order
1. Pre-order
a. Cetak data pada root
b. Secara rekursif mencetak seluruh data pada subpohon kiri
c. Secara rekursif mencetak seluruh data pada subpohon kanan
2. In-order
a. Secara rekursif mencetak seluruh data pada subpohon kiri
b. Cetak data pada root
c. Secara rekursif mencetak seluruh data pada subpohon kanan
3. Post-order
a. Secara rekursif mencetak seluruh data pada subpohon kiri
b. Secara rekursif mencetak seluruh data pada subpohon kanan
c. Cetak data pada root
Contoh program tree lenjutan:
#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;
}
}
}
Selamat mencoba!!
Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon. Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah. Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.
Contoh program tree:
READ MORE
Contoh program 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;
}
}
}
Good luck!!!#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;
}
}
}
Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri. Fungsi ini akan terus berjalan sampai kondisi berhenti terpenuhi, oleh karena itu dalam sebuah fungsi rekursif perlu terdapat 2 blok penting, yaitu blok yang menjadi titik berhenti dari sebuah proses rekursi dan blok yang memanggil dirinya sendiri.
Contoh program rekursif:
1. Rekursif pembalik kata
#include<stdio.h>
#define MAX 100
void rekursif_angka_terbalik(int);
main()
{
int i,j,jml=0;
char bil[MAX];
printf("\n=======================");
printf("\n=NAMA : MAHFUZ =");
printf("\n=NIM : 100533405403=");
printf("\n=KELAS : PTI '10 B =");
printf("\n=======================");
printf("\n");
printf("\n^_^Program Pembalik Angka^_^");
printf("\n");
printf("\nMasukkan bilangan yang akan dibalik kawan= ");
gets(bil);
for (i=0;bil[i];i++)
jml=jml++;
printf("\n");
printf("Maka hasilnya adalah= ");
for(j=jml-1;j>=0;j--)
printf("%c",bil[j]);
printf("\n");
}
2. Rekursif rumus bangun ruang
READ MORE
Contoh program rekursif:
1. Rekursif pembalik kata
#include<stdio.h>
#define MAX 100
void rekursif_angka_terbalik(int);
main()
{
int i,j,jml=0;
char bil[MAX];
printf("\n=======================");
printf("\n=NAMA : MAHFUZ =");
printf("\n=NIM : 100533405403=");
printf("\n=KELAS : PTI '10 B =");
printf("\n=======================");
printf("\n");
printf("\n^_^Program Pembalik Angka^_^");
printf("\n");
printf("\nMasukkan bilangan yang akan dibalik kawan= ");
gets(bil);
for (i=0;bil[i];i++)
jml=jml++;
printf("\n");
printf("Maka hasilnya adalah= ");
for(j=jml-1;j>=0;j--)
printf("%c",bil[j]);
printf("\n");
}
2. Rekursif rumus bangun ruang
#include <iostream.h>
#include <conio.h>
void main()
{
int pilihan;
float Lsegitiga,Ksegitiga,Lpersegi,Kpersegi,Lpersegipanjang,Kpersegipanjang,Llingkaran,Klingkaran,Vkubus,LPkubus,Vbalok,LPbalok,Vbola,LPbola,Vlimassegiempat,LPlimassegiempat,Vtabung,LPtabung ;
float a, t, s, p, l, r, phi,sAB,sBC,sCA;
char ulang;
do
{
cout<<"(c) Created 2009 by dsuryanta.Inc"<<endl<<endl;
cout<<"Menu Utama"<<endl;
cout<<"1. Menghitung Luas & Keliling Segitiga"<<endl;
cout<<"2. Menghitung Luas & Keliling Bujursangkar"<<endl;
cout<<"3. Menghitung Luas & Keliling Persegipanjang"<<endl;
cout<<"4. Menghitung Luas & Keliling Lingkaran"<<endl;
cout<<"5. Menghitung Volum & Luas Permukaan Kubus"<<endl;
cout<<"6. Menghitung Volum & Luas Permukaan Balok"<<endl;
cout<<"7. Menghitung Volum & Luas Permukaan Bola"<<endl;
cout<<"8. Menghitung Volum & Luas Permukaan Limas Segi Empat"<<endl;
cout<<"9. Menghitung Volum & Luas Permukaan Tabung"<<endl;
cout<<"10. Exit"<<endl;
cout<<endl<<endl;
cout<<"Pilihan anda : ";cin>>pilihan;
switch (pilihan)
{
case 1 :
cout<<"Menghitung Luas Segitiga"<<endl;
cout<<"Menghitung Keliling Segitiga"<<endl;
cout<<"Masukkan alas segitiga : ";cin>>a;
cout<<"Masukkan tinggi segitiga : ";cin>>t;
cout<<"Masukkan sisi AB segitiga : ";cin>>sAB;
cout<<"Masukkan sisi BC segitiga : ";cin>>sBC;
cout<<"Masukkan sisi CA segitiga : ";cin>>sCA;
Lsegitiga = 0.5*a*t;
Ksegitiga = sAB+sBC+sCA;
cout<<"Luas segitiga adalah : "<<Lsegitiga<<endl;
cout<<"Keliling segitiga adalah : "<<Ksegitiga<<endl;
break;
case 2 :
cout<<"Menghitung Luas Bujursangkar"<<endl;
cout<<"Menghitung Keliling Bujursangkar"<<endl;
cout<<"Masukkan sisi persegi : ";cin>>s;
Lpersegi = s*s;
Kpersegi = 4*s;
cout<<"Luas bujursangkar : "<<Lpersegi<<endl;
cout<<"Keliling bujursangkar : "<<Kpersegi<<endl;
break;
case 3 :
cout<<"Menghitung Luas Persegipanjang"<<endl;
cout<<"Menghitung Keliling Persegipanjang"<<endl;
cout<<"Masukkan panjang : ";cin>>p;
cout<<"Masukkan lebar : ";cin>>l;
Lpersegipanjang = p*l;
Kpersegipanjang = (p+l)*2;
cout<<"Luas Persegipnjng: "<<Lpersegipanjang<<endl;
cout<<"Keliling Persegipnjng: "<<Kpersegipanjang<<endl;
break;
case 4 :
cout<<"Menghitung Luas Lingkaran"<<endl;
cout<<"Menghitung Keliling Lingkaran"<<endl;
cout<<"Masukkan jari-jari lingkaran : ";cin>>r;
phi = 3.14;
Llingkaran = phi*r*r;
Klingkaran = phi*(r+r);
cout<<"Luas lingkaran adalah : "<<Llingkaran<<endl;
cout<<"Keliling lingkaran adalah : "<<Klingkaran<<endl;
break;
case 5 :
cout<<"Menghitung Volum Kubus"<<endl;
cout<<"Menghitung Luas Permukaan Kubus"<<endl;
cout<<"Masukkan sisi kubus : ";cin>>s;
Vkubus = s*s*s;
LPkubus = 6*s;
cout<<"Volum kubus adalah : "<<Vkubus<<endl;
cout<<"Luas permukaan kubus adalah : "<<LPkubus<<endl;
break;
case 6 :
cout<<"Menghitung Volum Balok"<<endl;
cout<<"Menghitung Luas Permukaan Balok"<<endl;
cout<<"Masukkan panjang balok : ";cin>>p;
cout<<"Masukkan lebar balok : ";cin>>l;
cout<<"Masukkan tinggi balok : ";cin>>t;
Vbalok = p*l*t;
LPbalok = (2*p*l)+(2*p*t)+(2*l*t);
cout<<"Volum balok adalah : "<<Vbalok<<endl;
cout<<"Luas permukaan balok adalah : "<<LPbalok<<endl;
break;
case 7 :
cout<<"Menghitung Volum Bola"<<endl;
cout<<"Menghitung Luas Permukaan Bola"<<endl;
cout<<"Masukkan jari jari bola : ";cin>>r;
cout<<"Masukkan tinggi bola : ";cin>>t;
phi = 3.14;
Vbola = 4/3*phi*r*t*t*t;
LPbola = 4*phi*r*r;
cout<<"Volum bola adalah : "<<Vbola<<endl;
cout<<"Luas permukaan bola adalah : "<<LPbola<<endl;
break;
case 8 :
cout<<"Menghitung Volum Limas Segi Empat"<<endl;
cout<<"Menghitung Luas Permukaan Limas Segi Empat"<<endl;
cout<<"Masukkan panjang limas segi empat : ";cin>>p;
cout<<"Masukkan lebar limas segi empat : ";cin>>l;
cout<<"Masukkan tinggi limas segi empat : ";cin>>t;
Vlimassegiempat = (p*l*t)*1/3;
LPlimassegiempat = ((p+l)*t)+(p*l);
cout<<"Volum limas segi empat adalah : "<<Vlimassegiempat<<endl;
cout<<"Luas permukaan limas segi empat adalah : "<<LPlimassegiempat<<endl;
break;
case 9 :
cout<<"Menghitung Volum Tabung"<<endl;
cout<<"Menghitung Luas Permukaan Tabung"<<endl;
cout<<"Masukkan jari jari tabung : ";cin>>r;
cout<<"Masukkan tinggi tabung : ";cin>>t;
phi = 3.14;
Vtabung = phi*r*r*t;
LPtabung = (2*phi*r)*(r*t);
cout<<"Volum tabung adalah : "<<Vtabung<<endl;
cout<<"Luas permukaan tabung adalah : "<<LPtabung<<endl;
break;
case 10 :
cout<<"Exitâ?¦"<<endl;
break;
default:
cout<<"Menu tidak tersediaâ?¦"<<endl;
break;
}
cout<<"Kembali ke Menu Utama (y/n)?";cin>>ulang;
}while(ulang == 'y');
}
#include <conio.h>
void main()
{
int pilihan;
float Lsegitiga,Ksegitiga,Lpersegi,Kpersegi,Lpersegipanjang,Kpersegipanjang,Llingkaran,Klingkaran,Vkubus,LPkubus,Vbalok,LPbalok,Vbola,LPbola,Vlimassegiempat,LPlimassegiempat,Vtabung,LPtabung ;
float a, t, s, p, l, r, phi,sAB,sBC,sCA;
char ulang;
do
{
cout<<"(c) Created 2009 by dsuryanta.Inc"<<endl<<endl;
cout<<"Menu Utama"<<endl;
cout<<"1. Menghitung Luas & Keliling Segitiga"<<endl;
cout<<"2. Menghitung Luas & Keliling Bujursangkar"<<endl;
cout<<"3. Menghitung Luas & Keliling Persegipanjang"<<endl;
cout<<"4. Menghitung Luas & Keliling Lingkaran"<<endl;
cout<<"5. Menghitung Volum & Luas Permukaan Kubus"<<endl;
cout<<"6. Menghitung Volum & Luas Permukaan Balok"<<endl;
cout<<"7. Menghitung Volum & Luas Permukaan Bola"<<endl;
cout<<"8. Menghitung Volum & Luas Permukaan Limas Segi Empat"<<endl;
cout<<"9. Menghitung Volum & Luas Permukaan Tabung"<<endl;
cout<<"10. Exit"<<endl;
cout<<endl<<endl;
cout<<"Pilihan anda : ";cin>>pilihan;
switch (pilihan)
{
case 1 :
cout<<"Menghitung Luas Segitiga"<<endl;
cout<<"Menghitung Keliling Segitiga"<<endl;
cout<<"Masukkan alas segitiga : ";cin>>a;
cout<<"Masukkan tinggi segitiga : ";cin>>t;
cout<<"Masukkan sisi AB segitiga : ";cin>>sAB;
cout<<"Masukkan sisi BC segitiga : ";cin>>sBC;
cout<<"Masukkan sisi CA segitiga : ";cin>>sCA;
Lsegitiga = 0.5*a*t;
Ksegitiga = sAB+sBC+sCA;
cout<<"Luas segitiga adalah : "<<Lsegitiga<<endl;
cout<<"Keliling segitiga adalah : "<<Ksegitiga<<endl;
break;
case 2 :
cout<<"Menghitung Luas Bujursangkar"<<endl;
cout<<"Menghitung Keliling Bujursangkar"<<endl;
cout<<"Masukkan sisi persegi : ";cin>>s;
Lpersegi = s*s;
Kpersegi = 4*s;
cout<<"Luas bujursangkar : "<<Lpersegi<<endl;
cout<<"Keliling bujursangkar : "<<Kpersegi<<endl;
break;
case 3 :
cout<<"Menghitung Luas Persegipanjang"<<endl;
cout<<"Menghitung Keliling Persegipanjang"<<endl;
cout<<"Masukkan panjang : ";cin>>p;
cout<<"Masukkan lebar : ";cin>>l;
Lpersegipanjang = p*l;
Kpersegipanjang = (p+l)*2;
cout<<"Luas Persegipnjng: "<<Lpersegipanjang<<endl;
cout<<"Keliling Persegipnjng: "<<Kpersegipanjang<<endl;
break;
case 4 :
cout<<"Menghitung Luas Lingkaran"<<endl;
cout<<"Menghitung Keliling Lingkaran"<<endl;
cout<<"Masukkan jari-jari lingkaran : ";cin>>r;
phi = 3.14;
Llingkaran = phi*r*r;
Klingkaran = phi*(r+r);
cout<<"Luas lingkaran adalah : "<<Llingkaran<<endl;
cout<<"Keliling lingkaran adalah : "<<Klingkaran<<endl;
break;
case 5 :
cout<<"Menghitung Volum Kubus"<<endl;
cout<<"Menghitung Luas Permukaan Kubus"<<endl;
cout<<"Masukkan sisi kubus : ";cin>>s;
Vkubus = s*s*s;
LPkubus = 6*s;
cout<<"Volum kubus adalah : "<<Vkubus<<endl;
cout<<"Luas permukaan kubus adalah : "<<LPkubus<<endl;
break;
case 6 :
cout<<"Menghitung Volum Balok"<<endl;
cout<<"Menghitung Luas Permukaan Balok"<<endl;
cout<<"Masukkan panjang balok : ";cin>>p;
cout<<"Masukkan lebar balok : ";cin>>l;
cout<<"Masukkan tinggi balok : ";cin>>t;
Vbalok = p*l*t;
LPbalok = (2*p*l)+(2*p*t)+(2*l*t);
cout<<"Volum balok adalah : "<<Vbalok<<endl;
cout<<"Luas permukaan balok adalah : "<<LPbalok<<endl;
break;
case 7 :
cout<<"Menghitung Volum Bola"<<endl;
cout<<"Menghitung Luas Permukaan Bola"<<endl;
cout<<"Masukkan jari jari bola : ";cin>>r;
cout<<"Masukkan tinggi bola : ";cin>>t;
phi = 3.14;
Vbola = 4/3*phi*r*t*t*t;
LPbola = 4*phi*r*r;
cout<<"Volum bola adalah : "<<Vbola<<endl;
cout<<"Luas permukaan bola adalah : "<<LPbola<<endl;
break;
case 8 :
cout<<"Menghitung Volum Limas Segi Empat"<<endl;
cout<<"Menghitung Luas Permukaan Limas Segi Empat"<<endl;
cout<<"Masukkan panjang limas segi empat : ";cin>>p;
cout<<"Masukkan lebar limas segi empat : ";cin>>l;
cout<<"Masukkan tinggi limas segi empat : ";cin>>t;
Vlimassegiempat = (p*l*t)*1/3;
LPlimassegiempat = ((p+l)*t)+(p*l);
cout<<"Volum limas segi empat adalah : "<<Vlimassegiempat<<endl;
cout<<"Luas permukaan limas segi empat adalah : "<<LPlimassegiempat<<endl;
break;
case 9 :
cout<<"Menghitung Volum Tabung"<<endl;
cout<<"Menghitung Luas Permukaan Tabung"<<endl;
cout<<"Masukkan jari jari tabung : ";cin>>r;
cout<<"Masukkan tinggi tabung : ";cin>>t;
phi = 3.14;
Vtabung = phi*r*r*t;
LPtabung = (2*phi*r)*(r*t);
cout<<"Volum tabung adalah : "<<Vtabung<<endl;
cout<<"Luas permukaan tabung adalah : "<<LPtabung<<endl;
break;
case 10 :
cout<<"Exitâ?¦"<<endl;
break;
default:
cout<<"Menu tidak tersediaâ?¦"<<endl;
break;
}
cout<<"Kembali ke Menu Utama (y/n)?";cin>>ulang;
}while(ulang == 'y');
}
3. Rekursif segitiga siku-siku terbalik
#include <iostream>
#include <conio.h>
#include <stdio.h>
using namespace std;
void rekursif(int argc, char *argv[])
{
int t,y,x;
cout << "Masukkan tinggi segitiga : ";
cin >> t;
cout << "----------------------------\n";
for(y=1;y<=t;y++)
{
cout<<" ";
for(x=1;x<=y;x++)
{
cout << "*";
}
cout << " " << endl;
}
cout<<endl<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
#include <conio.h>
#include <stdio.h>
using namespace std;
void rekursif(int argc, char *argv[])
{
int t,y,x;
cout << "Masukkan tinggi segitiga : ";
cin >> t;
cout << "----------------------------\n";
for(y=1;y<=t;y++)
{
cout<<" ";
for(x=1;x<=y;x++)
{
cout << "*";
}
cout << " " << endl;
}
cout<<endl<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
4. Rekursif menetukan nilai segitiga
#include <stdio.h>
#include <conio.h>
int main(){
int i,j,
sudut[3];
for (i=0;i<3;i++){
printf("Sudut ke - %d : ",i+1);
scanf("%d",&sudut[i]);
}
int sum;
bool samaKaki = false;
for (i=0;i<3;i++){
sum = 0;
for (j=0;j<3;j++){
if (j != i) {
sum += sudut[j];
}
}
if (sudut[i] == sum){
printf("Segitiga Sama Kaki");
samaKaki = true;
}
}
if (! samaKaki){
printf("Bukan segitiga sama kaki");
}
getch();
return 0;
}
#include <conio.h>
int main(){
int i,j,
sudut[3];
for (i=0;i<3;i++){
printf("Sudut ke - %d : ",i+1);
scanf("%d",&sudut[i]);
}
int sum;
bool samaKaki = false;
for (i=0;i<3;i++){
sum = 0;
for (j=0;j<3;j++){
if (j != i) {
sum += sudut[j];
}
}
if (sudut[i] == sum){
printf("Segitiga Sama Kaki");
samaKaki = true;
}
}
if (! samaKaki){
printf("Bukan segitiga sama kaki");
}
getch();
return 0;
}
Semoga bermanfaat!!
Salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara sekuensial, saling bersambungan, dinamis dan terbatas adalah senarai berkait (linked list). Suatu senarai berkait (linked list) adalah suatu simpul (node) yang dikaitkan dengan simpul yang lain dalam suatu urutan tertentu. Suatu simpul dapat berbentuk suatu struktur atau class. Simpul harus mempunyai satu atau lebih elemen struktur atau class yang berisi data.
Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Dikatakan single (singly) linked apabila hanya ada satu pointer yang menghubungkan setiap node. single artinya field pointer-nya hanya satu buah saja dan satu arah.
Contoh program Linked List:
#include <iostream>
#include <stdlib.h>
using namespace std;
// Node Class
class Node
{
private:
int data;
Node *pNext;
Node *pPrevious;
public:
Node(int d):data(d),pNext(NULL),pPrevious(NULL){}
int getData()const{return data;}
void setData(int d){data=d;}
Node * getNext()const{return pNext;}
void setNext(Node *p){pNext=p;}
Node * getPrevious()const {return pPrevious;}
void setPrevious(Node *p){pPrevious=p;}
};
// LinkedList class
class LinkedList
{
protected:
Node *pHead; //penunjuk (pointer) untuk node awal
Node *pTail; //penunjuk (pointer) untuk node terakhir
int nodeCounter; //menghitung jumlah angka pada node
Node * makeNode(int data); // membuat dan menukar node baru.
void remove(Node *tmp); // menghilangkan node dari data yang dihubungkan (linked list).
public:
LinkedList();
~LinkedList();
// pengoperasian
void addFirst(int data);
void addLast(int data);
void addBefore(int index,int data);
void removeFirst();
void removeLast();
void displayInOrder()const;
void displayInReverseOrder()const;
void destroyList();
int getSize()const{return nodeCounter;}
};
LinkedList::LinkedList():
pHead(NULL),pTail(NULL),nodeCounter(0)
{}
LinkedList::~LinkedList()
{
destroyList();
}
void LinkedList::displayInOrder()const
{
if( !pHead )
{
cout<<"\nNULL";
return ;
}
for(Node *cur=pHead;cur!=NULL;cur=cur->getNext())
cout<<cur->getData()<<" -> ";
cout<<"NULL"<<endl;
}
void LinkedList::displayInReverseOrder()const
{
if( !pHead )
{
cout<<"\nNULL";
return ;
}
for(Node *cur=pTail;cur!=NULL;cur=cur->getPrevious())
cout<<cur->getData()<<" -> ";
cout<<"NULL"<<endl;
}
Node * LinkedList::makeNode(int data)
{
nodeCounter++;
return new Node(data);
}
void LinkedList::addFirst(int data)
{
// membuat node baru
Node *pNew=makeNode(data); //membuat node baru sebagai node partama atau awal pada data yang dihubungkan (linked list).
if( !pHead ) // jika data yang dihubungkan atau yang dimasukkan tersebut kosong.
pHead=pTail=pNew;
else // jika terdapat beberapa node.
{
pNew->setNext(pHead);
pHead->setPrevious(pNew);
pHead=pNew;
}
}
void LinkedList::addLast(int data)
{
// membuat node baru
Node *pNew=makeNode(data);
// membuat node baru sebagai node terakhir pada data yang dihubungkan (linked list).
//jika pada kondisi tidak terdapat node pada data yang dihubungkan (linked list), maka ditambah node lagi.
//cara lain untuk memindahkan sebuah node baru ke tempat node yang terakhir.
if( !pHead )
pHead=pTail=pNew;
else
{
pTail->setNext(pNew);
pNew->setPrevious(pTail);
pTail=pNew;
}
}
void LinkedList::addBefore(int index,int data)
{
// mengecek atau memeriksa index untuk mengetahui apakah data yang dimasukkan sesuai atau tidak.
if( index <1 || index > getSize() )
{
cerr<<"\nError: index is too hight/low ";
return;
}
if(index == 1)
{
addFirst(data);
return ;
}
// Membuat node baru
Node *pNew=makeNode(data);
Node *pCur=pHead;
for(int i=1;i<index -1;i++,pCur=pCur->getNext());
pNew->setNext(pCur->getNext());
pCur->setNext(pNew);
}
void LinkedList::removeFirst()
{
if( !pHead )
{
cerr<<"\nTidak ada node yang akan dihilangkan!!";
return ;
}
Node *pTmp=pHead;
pHead=pHead->getNext();
if(pHead)
pHead->setPrevious(NULL);
else
pHead=pTail=NULL;
remove(pTmp);
}
void LinkedList::remove(Node *tmp)
{
delete tmp;
nodeCounter--;
};
void LinkedList::removeLast()
{
if( !pHead )
{
cerr<<"\nTidak ada node yang akan dihilangkan!!";
return ;
}
Node *pTmp=pTail;
pTail=pTail->getPrevious();
if(pTail)
pTail->setNext(NULL);
else
pTail=pHead=NULL;
remove(pTmp);
}
void LinkedList::destroyList()
{
Node *pTmp=pHead;
Node *pCur;
while( pTmp != NULL)
{
pCur=pTmp;
pTmp=pTmp->getNext();
remove(pCur);
}
}
//fungsi utama
int main()
{
LinkedList *p=new LinkedList;
for(int i=0;i<5;i++)
p->addLast(2*i+1);
cout<<"\nNAMA : MAHFUZ\n";
cout<<"\nNIM : 100533405403\n";
cout<<"\nKELAS : PTI '10 B\n";
cout<<"\ndata yang telah dihubungkan atau dimasukkan pada fungsi perintah:\n";
p->displayInOrder();
cout<<"\ndata yang telah dibalikkan pada fungsi perintah:\n";
p->displayInReverseOrder();
cout<<"\nmenambahkan 2 sebelum node ke dua (3). \n";
p->addBefore(2,2);
cout<<"\nmenembahkan 4 sebelum node ke empat (5). \n";
p->addBefore(4,4);
cout<<"\nmenambahkan 6 sebelum node ke enam (7). \n";
p->addBefore(6,6);
cout<<"\nmenambahkan 8 sebelum node ke delapan (9). \n";
p->addBefore(8,8);
cout<<"\ndata yang telah dihubungkan atau dimasukkan pada fungsi perintah: \n";
p->displayInOrder();
return 0;
}
Semoga bermanfaat bagi anda.
READ MORE
Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Dikatakan single (singly) linked apabila hanya ada satu pointer yang menghubungkan setiap node. single artinya field pointer-nya hanya satu buah saja dan satu arah.
Contoh program Linked List:
#include <iostream>
#include <stdlib.h>
using namespace std;
// Node Class
class Node
{
private:
int data;
Node *pNext;
Node *pPrevious;
public:
Node(int d):data(d),pNext(NULL),pPrevious(NULL){}
int getData()const{return data;}
void setData(int d){data=d;}
Node * getNext()const{return pNext;}
void setNext(Node *p){pNext=p;}
Node * getPrevious()const {return pPrevious;}
void setPrevious(Node *p){pPrevious=p;}
};
// LinkedList class
class LinkedList
{
protected:
Node *pHead; //penunjuk (pointer) untuk node awal
Node *pTail; //penunjuk (pointer) untuk node terakhir
int nodeCounter; //menghitung jumlah angka pada node
Node * makeNode(int data); // membuat dan menukar node baru.
void remove(Node *tmp); // menghilangkan node dari data yang dihubungkan (linked list).
public:
LinkedList();
~LinkedList();
// pengoperasian
void addFirst(int data);
void addLast(int data);
void addBefore(int index,int data);
void removeFirst();
void removeLast();
void displayInOrder()const;
void displayInReverseOrder()const;
void destroyList();
int getSize()const{return nodeCounter;}
};
LinkedList::LinkedList():
pHead(NULL),pTail(NULL),nodeCounter(0)
{}
LinkedList::~LinkedList()
{
destroyList();
}
void LinkedList::displayInOrder()const
{
if( !pHead )
{
cout<<"\nNULL";
return ;
}
for(Node *cur=pHead;cur!=NULL;cur=cur->getNext())
cout<<cur->getData()<<" -> ";
cout<<"NULL"<<endl;
}
void LinkedList::displayInReverseOrder()const
{
if( !pHead )
{
cout<<"\nNULL";
return ;
}
for(Node *cur=pTail;cur!=NULL;cur=cur->getPrevious())
cout<<cur->getData()<<" -> ";
cout<<"NULL"<<endl;
}
Node * LinkedList::makeNode(int data)
{
nodeCounter++;
return new Node(data);
}
void LinkedList::addFirst(int data)
{
// membuat node baru
Node *pNew=makeNode(data); //membuat node baru sebagai node partama atau awal pada data yang dihubungkan (linked list).
if( !pHead ) // jika data yang dihubungkan atau yang dimasukkan tersebut kosong.
pHead=pTail=pNew;
else // jika terdapat beberapa node.
{
pNew->setNext(pHead);
pHead->setPrevious(pNew);
pHead=pNew;
}
}
void LinkedList::addLast(int data)
{
// membuat node baru
Node *pNew=makeNode(data);
// membuat node baru sebagai node terakhir pada data yang dihubungkan (linked list).
//jika pada kondisi tidak terdapat node pada data yang dihubungkan (linked list), maka ditambah node lagi.
//cara lain untuk memindahkan sebuah node baru ke tempat node yang terakhir.
if( !pHead )
pHead=pTail=pNew;
else
{
pTail->setNext(pNew);
pNew->setPrevious(pTail);
pTail=pNew;
}
}
void LinkedList::addBefore(int index,int data)
{
// mengecek atau memeriksa index untuk mengetahui apakah data yang dimasukkan sesuai atau tidak.
if( index <1 || index > getSize() )
{
cerr<<"\nError: index is too hight/low ";
return;
}
if(index == 1)
{
addFirst(data);
return ;
}
// Membuat node baru
Node *pNew=makeNode(data);
Node *pCur=pHead;
for(int i=1;i<index -1;i++,pCur=pCur->getNext());
pNew->setNext(pCur->getNext());
pCur->setNext(pNew);
}
void LinkedList::removeFirst()
{
if( !pHead )
{
cerr<<"\nTidak ada node yang akan dihilangkan!!";
return ;
}
Node *pTmp=pHead;
pHead=pHead->getNext();
if(pHead)
pHead->setPrevious(NULL);
else
pHead=pTail=NULL;
remove(pTmp);
}
void LinkedList::remove(Node *tmp)
{
delete tmp;
nodeCounter--;
};
void LinkedList::removeLast()
{
if( !pHead )
{
cerr<<"\nTidak ada node yang akan dihilangkan!!";
return ;
}
Node *pTmp=pTail;
pTail=pTail->getPrevious();
if(pTail)
pTail->setNext(NULL);
else
pTail=pHead=NULL;
remove(pTmp);
}
void LinkedList::destroyList()
{
Node *pTmp=pHead;
Node *pCur;
while( pTmp != NULL)
{
pCur=pTmp;
pTmp=pTmp->getNext();
remove(pCur);
}
}
//fungsi utama
int main()
{
LinkedList *p=new LinkedList;
for(int i=0;i<5;i++)
p->addLast(2*i+1);
cout<<"\nNAMA : MAHFUZ\n";
cout<<"\nNIM : 100533405403\n";
cout<<"\nKELAS : PTI '10 B\n";
cout<<"\ndata yang telah dihubungkan atau dimasukkan pada fungsi perintah:\n";
p->displayInOrder();
cout<<"\ndata yang telah dibalikkan pada fungsi perintah:\n";
p->displayInReverseOrder();
cout<<"\nmenambahkan 2 sebelum node ke dua (3). \n";
p->addBefore(2,2);
cout<<"\nmenembahkan 4 sebelum node ke empat (5). \n";
p->addBefore(4,4);
cout<<"\nmenambahkan 6 sebelum node ke enam (7). \n";
p->addBefore(6,6);
cout<<"\nmenambahkan 8 sebelum node ke delapan (9). \n";
p->addBefore(8,8);
cout<<"\ndata yang telah dihubungkan atau dimasukkan pada fungsi perintah: \n";
p->displayInOrder();
return 0;
}
Semoga bermanfaat bagi anda.
