I\'m having some issues with this code, the current code takes a file called cmd

Question

I'm having some issues with this code, the current code takes a file called cmd.txt.

Output should be:

---------cmd.txt----------

1 20
7
1 30
7
1 10
7
1 25
7
1 29
7

1 23
7
1 56
7
1 89
7
1 4
7
1 33
7
2
3
4
6 20
2
3
4
6 89
2
3
4
8
9

------------CURRENT CODE-------------

#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>

using namespace std;

struct Node
{
Node();
int value;
int element;
Node* left;
Node* right;
};

class BST
{
public:
BST();
~BST();
void Insert(int value);
bool Find(int value);
void InOrder();
void PostOrder();
void PreOrder();
void Clear();
void Remove(int value);
   int TreeHeight();
   int FindMin();
   int FindMax();
protected:
int height(Node *r);
void Insert_(Node *&r, int value);
void Clear_(Node *&r);
void InOrder_(Node *r);
void PostOrder_(Node *r);
void PreOrder_(Node *r);
Node *FindNode(Node *r, int value);
   Node *Remove_(Node *r, int value);
Node *root;
//   void Remove_();
int TreeHeight_(Node *r);
int FindMin(Node *r);
int FindMax(Node *r);
};

void parse_file(string file_name, vector<pair<string, string> > &commands);

int main()
{
BST tree;
vector<pair<string, string> > cmd_arg;

parse_file("cmd.txt", cmd_arg);

for (size_t i = 0; i < cmd_arg.size(); i++)
{
if (cmd_arg[i].first == "1")
{
tree.Insert(atoi(cmd_arg[i].second.c_str()));
}
else if (cmd_arg[i].first == "2")
{
tree.InOrder();
}
else if (cmd_arg[i].first == "3")
{
tree.PostOrder();
}
else if (cmd_arg[i].first == "4")
{
tree.PreOrder();
}
else if (cmd_arg[i].first == "5")
{
if(tree.Find(atoi(cmd_arg[i].second.c_str())))
{
cout << "We found: ";
}
else
{
cout << "We did not find: ";
}
cout << cmd_arg[i].second << endl;
}
   else if (cmd_arg[i].first == "6")
{
// tree.Remove();
tree.Insert(atoi(cmd_arg[i].second.c_str()));
}
   else if (cmd_arg[i].first == "7")
{
tree.TreeHeight();
}
   else if (cmd_arg[i].first == "8")
{
tree.FindMin();
}
   else if (cmd_arg[i].first == "9")
{
tree.FindMax();
}
else
{
cout << "Unknown command: " << cmd_arg[i].first << endl;
}
}
cmd_arg.clear();
return 0;
}

Node::Node() : left(NULL), right(NULL) { }

BST::BST() : root(NULL) { }

BST::~BST() { Clear_(root); }

void BST::Insert(int value)
{
Insert_(root, value);
}

bool BST::Find(int value)
{
return (FindNode(root, value) != NULL);
}

void BST::InOrder()
{
cout << "Inorder: ";
InOrder_(root);
cout << endl;
}

void BST::PostOrder()
{
cout << "Postorder: ";
PostOrder_(root);
cout << endl;
}

void BST::PreOrder()
{
cout << "Preorder: ";
PreOrder_(root);
cout << endl;
}

//void BST::PreOrder()
//{
// cout << "Preorder: ";
//PreOrder_(root);
//cout << endl;
//}

int BST::TreeHeight()
{
cout << "Height of Tree: ";
TreeHeight_(root);
cout << endl;  

}

void BST::Clear() { Clear_(root); }

void BST::Insert_(Node *&r, int value)
{
if (r == NULL)
{
r = new Node;
r->value = value;
}
else if (value < r->value)
{
Insert_(r->left, value);
}
else
{
Insert_(r->right, value);
}
}

void BST::Clear_(Node *&r)
{
if (r != NULL)
{
Clear_(r->left);
Clear_(r->right);
delete r;
r = NULL;
}
}

void BST::InOrder_(Node *r)
{
if (r != NULL)
{
InOrder_(r->left);
cout << r->value << " ";
InOrder_(r->right);
}
}

void BST::PostOrder_(Node *r)
{
if (r != NULL)
{
PostOrder_(r->left);
PostOrder_(r->right);
cout << r->value << " ";
}
}

void BST::PreOrder_(Node *r)
{
if (r != NULL)
{
cout << r->value << " ";
PreOrder_(r->left);
PreOrder_(r->right);
}
}

Node *BST::FindNode(Node *r, int value)
{
if (r != NULL)
{
if (value == r->value)
{
return r;
}
else if (value > r->value)
{
return FindNode(r->right, value);
}
else
{
return FindNode(r->left, value);
}
}
return r;
}

//fuckery
void BST::Remove(int value) {
root = Remove_(root, value);
return;
}

