Question

(4) Based on Problem P13.10 e Submit the solution as hmw-6-4.cpp. . Write a program that reads a list of strings (a string per line) from the file data4.txt and inserts them into a binary search tree. You can use the implementation of the class BinarySearchTree introduced in the textbook or rhe one posted on CCLE Implement a traversal function void inorder (Action & a) for inorder traversal of a binary search tree that carries out an action other than just printing the node data. The action should be supplied as a derived class of the class class Actionf public: void act (string str) () ) i . Use the inorder function, and a suitable class derived from Action, to compute the sum of all lengths of the strings stored in a tree and then display it. Similarly, implement traversal functions nreorder (Act ion & al and rost.order (Action & a)

Answer 1

Code in C++(14):

Output:

//------------------------ Code starts------------------------

#include <iostream>

#include <fstream>

#include <stack>

using namespace std;

// node to store string

class node{

public:

string data;

node* left;

node* right;

};

// base class

class Action{

public:

node* root=nullptr;

void act(string data);

};

// derived class

class derived:public Action{

public:

void getLength(Action& a);

};

// creates binary search tree.

void Action::act(string data){

node* new_node=new node(); // new node to store a string

new_node->data=data;

new_node->left=nullptr; // left child of the node

new_node->right=nullptr; // right child of the node

if(root==nullptr){

// initially when root is null, then root

// is set to current node.

root=new_node;

}else{

node* temp_node=root;

node* past_temp_root=root;

// left child and right child of root are visited depending upon

// whether data is alphabetically greater than (or less) than root->data.

while(temp_node!=nullptr){

past_temp_root=temp_node;

if(data<temp_node->data){

temp_node=temp_node->left;

}else{

temp_node=temp_node->right;

}

}

if(data<past_temp_root->data){

past_temp_root->left=new_node;

}else{

past_temp_root->right=new_node;

}

}

}

// inorder traversal :

/*

left elements are visited first and then right elements.

current element is pushed until current element is not null

and then current element is popped out and right element is visited.

*/

void inorder(Action& a){

stack<node*> st;

node* current=a.root;

while(!st.empty() or current!=nullptr){

// left element is visited first

if(current!=nullptr){

st.push(current);

current=current->left;

}else{

node* nd=st.top();

st.pop();

cout << nd->data << endl;

current=nd->right;

}

}

}

// takes Action object as parameter.

// prints out length of all strings in the binary tree

// uses inorder traversal

void derived::getLength(Action& a){

stack<node*> st;

node* current=a.root;

int sum=0;

while(!st.empty() or current!=nullptr){

if(current!=nullptr){

st.push(current);

current=current->left;

}else{

node* nd=st.top();

st.pop();

sum+=nd->data.length();

current=nd->right;

}

}

cout << "Sum of length of all strings: "<< sum << endl;

}

int main(){

Action a;

ifstream file("H:/data4.txt"); // opens file containing names (one string in each line)

string line; // stores string from text file

while(getline(file, line)!=nullptr){

a.act(line); // each string from text file is stored in binary tree

}

cout << "-----Inorder traversal-----" << endl;

inorder(a); // inorder traversal

derived d;

d.getLength(a); // calculates length of all strings in the binary search tree

return 0;

}

//------------------------Code ends--------------------------