Given the incomplete program: // Tree class definition from Tree.h class Tree {

Question

Given the incomplete program:

// Tree class definition from Tree.h
class Tree {
public:
class Node {
public:
    Node() : left(nullptr), right(nullptr), data(0){}
    Node(int val) : left(nullptr), right(nullptr), data(val) {}
    int data;
    Node *left, *right;
};

Tree() : count(0), root(nullptr) {}
bool insert(int newVal);
friend ostream& operator << (ostream& str, const Tree& tree); // calls print and
                                                                // outputs count

private:
void print(ostream& ostr, Node* curNode) const; // recursive function

Node* root;
int count;
};

Write c++ programe to do the followings:

- The insert member function should use loops to find the correct place for the new data, and the print function must use recursion to print out the sorted data from the Tree.

- Inside the insert function you need to give the following “debug” output:

    insert in empty tree               when this is the case
    checking left/right                 when moving to the left or right down tree
    inserting TRUE/FALSE            able to insert or not
    {for an example look at the Program 6 Notes Tree.pdf in the Lecture section on Canvas}

- Insert the following numbers into the tree in this order:

                6   9    3    5    5   7   2   10   4   1   8

....and then output the data in sorted order and count from the list

Explanation / Answer

here is your program : ------------>>>>>>>>

#include<iostream>

using namespace std;

class Tree {

public:
  class Node {
   public:
    Node() : left(nullptr), right(nullptr), data(0){}
    Node(int val) : left(nullptr), right(nullptr), data(val) {}
    int data;
    Node *left, *right;
  };
  Tree() : count(0), root(nullptr) {}
  bool insert(int newVal);
  friend ostream& operator<<(ostream& str, const Tree& tree){
   tree.print(str,tree.root);
   str<<" Count = "<<tree.count;
   return str;
  }// calls print and// outputs count
private:
  void print(ostream& ostr, Node* curNode) const;// recursive function
  Node* root;
  int count;
};

void Tree::print(ostream &ostr,Tree::Node *curNode) const{
if(curNode == nullptr){
  return;
}
print(ostr,curNode->left);
ostr<<" "<<curNode->data;
print(ostr,curNode->right);
}

bool Tree::insert(int newVal){
Node *temp = new Node;
temp->data = newVal;
temp->left = nullptr;
temp->right = nullptr;

if(root == NULL){
  cout<<" Insert in Empty Tree";
  root = temp;
  cout<<" Inserting True";
  count++;
  return true;
}
Node *tmp = root;
while(true){
  if(newVal < tmp->data){
   cout<<" Checking left";
   if(tmp->left == nullptr){
    cout<<" inserting True";
    tmp->left = temp;
    count++;
    return true;
   }
   cout<<" inserting False";
   tmp = tmp->left;
  }else if(newVal > tmp->data){
   cout<<" Checking right";
   if(tmp->right == nullptr){
    cout<<" inserting True";
    tmp->right = temp;
    count++;
    return true;
   }
   cout<<" inserting false";
   tmp = tmp->right;
  }else{
   cout<<" Duplicate found";
   return false;
  }
}
}

int main(){
Tree t;
t.insert(6);
t.insert(9);
t.insert(3);
t.insert(5);
t.insert(5);
t.insert(7);
t.insert(2);
t.insert(10);
t.insert(4);
t.insert(1);
t.insert(8);
cout<<endl<<t;
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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