Implement binary search tree (BST) with insertion and per-order, postorder and i

Question

Implement binary search tree (BST) with insertion and per-order, postorder and in-order traversal operations. The program must read a list of strings from an input file and insert them into the binary search tree. Then it must traverse the tree in pre-order, in-order and post-order manner and print the data in the tree on the screen. Input file: The program has one input file called "data.txt" that contains a string on each line. There is no repetitive string in the file. Below is a sample input file: NewYork Cairo Toronto Barcelona London Paris Rome Athens Venice Output: The program must read each string from the input file, and inserts it into a binary search tree, then it prints the contents of the tree while traversing in three ways: pre-order, in-order and post-order.

Explanation / Answer

#include <iostream>
#include<fstream>
using namespace std;
//Class Node Definition
class Node
{
//Data member
string key;
Node* left;
Node* right;
public:
//Constructor
Node()
{
key = -1;
left = NULL;
right = NULL;
}
//To set the key
void setKey(string Key)
{
key = Key;
}
//To set Left
void setLeft(Node* Left)
{
left = Left;
};
//To set Right
void setRight(Node* Right)
{
right = Right;
}
//Return key
string Key()
{
return key;
}
//Return left
Node* Left()
{
return left;
}
//Return right
Node* Right()
{
return right;
}
};//End of class

// Class Tree Definition
class Tree
{
//Data member
Node* root;
public:
//Member function
Tree();
~Tree();
Node* Root()
{
return root;
}
void addNode(string key);
void inOrder(Node* nn);
void preOrder(Node* nn);
void postOrder(Node* nn);
private:
//Member function
void addNode(string key, Node* Leaf);
void freeNode(Node* Leaf);
};

// Constructor
Tree::Tree()
{
root = NULL;
}//End of constructor

// Destructor
Tree::~Tree()
{
freeNode(root);
}//End of destructor

// Free the node
void Tree::freeNode(Node* Leaf)
{
//Checks if leaf is null
if ( Leaf != NULL )
{
freeNode(Leaf -> Left());
freeNode(Leaf -> Right());
//Delete leaf
delete Leaf;
}//End of if
}//End of function

// Add a node
void Tree::addNode(string Key)
{
// No elements. Add the root
if ( root == NULL )
{
//Creates a new node
Node* nn = new Node();
nn -> setKey(Key);
root = nn;
}//End of if
else
{
addNode(Key, root);
}//End of else
}//End of function

// Add a node (private)
void Tree::addNode(string Key, Node* Leaf)
{
//Checks whether the key is less than or equal to leaf value
if ( Key <= Leaf -> Key() )
{
//Checks whether the leaf left is null
if ( Leaf -> Left() != NULL )
addNode(Key, Leaf -> Left());
else
{
//Creates a new node
Node* nn = new Node();
nn -> setKey(Key);
Leaf -> setLeft(nn);
}//End of else
}//End of if
else
{
//Checks whether leaf right is not null
if ( Leaf -> Right() != NULL )
addNode(Key, Leaf -> Right());
else
{
//Create a new node
Node* nn = new Node();
nn -> setKey(Key);
Leaf -> setRight(nn);
}//End of inner else
}//End of outer else
}//End of function

// Inorder traversal
// Procedure: Left , Root, Right
void Tree::inOrder(Node* nn)
{
if (nn)
{
inOrder(nn -> Left());
cout << nn -> Key() << ", ";
inOrder(nn -> Right());
}//End of if
}//End of function

// Preorder traversal
// Procedure: Root, Left , Right
void Tree::preOrder(Node* nn)
{
if (nn)
{
cout << nn -> Key() << ", ";
preOrder(nn -> Left());
preOrder(nn -> Right());
}//End of if
}//End of function

// Postorder Traversal
// Procedure: Left , Right, Root
void Tree::postOrder(Node* nn)
{
if (nn)
{
postOrder(nn -> Left());
postOrder(nn -> Right());
cout << nn -> Key() << ", ";
}//End of if
}//End of function

//Read data from file and stores it in the Tree
void readFile(Tree *tree)
{
//Creates an object of ifstream
ifstream readf;
//Opens the file for reading
readf.open("BSTData.txt");
string data;
//Loops till end of file
while(!readf.eof())
{
//Reads data and stores in respective array
readf>>data;
tree->addNode(data);
}//End of while
//Close file
readf.close();
}//End of function

// Test main program
int main()
{
//Creates a pointer of type Tree
Tree* tree = new Tree();
//Read the file and store the data in Tree
readFile(tree);

cout << "In order traversal" << endl;
tree->inOrder(tree->Root());
cout << endl;

cout << "Pre order traversal" << endl;
tree->preOrder(tree->Root());
cout << endl;

cout << "Post order traversal" << endl;
tree->postOrder(tree->Root());
cout << endl;

delete tree;
return 0;
}//End of main function

Output:

In order traversal
Athens, Barcelona, Cairo, London, NewYork, Paris, Rome, Toronto, Venice,
Pre order traversal
NewYork, Cairo, Barcelona, Athens, London, Toronto, Paris, Rome, Venice,
Post order traversal
Athens, Barcelona, London, Cairo, Rome, Paris, Venice, Toronto, NewYork,

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.