There are Six operation which we can perform on Binary search Tree.
Binary search tree operations
Search
Searches an element in a tree.
Insert
Inserts an element in a tree.
Pre order Traversal
Traverse a tree in a pre-order manner means first to traverse the Root node, then the Left node, and at last Right node.
Traverse format : (Root, Left, Right)
Pre order Traversal Program in C
[c]
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left;
struct node *right;
};
struct node *createNode(int item)
{
struct node *newNode = (struct node *)malloc(sizeof(struct node));
newNode->key = item;
newNode->left = newNode->right = NULL;
return newNode;
}
struct node *insertNode(struct node* node, int key)
{
if (node == NULL) return createNode(key);
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}
struct node* search(struct node* root, int key)
{
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
void preOrder(struct node *root)
{
if (root != NULL)
{
printf("%d \n", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
struct node *root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
printf("Pre-Order Tree Traversal\n");
preOrder(root);
return 0;
}
[/c]
In order Traversal
Traverse a tree in an in-order manner means first to traverse the Left node, then the root node, and then at last Right node.
Traverse format : (Left, Root, Right)
In order Traversal Program in C
[c]
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left;
struct node *right;
};
struct node *createNode(int item)
{
struct node *newNode = (struct node *)malloc(sizeof(struct node));
newNode->key = item;
newNode->left = newNode->right = NULL;
return newNode;
}
struct node *insertNode(struct node* node, int key)
{
if (node == NULL) return createNode(key);
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}
void inOrder(struct node *root)
{
if (root != NULL)
{
inOrder(root->left);
printf("%d \n", root->key);
inOrder(root->right);
}
}
int main()
{
struct node *root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
printf("In-Order Tree Traversal\n");
inOrder(root);
return 0;
}
[/c]
Post-order Traversal
Traverse a tree in a post-order manner means the first traverse left node, then the right node, and the last root node.
Traverse format : (Left, Right, Root)
[c]
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left;
struct node *right;
};
struct node *createNode(int item)
{
struct node *newNode = (struct node *)malloc(sizeof(struct node));
newNode->key = item;
newNode->left = newNode->right = NULL;
return newNode;
}
struct node *insertNode(struct node* node, int key)
{
if (node == NULL) return createNode(key);
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}
struct node* search(struct node* root, int key)
{
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
void postOrder(struct node *root)
{
if (root != NULL)
{
postOrder(root->left);
postOrder(root->right);
printf("%d \n", root->key);
}
}
int main()
{
struct node *root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
printf("Post-Order Tree Traversal\n");
postOrder(root);
return 0;
}
[/c]
C Program to implement Insertion and searching in binary search tree
[c]
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left;
struct node *right;
};
struct node *createNode(int item)
{
struct node *newNode = (struct node *)malloc(sizeof(struct node));
newNode->key = item;
newNode->left = newNode->right = NULL;
return newNode;
}
struct node *insertNode(struct node* node, int key)
{
if (node == NULL) return createNode(key);
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}
struct node* search(struct node* root, int key)
{
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
int main()
{
struct node *root = NULL;
root = insertNode(root, 60);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 50);
insertNode(root, 70);
insertNode(root, 90);
insertNode(root, 80);
struct node *result = search(root, 90);
printf("Search Value %d is founded",result->key);
return 0;
}
[/c]
Output:
[wpusb]