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
Algorithm for the Preorder Traversal from root node:
Algorithm for the Inorder Traversal from root node:
Algorithm for the Preorder Traversal from root node:
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
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;
Essay Writing Service Features
Our Experience
No matter how complex your assignment is, we can find the right professional for your specific task. Contact Essay is an essay writing company that hires only the smartest minds to help you with your projects. Our expertise allows us to provide students with high-quality academic writing, editing & proofreading services.
Free Features
Free revision policy
$10Free bibliography & reference
$8Free title page
$8Free formatting
$8How Our Essay Writing Service Works
First, you will need to complete an order form. It's not difficult but, in case there is anything you find not to be clear, you may always call us so that we can guide you through it. On the order form, you will need to include some basic information concerning your order: subject, topic, number of pages, etc. We also encourage our clients to upload any relevant information or sources that will help.
Complete the order form
Once we have all the information and instructions that we need, we select the most suitable writer for your assignment. While everything seems to be clear, the writer, who has complete knowledge of the subject, may need clarification from you. It is at that point that you would receive a call or email from us.
Writer’s assignment
As soon as the writer has finished, it will be delivered both to the website and to your email address so that you will not miss it. If your deadline is close at hand, we will place a call to you to make sure that you receive the paper on time.
Completing the order and download