/*Insertion ,Deletion and Traversal pada Binary Search Tree*/
# include <stdio.h>
# include <conio.h> // (1)
# include <stdlib.h>
Listing diatas digunakan untuk mengawali program yang dibuat. Include digunakan untuk membuat library di dalam program.
struct node {
int info;
struct node *lchild;
struct node *rchild; // (2)
}*root;
main() {
int choice,num;
root=NULL;
clrscr();
Listing diatas digunakan untuk mendefinisikan struktur node ke dalam program.untuk mendefinisikan fungsi-fungsi yang digunakan di dalam program yang akan dipanggil saat program dijalankan.dan merupakan fungsi utama dari program yang dimana fungsi ini yang akan dijalankan oleh program. root yang akan digunakan adalah nilai root sama dengan null atau kosong.
while(1) {
printf("\n");
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Inorder Traversal\n");
printf("4.Preorder Traversal\n");
printf("5.Postorder Traversal\n");
printf("6.Display\n");
printf("7.Quit\n");
printf("\nPilih : ");
scanf("%d",&choice);
switch(choice) {
Listing diatas digunakan untuk memilih menu yang ada dalam program yaitu insert, delete,preorder, inorder, postorder, display,dan exit. Untuk menginputkan pilihan digunakan perintah scanf.
case 1:
printf("\n masukkan item yag ingin disisipkan : ");
scanf("%d",&num);
insert(num); // (3)
break;
case 2:
printf("\n masukkan item yang ingin dihapus : ");
scanf("%d",&num);
del(num);
break;
case 3:
inorder(root); // (4)
break;
case 4:
preorder(root);
break;
case 5:
postorder(root); // (5)
break;
case 6:
display(root,1);
break;
case 7:
exit(1); // (6)
default:
printf("\nWeii... salah pilih tuh !\n");
}/*End of switch */
}/*End of while */
}/*End of main()*/
Listing diatas digunakan untuk kondisi. Dimana jika memilih 1 akan memasukan inputan (insert). Jika memili 2 maka akan menghapus inputan. Jika memilih 3 untuk mencetak nilai atau elemen dengan posisi inorder. Jika memilih 4 untuk mencetak nilai atau elemen dengan posisi preorder. Jika memilih 5 untuk mencetak nilai atau elemen dengan posisi postorder. Jika memilih 6 maka akan menampilkan hasil dari nilai atau elemen tersebut.jika memilih 7 maka akan keluar dari program.
find(int item,struct node **par,struct node **loc){
struct node *ptr,*ptrsave;
if(root==NULL) /*kondisi pada tree*/ {
*loc=NULL;
*par=NULL;
return; }
if(item==root->info) /*item terdapat pada root*/ {
*loc=root;
*par=NULL;
return;}
Listing diatas menjelaskan tentang struct node dimana jika dalam konisi pada tree root sama dengan NULL. NULL adalah 0 disini untuk menguji bilangan tersebut. Dan didalam item terdapat root artinya menguji apakah item telah menemukan lokasinya.
/*Inisialisasi ptr dan ptrsave*/
if( item)
ptr=root->lchild;
else
ptr=root->rchild;
ptrsave=root;
while(ptr!=NULL) {
if(item==ptr->info)
{ *loc=ptr;
*par=ptrsave;
return; }
ptrsave=ptr;
if(item)
ptr=ptr->lchild;
else
ptr=ptr->rchild;
}/*End of while */
*loc=NULL; /*item tidak ditemukan*/
*par=ptrsave;
}/*End of find()*/
insert(int item)
{ struct node *tmp,*parent,*location;
find(item,&parent,&location);
if(location!=NULL){
printf("\n item tersebut ada lho !");
return;}
Listing diatas menjelaskan tentang inisialisasi pointer dan pointer save. Jika pointer sama dengan root maka dimulai dari kiri jika tidak maka dimulai dari kanan. Untuk perulangan while pointer tidak sama dengan NULL digunakan untuk mencari item yang ingin dicari. Jika item tersebut tidak ditemukan maka pointer sama dengan pointer. Jika item tersebut ditemukan maka letak lokasi tersebut tidak sama dengan NULL(0).
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=item; // (7)
tmp->lchild=NULL;
tmp->rchild=NULL;
if(parent==NULL)
root=tmp;
else
if(item)
parent->lchild=tmp;
else
parent->rchild=tmp;
}/*End of insert()*/
Listing diatas digunakan untuk memesan tempat dengan perintah malloc yang digunakan untuk mendapatkan memori aktual yang menginisialisasikan field data. parent sama dengan NULL jika root sama dengan temporary dan jika parent maka temporary di mulai dari sebelah kiri maka juga bisa dimulai dari kanan.
del(int item){
struct node *parent,*location;
if(root==NULL){
printf("\n Tree kosong lho! ");
return;}
find(item,&parent,&location);
if(location==NULL){
printf("\n Item tidak ada pada tree lho !");
return;}
if(location->lchild==NULL && location->rchild==NULL)
case_a(parent,location); // (8)
if(location->lchild!=NULL && location->rchild==NULL)
case_b(parent,location);
if(location->lchild==NULL && location->rchild!=NULL)
case_b(parent,location);
if(location->lchild!=NULL && location->rchild!=NULL)
case_c(parent,location);
free(location);
}/*End of del()*/
Listing diatas menjelaskan tentang penghapusan. Jika root sma dengan NULL maka mencetak tree kosong. Jika lokasi sama dengan NULL maka mencetak item tidak ada tree.
case_a(struct node *par,struct node *loc ){
if(par==NULL) /*item yg akan di hapus adalah root simpul*/
root=NULL;
else
if(loc==par->lchild)
par->lchild=NULL;
else
par->rchild=NULL;
}/*End of case_a()*/
case_b(struct node *par,struct node *loc){
struct node *child; // (9)
/*Inisialisasi child*/
if(loc->lchild!=NULL) /*item yg akan dihapus ialah lchild */
child=loc->lchild;
else /*item yg akan dihapus ialah rchild */
child=loc->rchild;
if(par==NULL ) /*Item yang akan dihapus ialah root simpul*/
root=child;
else
if( loc==par->lchild) /*item yg menjadi parent lchild*/
par->lchild=child;
else /*item yg menjadi parrent rchild*/
par->rchild=child;
}/*End of case_b()*/
case_c(struct node *par,struct node *loc){
struct node *ptr,*ptrsave,*suc,*parsuc;
/*menemukan notasi inorder dan parent*/
ptrsave=loc;
ptr=loc->rchild;
while(ptr->lchild!=NULL){
ptrsave=ptr;
ptr=ptr->lchild;}
suc=ptr;
parsuc=ptrsave;
if(suc->lchild==NULL && suc->rchild==NULL)
case_a(parsuc,suc);
else
case_b(parsuc,suc);
if(par==NULL)
root=suc;
else
if(loc==par->lchild)
par->lchild=suc;
else
par->rchild=suc;
suc->lchild=loc->lchild;
suc->rchild=loc->rchild;
}/*End of case_c()*/
Listing diatas menjelaskan tentang penghapusan data.jika parent sama dengan NULL maka yang dihapus adalah simpul dari root tersebut. Jika root maka lchild tidak sama dengan NULL maka yang dihapus dimulai dari kiri. Jika root sama dengan parent maka item tersebut akan menjadi parent dari lchild tersebut. Untuk menemukan notasi inorder dan parent digunakan ptr sama dengan loc maka lchild.untuk perulangan ptr maka lchild tidak sama dengan NULL. Jika suc maka lchild sama dengan NULL dan suc maka rchild sama dengan NULL adalah case_a. Case_b jika parent sama dengan NULL dan jika loc sama dengan parent maka lchild.
preorder(struct node *ptr){
if(root==NULL){
printf("\n Tree kosong lho !");
return;}
if(ptr!=NULL){
printf("%d ",ptr->info);
preorder(ptr->lchild);
preorder(ptr->rchild);}
}/*End of preorder()*/
Listing diatas merupakan fungsi preorder dengan kondisi jika root sama dengan NULL maka akan mencetak “tree kosong” dan jika ptr tidak sama dengan null maka akan mencetak element yang ada di dalam tree yang telah diinputkan. Element yang tercetak pun sesuai dengan posisi preorder. Dimana yang akan tercetak dari element yang berada disebelah kiri dari root baru ke elemen yang berada di sebelah kanan dari root.
inorder(struct node *ptr){
if(root==NULL){
printf("\n Tree kosong lho !");
return;}
if(ptr!=NULL){
inorder(ptr->lchild);
printf("%d ",ptr->info);
inorder(ptr->rchild);}
}/*End of inorder()*/
Listing diatas merupakan fungsi inorder dengan kondisi jika root sama dengan NULL maka akan mencetak “tree kosong” dan jika temp tidak sama dengan null maka akan mencetak element yang ada di dalam tree yang telah diinputkan. Element yang tercetak pun sesuai dengan posisi inorder. Dimana yang akan tercetak dari element yang berada disebelah kiri dari root dengan posisi elemnt yang berurutan.
postorder(struct node *ptr){
if(root==NULL){
printf("\n Tree kosong lho");
return;}
if(ptr!=NULL){
postorder(ptr->lchild);
postorder(ptr->rchild);
printf(" %d ",ptr->info);}
}/*End of postorder()*/
Listing diatas merupakan fungsi postorder dengan kondisi jika root sama dengan NULL maka akan mencetak “tree kosong” dan jika temp tidak sama dengan null maka akan mencetak element yang ada di dalam tree yang telah diinputkan. Element yang tercetak pun sesuai dengan posisi postorder. Dimana yang akan tercetak dari element yang berada disebelah kanan dari root baru ke elemen yang berada di sebelah kiri dari root.
display(struct node *ptr,int level){
int i; // (10)
if ( ptr!=NULL ){
display(ptr->rchild, level+1);
printf("\n");
for (i = 0; i < level; i++)
printf(" ");
printf(" %d", ptr->info);
display(ptr->lchild, level+1);
}/*End of if*/
}/*End of display()*/
Listing diatas merupakan fungsi untuk menampilkan data yang telah di input. Jika ptr tidak sama dengan NULL maka akan menampilkan data sesuai inputan. Jika sama dengan NULL maka akan melakukan perulangan sebanyak 1 x kemudian mencetak data tersebut dengan mencetak secara kebawah miring ke kanan.
Tidak ada komentar:
Posting Komentar