Node *BST::Remove(Node* r, int value) {
if (r == NULL)
return r;

if (value < r->element) {
r->left = Remove(r->left, value);
return r;
}
if (value > r->element) {
r->right = Remove(r->right, value);
return r;
}

if (r->left != NULL && r->right != NULL) {
//int m=findMin(t->right);
int m = r->element = FindMin(r->right);
r->right = Remove(r->right, m);
return r;
}

if (r->right != NULL) {
Node *n = r;
r = r->right;
delete n;
return r;
} else {
Node *r = r;
r = r->left;
delete n;
return r;
}

}

int BST::TreeHeight_(Node *r) {
//Node *t=root;
//BST *B1=t;
if (r == NULL)
return 0;
if (r->left == NULL && r->right == NULL)
return 0;
if (height(r->left) > height(r->right))
return height(r->left) + 1;
else
return height(r->right) + 1;
}

//fuckery
void parse_file(string file_name, vector<pair<string, string> > &commands)
{
fstream file;
string line, command, argument;
size_t space_pos;

file.open(file_name.c_str(), fstream::in);
if (file.is_open())
{
while (getline(file, line))
{
if (line.empty())
continue;

if (line[line.length() - 1] == ' ')
line = line.substr(0, line.length() - 1);
space_pos = line.find(" ");
      
if (space_pos != string::npos)
{
command = line.substr(0, space_pos);
argument = line.substr(space_pos + 1);
commands.push_back(make_pair(command, argument));
}
else
{
commands.push_back(make_pair(line, ""));
}
}
file.close();
}
else
{
cout << "The file could not be opened" << endl;
}
}

Explanation / Answer

#include <iostream>
#include <queue>
using namespace std;

// Node class
class Node {
    string key;
    Node* left;
    Node* right;
public:
    Node() { key=-1; left=NULL; right=NULL; };
    void setKey(string aKey) { key = aKey; };
    void setLeft(Node* aLeft) { left = aLeft; };
    void setRight(Node* aRight) { right = aRight; };
    string Key() { return key; };
    Node* Left() { return left; };
    Node* Right() { return right; };
};

// Tree class
class Tree {
     Node* root;
public:
     Tree();
     ~Tree();
     Node* Root() { return root; };
     void addNode(string key);
     void levelOrder(Node* n);
     void Inorder(Node* );
    void Postorder(Node* );
    void Preorder(Node* node);
private:
     void addNode(string key, Node* leaf);
     void freeNode(Node* leaf);
};

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

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

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL )
    {
       freeNode(leaf->Left());
       freeNode(leaf->Right());
       delete leaf;
    }
}

// Add a node
void Tree::addNode(string key) {
     // No elements. Add the root
     if ( root == NULL ) {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
    root = n;
     }
     else {
    cout << "add other node ... " << key << endl;
    addNode(key, root);
     }
}

// Add a node (private)
void Tree::addNode(string key, Node* leaf) {
    if ( key <= leaf->Key() ) {
       if ( leaf->Left() != NULL )
      addNode(key, leaf->Left());
       else {
      Node* n = new Node();
      n->setKey(key);
      leaf->setLeft(n);
       }
    }
    else {
       if ( leaf->Right() != NULL )
      addNode(key, leaf->Right());
       else {
      Node* n = new Node();
      n->setKey(key);
      leaf->setRight(n);
       }
    }
}

// Print the tree level-order assisted by queue
void Tree::levelOrder(Node* n) {
   // Create a queue
   queue<Node*> q;

   // Push the root
   q.push(n);

   while ( ! q.empty() )
   {
       // Dequeue a node from front
       Node* v = q.front();
       cout << v->Key() << " ";

       // Enqueue the left children
       if ( v->Left() != NULL )
            q.push(v->Left());

       // Enqueue the right children
       if ( v->Right() != NULL )
            q.push(v->Right());

       // Pop the visited node
       q.pop();
   }
}

void Tree::Preorder(Node* node)
{
    if ( node )
    {
        cout << node->Key() << " ";
        Preorder(node->Left());
        Preorder(node->Right());
    }
}

void Tree:: Inorder(Node* Root)
{
    if(Root != NULL)
    {
        Inorder(Root->Left());
        cout << Root->Key() << endl;
        Inorder(Root->Right());

    }
}

void Tree:: Postorder(Node* Root)
{
    if(Root != NULL)
    {

        Postorder(Root->Left());
        Postorder(Root->Right());
        cout << Root->Key() << endl;

    }
}

// Test main program
int main() {
   Tree* tree = new Tree();
   tree->addNode("A");
    tree->addNode("B");
    tree->addNode("C");
    tree->addNode("D");
    tree->addNode("E");
    tree->addNode("F");
    tree->addNode("G");
    tree->addNode("H");
    tree->addNode("I");
    tree->addNode("J");
    tree->addNode("K");
    tree->addNode("L");

   cout << "Level order traversal" << endl;
   tree->levelOrder(tree->Root());
   cout << endl;

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

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

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

   delete tree;
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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