Contoh
Program C++ BINARY TREE
Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah
pohon struktur data di mana setiap simpul memiliki paling banyak dua anak.
Secara khusus anaknya dinamakan kiri dan kanan. Ini adalah contoh implementadi
pohon biner pada bahasa C++
#define WINDOWS
//#define LINUX
/** FAMILY TREE */
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
struct node
{
char name[50];
short int age,x; // x - height
of node
bool g; // g- gender
node* fc; // Pointer to
first child
node* ns; // Pointer to
next sibiling
node();
void getData();
};
node::node()
{
fc=ns=NULL;
g=0;
strcpy(name,"");
age=x=0;
}
void node::getData()
{
char ch;
cout<<"\nNama orang: ";
cin>>name;
cout<<"Umur "<<name<<": ";
cin>>age;
cout<<name<<" Adalah (P/L): ";
cin>>ch;
if(ch=='m')
g=1;
}
class familyTree
{
public:
node* start;
familyTree();
node* traverseDown(node*,char[]);
// Search functions
node* traverseRight(node*,char[]);
node* search(char[]);
void addSib(node*,node*);
// Functions for adding new members
void addChild(node*,node*);
void addNew();
void find(); // Function to find
relations
void show(node*);
// Function to show details of particular person
void display(node*);
// Function to display full tree
void destroy(node*); // Function to destroy full tree
void updateX(node*,int);
};
familyTree::familyTree()
{
start = NULL;
}
void familyTree::destroy(node* ptr)
{
node* temp = ptr;
if(ptr==NULL)
return;
while(ptr!=NULL)
{
destroy(ptr->fc);
temp = ptr;
ptr = ptr->ns;
delete temp;
}
start = NULL;
}
void familyTree::show(node* ptr)
{
char g[10];
strcpy(g,"Perempuan");
if(ptr->g)
strcpy(g,"Laki laki");
cout<<"\n\nNama: "<< ptr->name <<endl;
cout<<"Umur: "<< ptr->age <<endl;
cout<<"Jenis Kelamin: "<<g<<endl;
}
void familyTree::display(node* ptr)
{
if(ptr==NULL)
return;
while(ptr!=NULL)
{
cout<< ptr->name <<endl;
display(ptr->fc);
ptr = ptr->ns;
}
}
void familyTree::updateX(node*
ptr,int x)
{
if(ptr==NULL)
return;
while(ptr!=NULL)
{
updateX(ptr->fc,x++);
if(ptr->ns!=NULL)
ptr->ns->x = x;
ptr = ptr->ns;
}
}
void familyTree::find()
{
char name1[50],name2[50];
cout<<"Masukkan nama dua orang: \n";
cin>>name1>>name2;
node* ptr1 = search(name1);
node* ptr2 = search(name2);
node* ptr;
node* ptrk=ptr1;
node* ptrk1=ptr2;
switch(ptr1->x - ptr2->x)
{
case 0:
char s[50];
strcpy(s,"sister");
if(ptr1->g)
strcpy(s,"brother");
ptr = ptr1;
while(ptr!=NULL)
{
if(ptr==ptr2)
{
cout<<endl<<name1<<" is
"<<name2<<"'s "<<s<<endl;
return;
}
ptr = ptr->ns;
}
ptr = ptr2;
while(ptr!=NULL)
{
if(ptr==ptr1)
{
cout<<endl<<name1<<" is
"<<name2<<"'s "<<s<<endl;
return;
}
ptr = ptr->ns;
}
cout<<endl<<name1<<"
and "<<name2<<" are Cousins";
break;
case 1:
char str3[50];
strcpy(str3,"daughter");
if(ptr1->g)
strcpy(str3,"son");
ptr2 = ptr2->fc;
while(ptr2!=NULL)
{
if(ptr2==ptr1)
{
cout<<endl<<name1<<" is
"<<name2<<"'s "<<str3;
return;
}
ptr2=ptr2->ns;
}
strcpy(str3,"niece");
if(ptr1->g)
strcpy(str3,"nephew");
cout<<endl<<name1<<" is
"<<name2<<"'s "<<str3;
break;
case -1:
char str[10];
strcpy(str,"Ibu");
if(ptrk->g)
strcpy(str,"Ayah");
ptr = ptrk->fc;
while(ptr!=NULL)
{
if(ptr==ptrk1)
{
cout<<endl<<name1<<" is
"<<name2<<"'s "<<str;
return;
}
ptr=ptr->ns;
}
strcpy(str,"Paman");
if(ptrk->g)
strcpy(str,"Cucu");
cout<<endl<<name1<<" is
"<<name2<<"'s "<<str;
break;
case 2:
char str1[50];
strcpy(str1,"daughter");
if(ptr2->g)
strcpy(str1,"son");
ptr2 = ptr2->fc->fc;
while(ptr2!=NULL)
{
if(ptr2==ptr1)
{
cout<<endl<<name1<<"
is grand "<<str1<<" of "<<name2;
return;
}
ptr2 = ptr2->ns;
}
break;
case -2:
char str2[50];
strcpy(str2,"mother");
if(ptr1->g)
strcpy(str2,"father");
ptr1 = ptr1->fc->fc;
while(ptr1!=NULL)
{
if(ptr1==ptr2)
{
cout<<endl<<name1<<" is grand
"<<str2<<" of "<<name2;
return;
}
ptr1 = ptr1->ns;
}
break;
default:
cout<<"Hubungan terlalu
jauh";
break;
}
}
node* familyTree::search(char
s[50])
{
node *ptr = start;
if(strcmp(ptr->name,s)==0)
return ptr;
else if(traverseRight(start,s)!=NULL)
return traverseRight(start,s);
else if(traverseDown(start,s)!=NULL)
return traverseDown(start,s);
else
{
return NULL;
cout<<"***Tidak
ditemukan***";
}
}
node*
familyTree::traverseDown(node* ptr, char s[50])
{
ptr = ptr->fc;
while(ptr!=NULL)
{
if(
strcmp(ptr->name,s)==0 )
return ptr;
else if(traverseRight(ptr,s)!=NULL)
return traverseRight(ptr,s);
else
ptr = ptr->fc;
}
return NULL;
}
node*
familyTree::traverseRight(node* ptr, char s[50])
{
ptr = ptr->ns;
while(ptr!=NULL)
{
if(strcmp(ptr->name,s)==0)
return ptr;
else if (traverseDown(ptr,s)!=NULL)
return traverseDown(ptr,s);
else
ptr = ptr->ns;
}
return NULL;
}
void familyTree::addNew()
{
node* temp = new node;
temp->getData();
if(start == NULL)
{
start = temp;
temp->x=0;
}
else
{
cout<<"\nMasukkan nama
relasi apa pun: ";
char name[50];
cin>>name;
cout<<"\n1. Anak\n2. Saudara
kandung\n\n"<< temp->name <<" is ____ to
"<<name<<" : ";
int opt;
cin>>opt;
switch(opt)
{
case 1:
addChild(search(name),temp);
break;
case 2:
addSib(search(name),temp);
break;
}
}
cout<<"\nOrang berhasil ditambahkan.\n";
}
void familyTree::addSib(node*
a,node* b)
{
while(a->ns!=NULL)
a=a->ns;
a->ns = b;
b->x = a->x;
}
void familyTree::addChild(node*
a,node* b)
{
if(a->fc==NULL)
a->fc = b;
else
addSib(a->fc,b);
b->x = a->x+1;
}
void connect(familyTree *T1,
familyTree *T2)
{
char name[50];
int opt;
int x;
cout<<"Nama orang di pohon ke-1 untuk bergabung: ";
cin>>name;
cout<<T2->start->name<<" is __ to
"<<name<<"\n1. Anak 2. Saudara Kandung - ";;
cin>>opt;
node *ptr = T1->search(name);
switch(opt)
{
case 1:
T1->addChild(ptr,T2->start);
x = ptr->x + 1;
break;
case 2:
T1->addSib(ptr,T2->start);
x = ptr->x;
break;
}
T2->updateX(T2->start,x);
T2->destroy(T2->start);
cout<<"\nMerged\n";
}
int main()
{
familyTree T[100];
int opt,n,n1,n2;
char c,name[50];
cout<<"\nMasukkan nomor pohon keluarga = ";
cin>>n;
while(1)
{
#ifdef WINDOWS
system("cls");
#endif
#ifdef LINUX
system("clear");
#endif
cout<<"\n\n\n\tPohon
keluarga nomer = "<<n<<"\n\n\t1. Tambahkan orang
baru\n\t2. Temukan hubungan antara dua orang\n\t3. Pencarian\n\t4. Hapus\n\t5.
Tampilkan\n\t6. Ubah silsilah keluarga\n\t7. Hubungkan dua pohon keluarga\n\t8.
Exit\n\n\tMasukkan pilihan Anda = ";
cin>>opt;
cout<<endl;
switch(opt)
{
default:
cout<<"Masukan tidak
valid";
break;
case 1:
T[n].addNew();
break;
case 2:
T[n].find();
break;
case 3:
cout<<"Masukkan nama
orang untuk dicari: ";
cin>>name;
T[n].show(T[n].search(name));
break;
case 4:
T[n].destroy(T[n].start);
cout<<"Tree
"<<n<<" telah berhasil dihapus";
break;
case 5:
T[n].display(T[n].start);
break;
case 6:
cout<<"Masukkan
nomor pohon keluarga: ";
cin>>n;
break;
case 7:
cout<<"Gabung __ ke
__ \n";
cin>>n2>>n1;
connect(&T[n1],&T[n2]);
break;
case 8:
return 0;
}
cout<<"\n\ntekan tombol apa
saja untuk melanjutkan.....";
cin>>c;
}
}
Untuk outputnya dapat dilihat pada gambar dibawah ini ............
TERIMAKASIH................
Sumber Referensi
Modul Praktikum Struktur Data. Sukirman dan Irma Yuliana, Surakarta Februari 2017
Tidak ada komentar:
Posting Komentar