Binary Search Tree Implementation

Contoh implementasi Binary Search Tree:

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

struct Node
{
int value;
Node *left, *right;
};

Node *root;

Node *createNode(int value)
{
Node* node = (Node*)malloc(sizeof(Node));
node->value = value;
node->left = node->right = NULL;
return node;
}

Node *insert(Node *root, int value)
{
if (!root)
return createNode(value);

if (root->value > value)
root->left = insert(root->left, value);
else if (root->value < value)
root->right = insert(root->right, value);

return root;
}

Node* remove(Node *root, int value)
{
if (!root)
return root;

if (root->value > value)
root->left = remove(root->left, value);
else if (root->value < value)
root->right = remove(root->right, value);
else if (root->value == value)
{
if (root->left == NULL || root->right == NULL)
{
Node *node = root->left != NULL ? root->left : root->right;

if (node)
*root = *node;
else
free(node);
}
else
{
Node* node = root->left;
while (node->right)
node = node->right;
root->left = remove(root->left, node->value);
}
}

return root;
}

void printPreOrder(Node *root) {
if (root) {
printf("%d ", root->value);
printPreOrder(root->left);
printPreOrder(root->right);
}
}

void printInOrder(Node *root) {
if (root) {
printInOrder(root->left);
printf("%d ", root->value);
printInOrder(root->right);
}
}

void printPostOrder(Node *root) {
if (root) {
printPostOrder(root->left);
printPostOrder(root->right);
printf("%d ", root->value);
}
}

int main() {
root = insert(root, 4);
root = insert(root, 5);
root = insert(root, 3);
root = remove(root, 3);

printPreOrder(root);
printInOrder(root);
printPostOrder(root);
}