📋 Daftar Isi
Pada artikel kali ini akan dibahas mengenai implementasi binary search tree. Apabila sebelumnya kita telah memahami cara mengimplementasikan binary tree, akan terdapat perbedaan jika dibandingkan dengan binary search tree karena pada binary search tree terdapat urutan.
Fungsi Insert Node
struct node* insert(struct node* root, int newData)
{
if(root == NULL)
{
root = newNode(newData);
}
else
{
int is_left = 0;
struct node *cursor = root;
struct node *prev = NULL;
while(cursor != NULL)
{
prev = cursor;
if(newData < cursor->data)
{
is_left = 1;
cursor = cursor->left;
}
else if(newData > cursor->data)
{
is_left = 0;
cursor = cursor->right;
}
}
if(is_left == 1)
prev->left = newNode(newData);
else
prev->right = newNode(newData);
}
return root;
};
Fungsi Delete Node
struct node *delete_node(struct node *root, int deletedData)
{
if(root == NULL)
return;
struct node *cursor;
if(deletedData > root->data)
root->right = delete_node(root->right, deletedData);
else if(deletedData < root->data)
root->left = delete_node(root->left, deletedData);
else
{
//1 CHILD
if(root->left == NULL)
{
cursor = root->right;
free(root);
root = cursor;
}
else if(root->right == NULL)
{
cursor = root->left;
free(root);
root = cursor;
}
//2 CHILD NODE
else
{
cursor = root->right;
while(cursor->left != NULL)
{
cursor = cursor->left;
}
root->data = cursor->data;
root->right = delete_node(root->right, cursor->data);
}
}
return root;
};
Jika yang dihapus adalah leaf node
Jika yang dihapus adalah 1 child node
Jika yang dihapus adalah 2 child node, cari minimum di subtree kanan atau cari maksimum di subtree kiri untuk meggantikan node tersebut
Fungsi Search Node
void search_node(struct node *root, int data)
{
struct node *cursor = root;
while(cursor->data != data)
{
if(cursor != NULL)
{
if(data > cursor->data)
{
cursor = cursor->right;
}
else
{
cursor = cursor->left;
}
if(cursor == NULL)
{
printf("\nNode %d tidak ditemukan", data);
}
break;
}
}
printf("\nNode %d ditemukan", data);
return;
}
Source Code Lengkap
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *newNode(int data)
{
struct node *node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
};
void displayPreorder(struct node* node);
void displayInorder(struct node* node);
void displayPostorder(struct node* node);
struct node* insert(struct node* root, int newData);
void search_node(struct node *root, int data);
struct node *delete_node(struct node *root, int deletedData);
int main()
{
struct node* root = newNode(9);
/*root->left = newNode(3);
root->left->right = newNode(1);
root->left->left = newNode(6);
root->left->right->right = newNode(4);
root->left->right->left = newNode(7);
root->right = newNode(10);
root->right->left = newNode(14);
root->right->left->right = newNode(13);*/
//another version
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
printf("\nIsi dari binary tree (Pre-Order) adalah \n");
displayPreorder(root);
printf("\nIsi dari binary tree (In-Order) adalah \n");
displayInorder(root);
printf("\nIsi dari binary tree (Post-Order) adalah \n");
displayPostorder(root);
/*
search_node(root,6);
search_node(root,100);
root = delete_node(root, 13);
root = delete_node(root, 3);
printf("\nIsi dari binary tree (Pre-Order) adalah \n");
displayPreorder(root);
printf("\nIsi dari binary tree (In-Order) adalah \n");
displayInorder(root);
printf("\nIsi dari binary tree (Post-Order) adalah \n");
displayPostorder(root);
search_node(root,3);
search_node(root,13);
*/
return 0;
}
void displayPreorder(struct node* node)
{
if (node == NULL)
return;
printf("%d ", node->data); //root
displayPreorder(node->left); //subtree kiri
displayPreorder(node->right); //subtree kanan
}
void displayInorder(struct node* node)
{
if (node == NULL)
return;
displayInorder(node->left); //subtree kiri
printf("%d ", node->data); //akar
displayInorder(node->right); //subtree kanan
}
void displayPostorder(struct node* node)
{
if (node == NULL)
return;
displayPostorder(node->left); //subtree kiri
displayPostorder(node->right); //subtree kanan
printf("%d ", node->data); //root
}
struct node* insert(struct node* root, int newData)
{
if(root == NULL)
{
root = newNode(newData);
}
else
{
int is_left = 0;
struct node *cursor = root;
struct node *prev = NULL;
while(cursor != NULL)
{
prev = cursor;
if(newData < cursor->data)
{
is_left = 1;
cursor = cursor->left;
}
else if(newData > cursor->data)
{
is_left = 0;
cursor = cursor->right;
}
}
if(is_left == 1)
prev->left = newNode(newData);
else
prev->right = newNode(newData);
}
return root;
};
void search_node(struct node *root, int data)
{
struct node *cursor = root;
while(cursor->data != data)
{
if(cursor != NULL)
{
if(data > cursor->data)
{
cursor = cursor->right;
}
else
{
cursor = cursor->left;
}
if(cursor == NULL)
{
printf("\nNode %d tidak ditemukan", data);
}
break;
}
}
printf("\nNode %d ditemukan", data);
return;
}
struct node *delete_node(struct node *root, int deletedData)
{
if(root == NULL)
return;
struct node *cursor;
if(deletedData > root->data)
root->right = delete_node(root->right, deletedData);
else if(deletedData < root->data)
root->left = delete_node(root->left, deletedData);
else
{
//1 CHILD
if(root->left == NULL)
{
cursor = root->right;
free(root);
root = cursor;
}
else if(root->right == NULL)
{
cursor = root->left;
free(root);
root = cursor;
}
//2 CHILD NODE
else
{
cursor = root->right;
while(cursor->left != NULL)
{
cursor = cursor->left;
}
root->data = cursor->data;
root->right = delete_node(root->right, cursor->data);
}
}
return root;
};
Output
Materi Lengkap
Silakan baca juga beberapa artikel menarik kami tentang Tree (Bagian 1), daftar lengkapnya adalah sebagai berikut.
