Tree

Tree/Pohon

Pada struktur data kita juga mempelajari tree/pohon seperti juga pada mata kuliah Matematika Diskrit, bedanya ya tentu saja pada mata kuliah Struktur Data kita membuat code nya.
Nah, sebelum berbicara lebih jauh, berikut merupakan beberapa konsep yang harus di ketahui mengenai tree :

1. Tree adalah kumpulan beberapa node.
2. Node yang paling atas yang tidak memiliki parent disebut dengan akar/root.
3. Sebuah garis yang menghubungkan parent dengan anaknya disebut dengan edge.
4. Node yang tidak memiliki anak disebut dengan leaf/daun.
5. Node-node yang memiliki orang tua yang sama, berarti node-node tersebut bisa dikatakan saudara/sibling.
6. Degree sebuah node adalah total subtree node.
7. Height/Depth adalah ketnggian dari suatu pohon.

Binary Tree

Dapat diartikan sebagai tree yang setiap node nya paling banyak memiliki 2 anak.,left child dan juga right child.

Nah pada gambar diatas merupakan contoh dari binary tree.

Root/akar dari tree tersebut adalah angka 2 paling atas yang tidak memiliki parent, dan yang merupakan leaf/daun adalah angka 2 yang dibawah,5,11,4.

Macam-macam Binary Tree

1. Perfect Binary Tree : tree yang setiap node nya pasti memiliki 2 anak sehingga tree tersebut menjadi seimbang bagian kiri maupun kanan nya. Berikut ini merupakan contoh nya :
   
2. Complete Binary Tree : tree yang notabene lebih condong kekiri dikarenakan cara pengisian setiap level nya dengan cara bagian kiri diisi terlebih dahulu. Perfect Bianry Tree juga termasuk kedalam Complete Binary Tree. Berikut ini merupakan contoh nya :
   
3. Skewed Binary Tree : tree dimana node-node hanya memilki satu anak sehingga tree akan condong/berat sebelah, bisa kekiri maupun kekanan. Berikut ini merupakan contoh nya :
   

Hal-hal mengenai binary Tree :

1. Jumlah maksimum node disuatu level k pada binary tree yaitu 2k. Dimana level pada binary tree dimulai dari level 0.
2. Jumlah maksimum semua node pada ketinggian h pada binary tree yaitu 2h+1 - 1, dimana ketinggian dimulai dari 0.
3. Ketinggian minimum dari suatu binary tree yang memiliki node sebanyak n yaitu 2log(n).
4. Ketinggian maksimum dari suatu binary tree yang memiliki node sebanyak n yaitu n-1.(pada skewed binary tree).

Tree sendiri kemungkinan akan digunakan / sangat berhubungan dengan prefix,infix dan juga postfix

Contoh : prefix +ab

infix a+b

postfix ab+

Binary Seach Tree

adalah binary tree dengan tambahan-tambahan sebagai berikut :

1. Setiap node memiliki sebuah key/kunci dan tidak ada node lain yang memiliki key yang sama.
2. Node-node yang berada di sebelah kiri root memiliki key yang lebih kecil dibandingkan dengan key di root(standar nya seperti itu, tapi bisa juga sebaliknya).
3. Node-node yang berada di sebelah kanan root memiliki key yang lebih besar dibandingkan dengan key di root(standar nya seperti itu, tapi bisa juga sebaliknya).

Berikut merupakan contoh Binary Search Tree 

Kegunaan utama dari BST sendiri yaitu memudahkan dan juga mempercepat dalam mencari data hingga mencapai 2x lebih cepat. Itulah mengapa skewed tree dapat dilakukan AVL agar tree jadi seimbang dan mempercepat pencarian data.

Berikut ini merupakan 3 operasi pada BST :

1. Searching/Pencarian
1. Langkah :
1. Dimulai dari root.
2. Jika data di root sama dengan data yang ingin dicari maka proses pencarian selesai.
3. Jika key yang ingin dicari < data di root maka cari secara rekursif pada subtree yang kiri dan bila key > data di root maka cari secara rekursif pada subtree kanan.
2. Insert/Memasukkan data
1. Langkah:
1. Dimulai dari root.
2. Jika data yang ingin dimasukkan < data di root maka masukkan data tersebut ke subtree kiri dan lakukan terus menerus secara rekursif, sebaliknya jika data yang ingin dimasukkan > data di root maka masukkan data tersebut ke subtree kana dan lakukan juga terus menerus secara rekursif.
3. Lakukan terus sampai ditemukan node kosong untuk meletakkan data tersebut(data yang di masukkan akan selalu menjadi leaf/daun).
3. Delete/Menghapus node
1. Langkah :
1. Jika key nya di daun maka lagsung hapus saja node tersebut.
2. Jika key nya pada node yang memiliki 1 anak/child maka hapus node tersebut dan hubungkan childnya dengan parentnya–If the key is in a node which has one child, delete that node and connect its child to its parent
3. Jika key nya pada node yang memiliki 2 anak, temukan child yang paling kanan dari subtree kiri dan lakukan secara rekursif.
4. 
   
5. Operasi delete pada BST merupakan operasi tersulit dalam melakukan coding nya diantara operasi lainnya.

Preorder
Preorder adalah cara untuk menampilkan data dengan urutan seperti prefix. Rumus untuk preorder adalah PLR, yaitu data yang ditemukan(ditengah) dicetak/print (Print), kemudian bergerak kesebelah kiri (Left), setelah itu kesebelah kanan (Right).


Inorder
Inorder adalah cara untuk menampilkan data dengan urutan seperti infix. Rumus untuk inorder adalah LPR, yaitu memproses data disebelah kiri (Left),data yang ditemukan(ditengah) diprint (Print), lalu bergerak kesebelah kanan (Right).

Postorder
Postorder adalah cara untuk menampilkan data dengan urutan seperti postfix. Rumus untuk postfix adalah LRP, yaitu memproses data disebelah kiri (Left), kemudian bergerak kesebelah kanan (Right). terakhir baru memprint data yang ditemukan(ditengah) (Print).

NB : Bahan yang ditulis berdasarkan apa yang pernah saya pelajari dari dosen dan juga slide-slide powerpoint dari Binus University.


Binus University     Skyconnectiva

Code Binary Search Tree

Ini code untuk binasy search tree(BST) dari dosen saya(ko sky), tapi untuk code ini masih ada error nya, so, wait for update :

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

//Binary Search Tree
struct MLM{
char nama[25];
int usia;
int level;
struct MLM *left, *right, *parent;
}*root;

void push(struct MLM **curr, char nama[], int usia, int level){
if(*curr == NULL){
(*curr) = (struct MLM*)malloc(sizeof(struct MLM));
// Presendence (kurung)
strcpy((*curr)->nama, nama);
(*curr)->usia = usia;
(*curr)->level = level;
(*curr)->left = (*curr)->right = NULL;
}else{
if(usia < (*curr)->usia){
if(*curr != NULL){
(*curr)->left->parent = (*curr);
}
push(&(*curr)->left,nama,usia,level+1);
}else if(usia > (*curr)->usia){
if((*curr) != NULL){
(*curr)->right->parent = (*curr);
}
push(&(*curr)->right,nama,usia,level+1);
}else{
printf("Angka %d sudah ada\n",usia);
}
}
}

void preorder(struct MLM *curr){
if(curr == NULL){
//printf("Maaf, kosong.. coba lagi besok.\n");
//getchar();
}else{
printf("%s %d %d\n",curr->nama, curr->usia, curr->level);
preorder(curr->left);
preorder(curr->right);
}
}

void inorder(struct MLM *curr){
if(curr == NULL){
//printf("Maaf, kosong.. coba lagi besok.\n");
//getchar();
}else{
inorder(curr->left);
printf("%s %d %d\n",curr->nama, curr->usia, curr->level);
inorder(curr->right);
}
}

