Searching and sorting arrays in C / C++ How to use Binary Search Tree (BST) in C / C++
In this tutorial, we will learn about how to use Binary Search Tree in C / C++ and its working with the help of some examples. This is one of the basic knowledge in C / C++ programming language, so please learn it carefully.
Before learning about Binary Search Tree in C / C++, let's learn about binary tree data structure.
What is a Binary Tree in C / C++?
Let us take a real example for you to understand the tree structure.
Example: The tree structure is similar to how we organize folders in a computer. Outside is the parent folder, inside contains sub-folders.
A binary tree gathers many nodes together. Each node consists of three components:
- Data: The value of a node is stored in a binary search tree.
- Left pointer: This is a pointer, it points to the binary tree on the left.
- Right pointer: This is a pointer, it points to the binary tree on the right.
What is a Binary Search Tree in C / C++?
The nodes in the binary search tree must comply with the following rules:
- The node to the left is always smaller than the node immediately above it.
- The node to the right is always larger than the node immediately above it.
How does a Binary Search Tree in C / C++ work?
To illustrate how binary search tree in C / C++ work. We have an example below.
Example: Suppose we have a binary search tree. Now we will insert nodes with values 27, 14, 35, 10, 19, 31, 42 into the binary search tree. Then the storage process is done as follows.
Explain:
- The number 27 is stored in the tree, this is the
keyused to compare with the following elements. - The number 14 is compared with the number 27 (key). Since
14 < 27, the number 14 is stored to the left of 27. - The number 35 is compared with the number 27 (key). Since
35 > 27, the number 35 is stored to the right of 27. 10 < 27and10 < 14. So 10 is stored to the left of 14.19 < 27and19 > 14. So 19 is stored to the right of 14.31 > 27and31 < 35. So 31 is stored to the left of 35.42 < 27and42 > 35. So 42 is stored to the right of 35.
Insert node to Binary Search Tree in C / C++
Before insert a new node to the binary search tree in C / C++. We need to create the data structure of the binary search tree first.
struct node
{
int data;
struct node *pLeft;
struct node *pRight;
};
/*Initialize a binary search tree*/
void Initialize(TREE &t)
{
t = NULL;
}To insert a new node to the binary search tree we have two cases.
- Case 1: The binary search tree is empty, then the newly added node is the
key. - Case 2: The binary search tree already has elements, then we need to compare it with the
keyto store the new node.
void InsertNode(TREE &t, int x)
{
if (t == NULL)
{
NODE *p = new NODE;
p->data = x;
p->pLeft = NULL;
p->pRight = NULL;
t = p;
}
{
if (t->data > x)
{
InsertNode(t->pLeft, x);
}
else if (t->data < x)
{
InsertNode(t->pRight, x);
}
}
}How to traverse Binary Search Tree in C / C++
To traverse the binary search tree in C / C++, we have 6 ways to do it. Each way will give us a different result.
Traversing the NLR (Node - Left - Right) binary search tree in C/C++:
void Traverse_NLR(TREE t)
{
if (t != NULL)
{
cout << t->data << " ";
Traverse_NLR(t->pLeft);
Traverse_NLR(t->pRight);
}
}Traversing the NRL (Node - Right - Left) binary search tree in C/C++:
void Traverse_NRL(TREE t)
{
if (t != NULL)
{
cout << t->data << " ";
Traverse_NRL(t->pRight);
Traverse_NRL(t->pLeft);
}
}Traversing the LNR (Left - Node - Right) binary search tree in C/C++:
void Traverse_LNR(TREE t)
{
if (t != NULL)
{
Traverse_LNR(t->pLeft);
cout << t->data << " ";
Traverse_LNR(t->pRight);
}
}To traverse a binary search tree in this way, the result will be a list of elements sorted in ascending order.
Traversing the RNL (Right - Node - Left) binary search tree in C/C++:
void Traverse_RNL(TREE t)
{
if (t != NULL)
{
Traverse_RNL(t->pRight);
cout << t->data << " ";
Traverse_RNL(t->pLeft);
}
}To traverse a binary search tree in this way, the result will be a list of elements sorted in descending order.
Traversing the LRN (Left - Right - Node) binary search tree in C/C++:
void Traverse_LRN(TREE t)
{
if (t != NULL)
{
Traverse_LRN(t->pLeft);
Traverse_LRN(t->pRight);
cout << t->data << " ";
}
}Traversing the RLN (Right - Left - Node) binary search tree in C/C++:
void Traverse_RLN(TREE t)
{
if (t != NULL)
{
Traverse_RLN(t->pRight);
Traverse_RLN(t->pLeft);
cout << t->data << " ";
}
}Remove node from Binary Search Tree in C / C++
To remove a node from the binary search tree, we have three cases as follows:
- The node to be deleted is the leaf node.
- The node to be deleted lies has a single child node.
- The node to be deleted has two children.
Case 1: The node to be deleted is the leaf node.
In this case, we just need to delete the node without taking any further action.
Case 2: The node to be deleted lies has a single child node.
- Replace that node with its child node.
- Remove the child node from its original position.
Case 3: The node to be deleted has two children.
- Get the inorder successor of that node.
- Replace the node with the inorder successor.
- Remove the in order successor from its original position.
Below is a function that deletes any node that we have written. You can refer.
void AlternativeNode(TREE &X, TREE &Y)
{
if (Y->pLeft != NULL)
{
AlternativeNode(X, Y->pLeft);
}
else
{
X->data = Y->data;
X = Y;
Y = Y->pRight;
}
}
void RemoveNode(TREE &t, int data)
{
if (t == NULL)
{
return;
}
else
{
if (data < t->data)
{
RemoveNode(t->pLeft, data);
}
else if (data > t->data)
{
RemoveNode(t->pRight, data);
}
else
{
NODE *X = t;
if (t->pLeft == NULL)
{
t = t->pRight;
}
else if (t->pRight == NULL)
{
t = t->pLeft;
}
else
{
AlternativeNode(X, t->pRight);
}
delete X;
}
}
}Example of Binary Search Tree in C / C++
Here, we have an example that illustrates how to use binary search tree in C / C++. The program includes all the operations mentioned above.
#include<iostream>
using namespace std;
struct node
{
int data;
struct node *pLeft;
struct node *pRight;
};
typedef struct node NODE;
typedef NODE* TREE;
void Initialize(TREE &t)
{
t = NULL;
}
void InsertNode(TREE &t, int x)
{
if (t == NULL)
{
NODE *p = new NODE;
p->data = x;
p->pLeft = NULL;
p->pRight = NULL;
t = p;
}
else
{
if (t->data > x)
{
InsertNode(t->pLeft, x);
}
else if (t->data < x)
{
InsertNode(t->pRight, x);
}
}
}
void Traverse_NLR(TREE t)
{
if (t != NULL)
{
cout << t->data << " ";
Traverse_NLR(t->pLeft);
Traverse_NLR(t->pRight);
}
}
void Traverse_NRL(TREE t)
{
if (t != NULL)
{
cout << t->data << " ";
Traverse_NRL(t->pRight);
Traverse_NRL(t->pLeft);
}
}
void Traverse_LNR(TREE t)
{
if (t != NULL)
{
Traverse_LNR(t->pLeft);
cout << t->data << " ";
Traverse_LNR(t->pRight);
}
}
void Traverse_RNL(TREE t)
{
if (t != NULL)
{
Traverse_RNL(t->pRight);
cout << t->data << " ";
Traverse_RNL(t->pLeft);
}
}
void Traverse_LRN(TREE t)
{
if (t != NULL)
{
Traverse_LRN(t->pLeft);
Traverse_LRN(t->pRight);
cout << t->data << " ";
}
}
void Traverse_RLN(TREE t)
{
if (t != NULL)
{
Traverse_RLN(t->pRight);
Traverse_RLN(t->pLeft);
cout << t->data << " ";
}
}
void AlternativeNode(TREE &X, TREE &Y)
{
if (Y->pLeft != NULL)
{
AlternativeNode(X, Y->pLeft);
}
else
{
X->data = Y->data;
X = Y;
Y = Y->pRight;
}
}
void RemoveNode(TREE &t, int data)
{
if (t == NULL)
{
return;
}
else
{
if (data < t->data)
{
RemoveNode(t->pLeft, data);
}
else if (data > t->data)
{
RemoveNode(t->pRight, data);
}
else
{
NODE *X = t;
if (t->pLeft == NULL)
{
t = t->pRight;
}
else if (t->pRight == NULL)
{
t = t->pLeft;
}
else
{
AlternativeNode(X, t->pRight);
}
delete X;
}
}
}
int main()
{
TREE t;
Initialize(t);
int n, k, x;
cout<<"Enter the number of elements in the tree: ";
cin>>n;
cout<<"Enter values for the elements.\n";
for(int i = 1; i <= n; i++){
cout<<"The value of element "<<i<<": ";
cin>>k;
InsertNode(t,k);
}
cout<<"\nTraversing the NLR: ";
Traverse_NLR(t);
cout<<"\nTraversing the NRL: ";
Traverse_NRL(t);
cout<<"\nTraversing the LNR: ";
Traverse_LNR(t);
cout<<"\nTraversing the RNL: ";
Traverse_RNL(t);
cout<<"\nTraversing the LRN: ";
Traverse_LRN(t);
cout<<"\nTraversing the RLN: ";
Traverse_RLN(t);
cout<<"\n\nEnter the value to remove: ";
cin>>x;
RemoveNode(t, x);
cout<<"\nElements in the tree after deletion: ";
Traverse_NLR(t);
cout<<"\n-------------------------------\n";
cout<<"This program is posted at learnnc.com";
return 0;
}Output:
