Binary Tree Traversal And Implementation In C++
Data Structure for Trees
The Binary tree is the data structure which follows the tree like structure. Each node in the binary tree holds the data and two child pointers. One child pointer points to left child and another pointer points to the right child. In order to implement efficient search data are inserted in the binary tree in a manner that nodes in the left part of the subtree are less than the data in parent node and the data in right subtree are greater than the data in the parent node.
The data stored in the binary tree are traversed in three methodologies
- Preorder traversal
- Inorder traversal
- Postorder traversal
Algorithm for the Preorder Traversal from root node:
- Visit the root
- Traverse the left sub tree
- Traverse the right sub tree
Algorithm for the Inorder Traversal from root node:
- Traverse the left sub tree
- Visit the root
- Traverse the right sub tree
Algorithm for the Preorder Traversal from root node:
- Traverse the left sub tree
- Traverse the right sub tree
- Visit the root
The program stores the structure of the Binary Tree Node in the BTNode class. The BinaryTree class performs the binary tree implementation like inserting data into the binary tree, preorder traversal, inorder traversal and postorder traversal of the binary tree. A Driver program is written which acts like the controller for the execution of the program. The driver program displays the menu and based on the user choice specific operation is carried out.
Coding:
BTNode.h
#ifndef BTNODE_H
#define BTNODE_H
#include
// BTNode defines structure of each node in the Binary Tree
class BTNode{
public:
// constructor of the class
BTNode(int);
// accessor of data
int getData();
// accessor of left child
BTNode *getLeftChild();
// accessor of right child
BTNode *getRightChild();
// mutuator for left child
void setLeftChild(BTNode *);
// mutuator for right child
void setRightChild(BTNode *);
private:
// variable data is used to store the data
int data;
// pointer to the left child
BTNode *leftChild;
// pointer to the right child
BTNode *rightChild;
#endif // BTNODE_H
BTNode.cpp
#include “BTNode.h”
// constructor of the BTNode
BTNode::BTNode(int data){
// iniitalize the fields
this->data=data;
this->leftChild=NULL;
this->rightChild=NULL;
// accessor of data
int BTNode::getData(){
return data;
// accessor of left child
BTNode *BTNode::getLeftChild(){
return leftChild;
// accessor of right child
BTNode *BTNode::getRightChild(){
return rightChild;
// mutuator for left child
void BTNode::setLeftChild(BTNode *child){
leftChild=child;
// mutuator for right child
void BTNode::setRightChild(BTNode *child){
rightChild=child;
BinaryTree.h
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include
#include “BTNode.h
// This class provides the definition for Binary tree to be implemented
class BinaryTree
public:
// constructor of the class
BinaryTree();
// insert data in to the binary tree
void insert(int);
// traverse the tree in preorder
Preorder Traversal of Binary Tree
void preOrder();
// traverse the tree in inorder
void inOrder();
// traverse the tree in postorder
void postOrder();
protected
private:
BTNode *root;
void preOrder(BTNode *);
void inOrder(BTNode *);
void postOrder(BTNode *);
#endif // BINARYTREE_H
BinaryTree.cp
#include “BinaryTree.h”
using namespace std;
// constructor of the class
BinaryTree::BinaryTree()
root=NULL;
// insert() is used to insert data in to the binary tree
void BinaryTree::insert(int data){
//create memory for the binary node
BTNode *newNode=new BTNode(data);
//check if the root is null
if(root==NULL){
// make the new node as the root of the tree
root=newNode
else{
BTNode *current=root;
BTNode *parent=NULL;
bool isLeft=false;
// traverse the tree until the valid position to place node is located
while(current!=NULL){
parent=current;
// as per the algorithm the data in left sub tree are less than the parent node
// and the data in right subtree are greater than the parent node
if(current->getData()>=data){
// notifies whether the last traversal was made left
isLeft=true;
current=current->getLeftChild();
else{
// notifies whether the last traversal was made right
isLeft=false;
current=current->getRightChild();
// if the last traversal was made left then add the new node to the left of the parent
if(isLeft)
parent->setLeftChild(newNode);
else
parent->setRightChild(newNode); // make the new node as the right child of the parent
// traverse the tree in preorder
void BinaryTree::preOrder(){
preOrder(root);//calls the recursive function to traverse the tree in preorder
// traverse the tree in inorder
void BinaryTree::inOrder(){
inOrder(root);//calls the recursive function to traverse the tree in inorder
// traverse the tree in postorder
void BinaryTree::postOrder(){
postOrder(root);//calls the recursive function to traverse the tree in postorder
// private recursive helper function to traverse the tree in preorder
void BinaryTree::preOrder(BTNode *parent){
//check if the parent node is not null
if(parent!=NULL){
// Display the current node data
cout<getData()<<” “;
// traverse the left child of current node
preOrder(parent->getLeftChild());
// traverse the right child of current node
preOrder(parent->getRightChild());
// private recursive helper function to traverse the tree in inorder
void BinaryTree::inOrder(BTNode *parent){
//check if the parent node is not null
if(parent!=NULL){
// traverse the left child of current node
inOrder(parent->getLeftChild());
// Display the current node data
cout<getData()<<” “;
// traverse the right child of current node
inOrder(parent->getRightChild());
// private recursive helper function to traverse the tree in postorder
void BinaryTree::postOrder(BTNode *parent){
//check if the parent node is not null
if(parent!=NULL){
// traverse the left child of current node
postOrder(parent->getLeftChild());
// traverse the right child of current node
postOrder(parent->getRightChild());
// Display the current node data
cout<getData()<<” “;
main.cpp
#include
#include “BinaryTree.h
using namespace std
int main(
bool loop=true;
// create object for the binary tree
BinaryTree binaryTree;
// perform the following function repeatedly until the user exits the application
while(loop){
// display the menu
cout<<“Menu”<<endl;
cout<<“1) Insert Data”<<endl;
cout<<“2) Display in Preorder”<<endl;
cout<<“3) Display in Inorder”<<endl;
cout<<“4) Display in Postorder”<<endl;
cout<<“5) Exit”<<endl;
//get the user choice
cout<<“Enter your choice: “;
int choice=0;
cin>>choice;
// switch based on the choice requested
switch(choice){
case 1:{
// Get the data to insert from the user
cout<<“Enter the data: “;
int data;
cin>>data;
// insert the data into the binary tree
binaryTree.insert(data);
break
case 2:{
// traverse the tree in preorder traversal
cout<<“Preorder Traversal”<<endl;
binaryTree.preOrder();
cout<<endl;
break;
case 3:{
// traverse the tree in inorder traversal
cout<<“Inorder Traversal”<<endl;
binaryTree.inOrder();
cout<<endl;
case 4:{
// traverse the tree in postorder traversal
cout<<“Postorder Traversal”<<endl;
binaryTree.postOrder();
cout<<endl;
case 5:{
// set loop to false to exit the application
loop=false;
break;