Step-by-Step Guide to Binary Tree Implementation in C++
Implementing full and complete binary trees in C++ programs
What is a Binary tree?
A binary tree is tree data structure in which each node can have at most two child nodes referred to as the left and right child.
The two types of binary trees on which we are going to focus today are full and complete binary tree.
Full binary tree
A full binary tree is a type of binary tree in which each node except the leaf node has exactly two children.
Complete binary tree
A type of binary tree in which each level is completely filled except possibly for the last level which is filled from left to right.
In simple words, starting from left whenever any node has no child either left or right i.e. there is a break, any other node after it should not have any child at all.
Now we will implement a tree data structure using arrays in C++.
Working of each function is explained after the code.
// Necessary header files
#include <iostream>
#include <cmath>
using namespace std;
// class named BinaryTree
class BinaryTree
{
private:
// total size of the array / binary tree
int size;
// to count the total number of nodes in binary tree
int noOfElements;
/* to check if a certain node is empty or filled. It is initialized
by -1 to show availability and whenever an element is inserted the
-1 at that particular index is changed to any other number showing
it is occupied */
int *avail;
// to store the nodes in format of array
int *data;
/* Helper function of the displayPreOrder function to print the
nodes of the tree according to preorder traversal */
void displayPreOrder(int i)
{
if (i < size && avail[i] != -1)
{
cout << data[i] << " ";
displayPreOrder((i + i) + 1);
displayPreOrder((i + i) + 2);
}
}
/* Helper function of the displayInOrder function to print the
nodes of the tree according to inorder traversal */
void displayInOrder(int i)
{
if (i < size && avail[i] != -1)
{
displayInOrder((i + i) + 1);
cout << data[i] << " ";
displayInOrder((i + i) + 2);
}
}
/* Helper function of the displayPostOrder function to print the
nodes of the tree according to postorder traversal */
void displayPostOrder(int i)
{
if (i < size && avail[i] != -1)
{
displayPostOrder((i + i) + 1);
displayPostOrder((i + i) + 2);
cout << data[i] << " ";
}
}
/* If the array gets filled this function can be called to increase
the size of the original array */
void resize()
{
int newSize = size + 15;
int *newData = new int[newSize];
int *newAvail = new int[newSize];
for (int i = 0; i < size; i++)
{
newAvail[i] = avail[i];
newData[i] = data[i];
}
for (int i = size; i < newSize; i++)
{
newAvail[i] = -1;
}
data = newData;
avail = newAvail;
size = newSize;
}
public:
/* Default constructor to initialize all the data members of class
BinaryTree */
BinaryTree()
{
size = 10;
noOfElements = 0;
avail = new int[size];
for (int i = 0; i < size; i++)
{
avail[i] = -1;
}
data = new int[size];
}
// Constructor to initialize the data members
BinaryTree(int size)
{
if (size < 10)
{
this->size = 10;
}
else
{
this->size = size;
}
data = new int[this->size];
noOfElements = 0;
avail = new int[this->size];
for (int i = 0; i < size; i++)
{
avail[i] = -1;
}
}
/* Insert function to insert an element at the first non-filled
index of array */
void insertElement(int element)
{
if (noOfElements == size)
{
resize();
}
data[noOfElements] = element;
avail[noOfElements] = 5;
noOfElements++;
}
/* This function inserts a left child of the element provided. If the
element provided is not found or if its left child already exists it
returns false */
bool insertLeftChild(int parent, int child)
{
int index = -1;
for (int i = 0; i < noOfElements; i++)
{
if (data[i] == parent)
{
index = i;
break;
}
}
if (index == -1)
{
cout << "Element not found" << endl;
return false;
}
else
{
int leftChild = 2 * index + 1;
if (leftChild >= size)
{
resize();
}
if (avail[leftChild] != -1)
{
cout << "Left already exists" << endl;
return false;
}
else
{
data[leftChild] = child;
avail[leftChild] = 5;
noOfElements++;
return true;
}
}
}
/* This function inserts a right child of the element provided. If
the element provided is not found or if its right child already
exists it returns false */
bool insertRightChild(int parent, int child)
{
int index = -1;
for (int i = 0; i < noOfElements; i++)
{
if (data[i] == parent)
{
index = i;
break;
}
}
if (index == -1)
{
cout << "Parent not found" << endl;
return false;
}
else
{
int rightChild = 2 * index + 2;
if (rightChild >= size)
{
resize();
}
if (avail[rightChild] != -1)
{
cout << "Right already exists" << endl;
return false;
}
else
{
data[rightChild] = child;
avail[rightChild] = 5;
noOfElements++;
return true;
}
}
}
/* This function deletes the provided element by swapping the given
element with the last element in the array and then deletes the last
element. If the provided element is not found, it returns false */
bool deleteElement(int element)
{
int index = -1;
for (int i = 0; i < noOfElements; i++)
{
if (data[i] == element)
{
index = i;
break;
}
}
if (index == -1)
{
cout << "Element not found" << endl;
return false;
}
else
{
int lastNodeIndex = size - 1;
for (int i = size - 1; i >= 0; i--)
{
if (avail[i] != -1)
{
lastNodeIndex = i;
break;
}
}
data[index] = data[lastNodeIndex];
avail[lastNodeIndex] = -1;
noOfElements--;
return true;
}
}
/* This display function prints the nodes of each level in a new line
and if a certain node is empty, it prints _ at its place */
void display_Level()
{
int level = 0;
int count = 0;
int nodesInCurrentLevel = 1;
for (int i = 0; i < size; i++)
{
if (avail[i] != -1)
{
cout << data[i] << " ";
}
else
{
cout << "_ ";
}
count++;
if (count == nodesInCurrentLevel)
{
cout << endl;
level++;
nodesInCurrentLevel = pow(2, level);
count = 0;
}
}
cout<<endl;
}
// displays the contents of the tree using pre-order traversal
void display_PreOrder()
{
displayPreOrder(0);
cout << endl;
}
// displays the contents of the tree using in-order traversal
void display_InOrder()
{
displayInOrder(0);
cout << endl;
}
// displays the contents of the tree using post-order traversal
void display_PostOrder()
{
displayPostOrder(0);
cout << endl;
}
// returns the total number of nodes in the tree
int totalElements()
{
return noOfElements;
}
// deletes the allocated memory from the heap
~BinaryTree()
{
delete[] avail;
delete[] data;
}
};
Working of each function
insertElement
functionThis function first checks if the array is full or not. If it is full, it then calls the resize function to increase the size of original array making space for the new element. It finds the first available space in the array and inserts that element there. It also increments the count of
noOfElements
by 1.resize
functionThis function creates two pointers to new arrays namely
newData
andnewAvail
and copies the elements of the originaldata
andavail
into them respectively. It finally assignsnewData
andnewAvail
todata
andavail
respectively asnewData
andnewAvail
have no scope beyond this function. Note that it copies the originalavail
tonewAvail
and then initializes the remainingnewAvail
with -1 to maintain the functioning ofavail
.insertLeftChild
functionThis function takes two arguments parent and child. First a variable named
index
is initialized with the value -1 and then a for loop is used to iterate through the whole array to find the parent element and its index is stored in index variable. If after the loop terminates and value of index is still -1 it means that element is not present in the tree and the function returns.If the parent element is found, then we find its left index so that we can insert the child element there. We do this by using the formula
2*index+1
which takes to the index which is supposed to be the left child of the parent element. If it is out of bounds, we resize the array and then we check if it's available by checking the value ofavail
at that index. If it is not -1 it means it is already occupied and we return false saying that left child of the given parent element already exists. Otherwise, we insert the child element at that index and increment the count ofnoOfElements
and change itsavail
value to anything other than -1.insertRightChild
functionThis function takes two arguments parent and child. First a variable named
index
is initialized with the value -1 and then a for loop is used to iterate through the whole array to find the parent element and its index is stored in index variable. If after the loop terminates and value of index is still -1 it means that element is not present in the tree and the function returns.If the parent element is found, then we find its right index so that we can insert the child element there. We do this by using the formula
2*index+2
which takes to the index which is supposed to be the right child of the parent element. If it is out of bounds, we resize the array and then we check if it's available by checking the value ofavail
at that index. If it is not -1 it means it is already occupied and we return false saying that right child of the given parent element already exists. Otherwise, we insert the child element at that index and increment the count ofnoOfElements
and change itsavail
value to anything other than -1.deleteElement
functionThis function only takes a single argument which is the element that the user wants to delete. First a variable named
index
is initialized with the value -1 and then a for loop is used to iterate through the whole array to find the desired element and its index is stored in index variable. If after the loop terminates and value of index is still -1 it means that element is not present in the tree and the function returns.If the element is found, it then proceeds to find the last element of the tree by using a for loop that starts from end and the first element it finds which has avail value other than -1 it stores it into a variable called
lastNodeIndex
. It then places the value of thislastNodeIndex
in place of the element that needs to be deleted and changes the avail value oflastNodeIndex
to -1 showing that this particular index is once again available for insertion.noOfElements
is also decremented by 1.display_Level function
This function finds the number of nodes in each level by using the formula
$$2^n$$
where n is the level or height and stores them in variable called
nodesInCurrentLevel
. A variable namedcount
is also initialized to 0 and whenever a value or _ is printed its value is incremented and when its value becomes equal tonodesInCurrentLevel
it means a level is finished so a new line is printed, and value of count is again assigned zero value to maintain correct count of the nodes in new level. Nodes in the next level are found by using the same formula but the value of n is increased by 1.display_PreOrder
functionIt traverses the tree in pre order fashion and prints the value in that order. It does so by using the VLR principle which means
Visit the current node.
Go to the left subtree.
Go to the right subtree.
display_InOrder
functionIt traverses the tree in in order fashion and prints the value in that order. It does so by using the LVR principle which means
Go to the left subtree.
Visit the current node.
Go to the right subtree.
display_PostOrder
functionIt traverses the tree in post order fashion and prints the value in that order. It does so by using the LRV principle which means
Go to the left subtree.
Go to the right subtree.
Visit the current node.
totalElements
functionReturns the total number of nodes in the tree.
I hope you found this detailed post on binary trees informative. If you have any questions or reviews comment them. I will answer to all of them.