Binary Search Tree

Berikut kodingan saya sendiri mengenai Binary Search Tree.

#include<stdio.h>
#include<stdlib.h>

int flag = 0;

struct node{
int angka;
struct node *left;
struct node *right;
};

struct node *NodeBaru(int InputanAngka){
//bkin structnya buat ditempatin di akar paling bawah
struct node *temp = (struct node*) malloc (sizeof(struct node));
temp->angka = InputanAngka;
temp->left=temp->right=NULL;
}

struct node *MasukkanAngka(struct node *ROOT,int InputanAngka){
//klo misal akar yang ditempatinya NULL yauda tinggal dimasukkin datanya
if(ROOT==NULL){
return NodeBaru(InputanAngka);
}
//bakal pindah akar ke kiri teros klo lebih kecil smpe nemu NULL^
if(InputanAngka < ROOT->angka){
ROOT->left = MasukkanAngka(ROOT->left, InputanAngka);
}
//bakal pindah akar ke kanan teros klo lebih besar dr smua angka smpe nemu NULL^
else if(InputanAngka > ROOT->angka){
ROOT->right = MasukkanAngka(ROOT->right, InputanAngka);
}
}

struct node *CariNode(struct node *root){
struct node *curr = root->left;
while(curr->right!=NULL){
curr = curr->right;
}
return curr;
}

struct node *HapusAngka (struct node *root, int AngkaYangDicari){
//klo data ga ditemukan
if(root==NULL){
flag = 2;
return NULL;
}
//cari angka di root kiri
else if(AngkaYangDicari < root->angka){
root->left = HapusAngka(root->left,AngkaYangDicari);
}
//cari angka di root kanan
else if(AngkaYangDicari > root->angka){
root->right = HapusAngka(root->right,AngkaYangDicari);
}
//angkanya udah ketemu
else{
//ini untuk case klo rootnya punya 1 cabang atau tidak punya sama sekali
if(root->left==NULL||root->right==NULL){
struct node *temp = NULL;
if(root->right!=NULL){
temp=root->right;
}
else{
temp=root->left;
}
//jika tidak mempunyai cabang samsek
if(temp==NULL){
root=NULL;
}
//jika terdapat salah satu cabang
else{
*root = *temp;
}
free(temp);
}
//ini untuk case yang terdapat 2 cabang
else{
//cari node paling kanan di root->left
struct node *temp = CariNode(root);
root->angka=temp->angka;

//deletenya
root->left=HapusAngka(root->left,temp->angka);
}
}
return root;
}

void PrintAll(struct node *root){
//klo misal akar yg diliatnya skrg udah NULL printnya berhenti
if(root!=NULL){
//nge print smua yg dikiri
PrintAll(root->left);
printf("%d\n",root->angka);
//ini biar printnya bisa liat angka yang dikanan
PrintAll(root->right);
}
}

int main(){
int Menu,AngkaInput,AngkaDelete;
//ini biar jadi pusat akarnya
struct node *root = NULL;
do{
if(flag==0){
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
}
else if (flag==1){
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
PrintAll(root);
flag=0;
}
else if(flag==2){
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
printf("Data Tidak Ditemukan!\n");
}
printf("BINARY SEARCH TREE\n");
printf("Menu :\n");
printf("1. Masukkan Angka\n");
printf("2. Hapus Angka\n");
printf("3. Print Angka\n");
printf("4. Exit\n");
printf(">> ");
scanf("%d",&Menu);
if(Menu==1){
printf("Input Angka : ");
scanf("%d",&AngkaInput);
root=MasukkanAngka(root,AngkaInput);
}else if(Menu==2){
printf("Tulis Angka Yang Mau Dihapus : ");
scanf("%d",&AngkaDelete);
root=HapusAngka(root,AngkaDelete);
}else if(Menu==3){
flag=1;
}
}while(Menu!=4);
}

Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

Gambar
Pada dasarnya AVL Tree ini adalah Binary Search Tree namun yang lebih seimbang atau balance karena pasti total node kiri dan kanan selisih tingginya tidak akan lebih dari 1. Sedangkan di BST bisa saja tinggi node kiri dan kanan tidak seimbang sehingga bisa menyebabkan proses pencarian, insert, maupun delete lebih lama yaitu n sedangkan dengan AVL Tree proses pencarian,insert, atau delete menjadi log n. Contoh hasil BST jika dengan insert 2, 5, 7, 8, 13: Contoh hasil AVL Tree jika dengan insert yang sama: Untuk menyeimbangkan node tersebut, AVL Tree menggunakan rotasi atau rotation. Rotation ini dibagi menjadi 2 yaitu single rotation dan double rotation. rotation ini terjadi akibat perbedaan selisih tinggi node kiri dan kanan yang lebih dari 1. Contoh single rotation Contoh double rotation
Baca selengkapnya

HEAP and TRIES

Gambar
HEAP Heaps adalah binary tree yang nodenya dapat direpresentasikan dalam sebuah array. Type of Heap A. Max Heap Max yang berarti parentnya lebih besar daripada childnya. Elemen terbesar pada Max Heap terdapat di root tree dan semakin kebawah artinya semakin kecil. B. Min Heap Min yang berarti parentnya lebih kecil daripada childnya. Elemen terbesar pada Min Heap terdapat di root tree dan semakin kebawah artinya semakin besar. Heap dapat diimplementasikan menggunakan linked list tapi lebih mudah menggunakan array. C. Min Max Heap Ini adalah case unik atau spesial dari heap. Max dan min bergantian pada setiap level. Urutan level dari heap berupa min(dimulai dari root) lalu max lalu min lagi dan seterusnya. Pada bagian min akan selalu ganjil dan max akan selalu genap. Di dalam heap terdapat 2 metode yaitu insertion dan deletion. Max Heap Insertion step 1 : membuat node baru di akhir dari heap step 2 : memasukkan nilai baru ke node tersebut ste...
Baca selengkapnya

Summary

Gambar
Linked List Pada pertemuan kedua kelas besar kemarin saya belajar mengenai cara membuat linked list di C. Setelah saya mempelajarinya kemarin, saya juga mencoba membuat linked list buatan saya sendiri. Berikut codingan linked list saya : #include<stdio.h> #include<stdlib.h> #include<string.h> struct Node{ int test; char nama[1000]; struct Node *next; }*head,*curr,*tail,*temp1,*temp2; void pushhead(int a,char nama[]){ curr = (struct Node*)malloc(sizeof(struct Node)); curr -> test = a; strcpy(curr->nama,nama); if(head==NULL){ head=curr; tail=curr; tail->next=NULL; } else{ curr->next = head; head = curr; } } void pushtail(int a,char nama[]){ curr = (struct Node*)malloc(sizeof(struct Node)); curr -> test = a; strcpy(curr->nama,nama); if(head==NULL){ head=curr; tail=curr; tail->next=NULL; } else{ tail->next = curr; curr->next=NULL; tail = curr; } } void poptail(){ curr=head; while(curr->next->nex...
Baca selengkapnya