#include \"BinTree.h\" // CS212, Spring 2014, EXAM #5 void main() { BinTree<int>

Question

#include "BinTree.h"

// CS212, Spring 2014, EXAM #5   

void main()

{

     BinTree<int> treeA;

     // Add elements to the tree

     treeA.insert(42);

     treeA.insert(11);

     treeA.insert(99);

     treeA.printSideways(); // see output

// Above output is given at the very top of this page to get things started.

// 1. Using our text definition for binary search tree, is this tree a valid BST?

// 2. How many nodes are in this overall tree structure?

// 3. How many levels?

// 4. What data is at the overall root?

// 5. Give the order of data output for a pre-order traversal of this tree.

     treeA.insert(33);

// 6. Sketch the tree structure after the insert(33) operation is complete.

     treeA.printSideways();

     BinTree<string> treeB; // start a new tree structure

     treeB.insert("Belize");

     treeB.insert("America");

     treeB.insert("Texas");

     treeB.printSideways(); /

// 7. What does the tree look like here.

     treeB.insert("Canada");

     treeB.printSideways();

// 8. Now what does it look like? Hint: Texas no longer appears!

// 9. Fix the insert function so Texas will NOT be lost in the operations above.

     treeA.clear(); // 10. Write this function.

// On attached paper, clearly indicate:

     // what lines of code go where in the "header" information.

     // what lines of code go where in the implementations.

     // if functions are members, non-members, or friends.

// BELOW is the "BinTree.h" file for main() program above

#include <iostream>

#include <string>

using namespace std;

// W.P. Iverson, CS212 Exam #5

// June 2014

template<typename T>

class TreeNode

{

public:

T data; // Element contained in the node

TreeNode<T>* left; // Pointer to the left child

TreeNode<T>* right; // Pointer to the right child

TreeNode(T element) // Constructor

{

    data = element;

    left = NULL;

    right = NULL;

}

};

Explanation / Answer

here is your BinTree.h : ------------>>>>>>>>>>>

#include <iostream>
#include <string>
using namespace std;
// W.P. Iverson, CS212 Exam #5
// June 2014
template<typename T>
class TreeNode
{
public:
T data; // Element contained in the node
TreeNode<T>* left; // Pointer to the left child
TreeNode<T>* right; // Pointer to the right child
TreeNode(T element) // Constructor
{
data = element;
left = NULL;
right = NULL;
}
};

template<class T>
class BinTree{
private:
  TreeNode<T> *root;
  void insert(TreeNode<T> *root,T item){
   if(root->data < item){
    if(root->right == NULL){
     root->right = new TreeNode<T>(item);
     return;
    }
    insert(root->right,item);
   }else if(root->data > item){
    if(root->left == NULL){
     root->left = new TreeNode<T>(item);
     return;
    }
    insert(root->left,item);
   }
  }
  void print(TreeNode<T> *root,int indent){
   if(root == NULL){
    return;
   }
   if(root->right != NULL){
    print(root->right,indent+1);
   }
   for(int i = 0;i<indent;i++)
    cout<<"      ";
   cout<<root->data<<" ";
   print(root->left,indent+1);
  }
  void clear(TreeNode<T> *root){
   if(root == NULL){
    return;
   }
   if(root->left != NULL){
    clear(root->left);
    delete root->left;
   }
   if(root->right != NULL){
    clear(root->right);
    delete root->right;
   }
  }
public:
  BinTree(){
   root = NULL;
  }
  void insert(T item){
   if(root == NULL){
    this->root = new TreeNode<T>(item);
    return;
   }
   insert(root,item);
  }
  void printSideways(){
   cout<<" ---------------------------------- ";
   print(root,0);
  }
  void clear(){
   clear(root);
   if(root != NULL){
    delete root;
   }
  }
};

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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