void postorder(struct MLM *curr){
if(curr == NULL){
//printf("Maaf, kosong.. coba lagi besok.\n");
//getchar();
}else{
postorder(curr->left);
postorder(curr->right);
printf("%s %d %d\n",curr->nama, curr->usia, curr->level);
}
}



void popALL(struct MLM *curr){
if(curr != NULL){
popALL(curr->left);
popALL(curr->right);
free(curr);
}
}

void pop(struct MLM **curr, char nama[]){
if(*curr==NULL){
printf("Not found !\n");
//kosong cuy
}else{
if(strcmpi(nama,(*curr)->nama) < 0){
pop(&(*curr)->left, nama);
}else if(strcmpi(nama, (*curr)->nama) > 0){
pop(&(*curr)->right,nama);
}else if(strcmpi(nama, (*curr)->nama) == 0){
printf("Nemu coy\n");
free(*curr);
}
}

}

int main(){
push(&root,"hehe",20,0);
push(&root,"hue",19,0);

//pop(&root,"hehe");
inorder(root);
return 0;
}

NB : Bahan yang ditulis berdasarkan apa yang pernah saya pelajari dari dosen dan juga slide-slide powerpoint dari Binus University.


Binus University     Skyconnectiva

Code Double Linked List *update*

Pada postingan kali ini coding linked list ini sudah lebih baik dikarenakan cara penghapusan yang lebih fleksibel(by user input(by name)) dan memasukkan data nya juga fleksibel, bahkan ada push mid nya juga lho..
So, check this code out :

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

//DLL
struct Grocery{
char vegetableName[25];
int qty;
struct Grocery *next,*prev;
}*tail, *head;

int jumlahData=0;

void push(char vegetableName[], int qty, int pos){
struct Grocery *curr = (struct Grocery*)malloc(sizeof(struct Grocery));
strcpy(curr->vegetableName, vegetableName);
curr->qty = qty;
if(head == NULL){
head = tail = curr;
tail->next = NULL;
head->prev = NULL;
}else{
if(pos == 1){
//push depan
curr->next = head;
head->prev = curr;
head = curr;
head->prev = NULL;
}else if(pos == jumlahData+1){
//push belakang
tail->next = curr;
curr->prev = tail;
tail = curr;
tail->next = NULL;
}else{
//push mid
struct Grocery *temp = head;
int i=1;
while(temp!=tail && i!= pos-1){
temp = temp->next;
i++;
}
curr->next = temp->next;
temp->next->prev = curr;
temp->next = curr;
curr->prev = temp;
}
}
}

void pop(char vegetableName[]){
if(head == NULL){
printf("\nSorry no vegetable at store");
getchar();
}else{
if(strcmp(head->vegetableName,vegetableName)==0){
//pop head
if(head == tail){
//data 1
free(head);
head = tail = NULL;
}else{
//data >1
head = head->next;
free(head->prev);
head->prev = NULL;
}
}else if(strcmp(tail->vegetableName,vegetableName)==0){
//pop tail //code optimization
//if(head == tail){
// //data 1
// free(head);
// head = tail = NULL;
//}else{
//data > 1
tail = tail->prev;
free(tail->next);
tail->next = NULL;
//}
}else{
//pop mid
struct Grocery *temp = head;
int isFound = 0;
while(temp != NULL){
if(strcmp(vegetableName,temp->vegetableName) == 0){
isFound = 1;
break;
}
temp = temp->next;
}
if(isFound == 1){
//kl ktmu, qta hapus
temp->next->prev = temp->prev;
temp->prev->next = temp->next;
free(temp);
}else{
printf("\nSorry, you vegetable is eaten by Zombie..\n");
getchar();
}
}
}
}

