LATEST

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++?

A binary tree is a dynamic data structure, it is used to store data in the form of a tree.

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.

bst 01 PNG

What is a Binary Search Tree in C / C++?

A binary search tree is a special type of binary tree. So a binary search tree has all the components of a binary tree.

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.

bst 02 PNG

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.

bst 03 PNG

Explain:

  1. The number 27 is stored in the tree, this is the key used to compare with the following elements.
  2. The number 14 is compared with the number 27 (key). Since 14 < 27, the number 14 is stored to the left of 27.
  3. The number 35 is compared with the number 27 (key). Since 35 > 27, the number 35 is stored to the right of 27.
  4. 10 < 27 and 10 < 14. So 10 is stored to the left of 14.
  5. 19 < 27 and 19 > 14. So 19 is stored to the right of 14.
  6. 31 > 27 and 31 < 35. So 31 is stored to the left of 35.
  7. 42 < 27 and 42 > 35. So 42 is stored to the right of 35.
Note: The node with a value smaller than the node immediately above it will be saved to the left. Otherwise, if it is larger, it will be saved to the right.

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 key to 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.

bst 04 PNG

Case 2: The node to be deleted lies has a single child node.

  1. Replace that node with its child node.
  2. Remove the child node from its original position.

bst 05 PNG

Case 3: The node to be deleted has two children.

  1. Get the inorder successor of that node.
  2. Replace the node with the inorder successor.
  3. Remove the in order successor from its original position.

bst 06 PNG

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:

bst 07 PNG

Cùng chuyên mục:

How to use multidimensional Arrays in C / C++

How to use multidimensional Arrays in C / C++

Searching and sorting arrays in C / C++

Searching and sorting arrays in C / C++

How to use arrays in C / C++

How to use arrays in C / C++

How to use goto statement in C / C++

How to use goto statement in C / C++

How to use switch...case statement in C / C++

How to use switch...case statement in C / C++

How to use continue statement in C / C++

How to use continue statement in C / C++

How to use break statement in C / C++

How to use break statement in C / C++

How to use if - else statement in C / C++

How to use if - else statement in C / C++

How to use do while loop in C / C++

How to use do while loop in C / C++

How to use while loop in C / C++

How to use while loop in C / C++

How to use for loop in C / C++

How to use for loop in C / C++

Top