void popALL(){
struct Grocery *temp;
while(head!=NULL){
temp = head;
head=head->next;
free(temp);
}
head = tail = NULL;
}

void line(){
int i;
for(i=0;i<27;i++)
{
printf("-");
}
printf("\n");
}

void cetak(){
struct Grocery *temp = head;
line();
printf("|%-15s|%-9s|\n","Vegetable Name","Quantity");
while(temp){
line();
printf("|%-15s|%-9d|\n",temp->vegetableName,temp->qty);
temp = temp->next;
}
line();
}

void menu(){
printf("Happy Groceria\n");
printf("1. Add Stock\n");
printf("2. Buying\n");
printf("3. Exit\n");
printf("Input choice [1..3]: ");
}

void add(){
char vegeName[25];

do{
printf("Input Vegetable Name [3..24]: ");
gets(vegeName);
}while(strlen(vegeName) < 3 || strlen(vegeName) > 24 );

srand(time(NULL));
int qty;
qty = rand()%10+20;

int pos;
do{
printf("Input Position [1..%d]: ",jumlahData+1);
scanf("%d",&pos);
fflush(stdin);
}while(pos < 1 || pos > jumlahData+1);

push(vegeName,qty,pos);
jumlahData++;
}

void buying(){
char vegeName[25];
do{
printf("Input Vegename [3..24]: ");
gets(vegeName);
}while(strlen(vegeName) < 3 || strlen(vegeName) > 24);
pop(vegeName);
}

void clear(){
int i;
for(i=0;i<25;i++){
printf("\n");
}
}

int main(){
int switches;
do{
clear();
if(jumlahData != 0){
cetak();
}
menu();
scanf("%d",&switches);
fflush(stdin);
switch(switches){
case 1: add(); break;
case 2: buying(); break;
}
}while(switches != 3);
return 0;
}

NB : Bahan yang ditulis berdasarkan apa yang pernah saya pelajari dari dosen dan juga slide-slide powerpoint dari Binus University.


Binus University     Skyconnectiva

Code Stack

Stack dengan Linked List sebenarnya cara memakainya sama dengan membuat linked list biasa, hanya saja pada Stack masukkin data dan menghapus data dari tempat yang sama, kalau mau dari belakang ya push dan pop belakang dan begitu pula sebaliknya.(sesuai dengan prinsip nya LIFO)
Berikut ini code nya:


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

struct Facebook{
char nama[25];
int usia;
struct Facebook *next;
}*head,*tail;

void pushBelakang(char nama[], int usia){
struct Facebook *curr = (struct Facebook*) malloc(sizeof(struct Facebook));
strcpy(curr->nama,nama);
curr->usia = usia;
if(head == NULL){
head = tail = curr;
tail->next = NULL;
}else{
tail->next = curr;
tail = curr;
tail->next = NULL;
}
}

void line(){
int i;
for(i=0;i<33;i++){
printf("-");
}
printf("\n\n");
}

void cetak(){
struct Facebook *curr;
if(head != NULL){
line();
printf("%-25s|%-4s\n","Nama","Usia");
line();
for(curr=head;curr!=NULL;curr=curr->next){
printf("%-25s|%-4d\n",curr->nama, curr->usia);
}
line();
}
}

void popALL(){
struct Facebook *curr;
for(curr=head;curr!=NULL;curr=curr->next){
free(curr);
}
}

void clear(){
int i;
for(i=0;i<25;i++){
printf("\n");
}
}

void menu(){
printf("The FaceBook: 1990\n");
printf("1. Register\n");
printf("2. Abadon Data\n");
printf("3. Exit\n");
printf("Select Menu [1..3]: ");
}

void menu1(){
char name[25];
int age;
do{
printf("\nInput Name [3..24]: ");
gets(name);  //scanf("%[^\n]",name);
}while(strlen(name) < 3 || strlen(name) > 24);

do{
printf("Input Age <17 & >27: ");
scanf("%d",&age);
fflush(stdin);
}while(age >= 17 && age <=27);

pushBelakang(name,age);
}

void popBelakang(){
if(head == NULL){
system("color 0A");
printf("\nThere is no data yet\n");
getchar();
}else{
struct Facebook *curr = head;
if(head == tail){
//cuma ada 1 node;
head = tail = NULL;
printf("Data %s",curr->nama);
free(curr);
}else{
for(curr=head;curr->next != tail; curr=curr->next);
tail = curr;
printf("Data %s",curr->next->nama);
free(curr->next);
tail->next = NULL;
}
printf(" sudah dihapus\n");
getchar();
}

}

void menu2(){
popBelakang();
}

int main(){
int pilih;
do{
clear();
cetak();
menu();
scanf("%d",&pilih);
fflush(stdin);
switch(pilih){
case 1: menu1(); break;
case 2: menu2(); break;
}
}while(pilih != 3);
popALL();
return 0;
}

NB : Bahan yang ditulis berdasarkan apa yang pernah saya pelajari dari dosen dan juga slide-slide powerpoint dari Binus University .

Binus University     Skyconnectiva

Code Queue

Queue dengan Linked List sebenarnya cara memakainya sama dengan membuat linked list biasa, hanya saja pada queue masukkin data dari rear(push belakang) dan menghapus data dari front (pop depan)
Berikut ini code nya:


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

struct Facebook{
char nama[25];
int usia;
struct Facebook *next;
}*head,*tail;

void pushBelakang(char nama[], int usia){
struct Facebook *curr = (struct Facebook*) malloc(sizeof(struct Facebook));
strcpy(curr->nama,nama);
curr->usia = usia;
if(head == NULL){
head = tail = curr;
tail->next = NULL;
}else{
tail->next = curr;
tail = curr;
tail->next = NULL;
}
}

void line(){
int i;
for(i=0;i<33;i++){
printf("-");
}
printf("\n\n");
}

void cetak(){
struct Facebook *curr;
if(head != NULL){
line();
printf("%-25s|%-4s\n","Nama","Usia");
line();
for(curr=head;curr!=NULL;curr=curr->next){
printf("%-25s|%-4d\n",curr->nama, curr->usia);
}
line();
}
}

void popALL(){
struct Facebook *curr;
for(curr=head;curr!=NULL;curr=curr->next){
free(curr);
}
}

void clear(){
int i;
for(i=0;i<25;i++){
printf("\n");
}
}

void menu(){
printf("The FaceBook: 1990\n");
printf("1. Register\n");
printf("2. Abadon Data\n");
printf("3. Exit\n");
printf("Select Menu [1..3]: ");
}

void menu1(){
char name[25];
int age;
do{
printf("\nInput Name [3..24]: ");
gets(name);  //scanf("%[^\n]",name);
}while(strlen(name) < 3 || strlen(name) > 24);

do{
printf("Input Age <17 & >27: ");
scanf("%d",&age);
fflush(stdin);
}while(age >= 17 && age <=27);

pushDepan(name,age);
}

void popDepan(){
if(head == NULL){
system("color 0A");
printf("\nThere is no data yet\n");
getchar();
}else{
struct Facebook *curr = head;
if(head == tail){
//cuma ada 1 node;
head = tail = NULL;
printf("Data %s",curr->nama);
free(curr);
}else{
head = head->next;
printf("Data %s",curr->nama);
free(curr);
}
printf(" sudah dihapus\n");
getchar();
}
}

void menu2(){
popDepan();
}

int main(){
int pilih;
do{
clear();
cetak();
menu();
scanf("%d",&pilih);
fflush(stdin);
switch(pilih){
case 1: menu1(); break;
case 2: menu2(); break;
}
}while(pilih != 3);
popALL();
return 0;
}

NB : bahan yang ditulis berdasarkan apa yang pernah saya pelajari dari dosen dan juga slide-slide powerpoint dari  Binus University .

Binus University    skyconnectiva