Add as member functions to the class BST: in addition to above add following fun

ID: 665049 • Letter: A

Question

Add as member functions to the class BST:

in addition to above add following funcntions

Size() // should return the size(number of the nodes in a BST),

MirrorImage()// should return another binary tree that is mirror image of the original,

isBST()// should return value 1 if it is a binary tree or return false if it is not.

22. Write a recursive function member 1eve10 for class template BST that determines the level in the BST at which a specified item is located. The root of the BST is at level 0, its children are at levell, and so on.

24. The worst-case numberofcomparisons in searching a BSTis equaltoits height,that is, the numberoflevels in the tree.Write a recursive function member hei ght0 for class template BST to determine the height ofthe BST.

25. Write a recursive function member 1eafCountO for class template BST to count the leaves in a binary tree. (Hint: How is the number of leaves in the entire tree related to the number ofleaves in the left and right subtrees ofthe root?)

So my code so far is:

//BinTree.h
#include <iostream>
#include<iomanip>
using namespace std;

class BinTree
{
class BinNode
{
  public:
   int data; //holds the data
   BinNode * lchild, * rchild; //points to the left and right child
   BinNode():lchild(0), rchild(0){} //setting variables = 0
   BinNode(int value):data(value),lchild(0), rchild(0){} //setting data - to the value and variables = 0
};

BinNode * root; //points to the address of the top of top of a binary tree
bool searchAux(BinNode *, int);
void destroyAux(BinNode *);
void insertAux(BinNode * &, int);
BinNode * cloneAux(BinNode *);
void displayAux(BinNode *);
void graphAux(ostream & out, int indent, BinNode * subtreeRoot);
public:
  BinTree():root(0){} //constructor to set root = 0
  BinTree(BinTree &T);
  bool search(int);
  void insert(int);
  void erase(int);
  ~BinTree(); //destructor
  void display();
  void graph(ostream & out);
};

void BinTree::display(){
displayAux(root);
}

void BinTree::displayAux(BinNode *node){
if (node != 0){
  displayAux(node->lchild);
  cout<<" "<<node->data<<" ";
  displayAux(node->rchild);
}

}

//Destructor
BinTree::~BinTree() //destructor you have to destroy from the bottom up, can't destroy root first or you will lose the addresses
//use postorder traversal (LRV)
{
destroyAux(root); //pass the root to the destroyAux function
}

void BinTree::destroyAux(BinNode * node)
{
if(node != 0) //if we are not at the end of the list
{
  destroyAux(node->lchild); //destroy node left child then it goes back through function and goes to the next address and so on
  destroyAux(node->rchild); //then after the left child has reached null, it goes here and right child also is null
  delete node; //so we finally delete that node
}
}

//Insert function
void BinTree::insert(int value)
{
insertAux(root, value); //call insertAux with root and value
}

void BinTree::insertAux(BinNode * &node, int item) //must pass by reference!
{
if (node == 0) //if node = 0 then add a new node
{
node = new BinNode(item);
}

else if (node->data > item)
{
insertAux(node->lchild, item);
}

else if(node->data < item)
{
insertAux(node->rchild, item);
}

else
{
cout << "Node exists already. ";
}
}

//Delete function
void BinTree::erase(int item)
{
BinNode * n2del = root, * parent = 0, * temp;

//traverse to find parent and the n2del
while (n2del != 0 && n2del->data != item)
{
  if (n2del->data > item)
  {
   parent = n2del; //set parent = to the n2del
   n2del = n2del->lchild; //set the n2del = to the n2del's left child
  }
  else
  {
   parent = n2del; //set parent = to the n2del
   n2del = n2del->rchild; //set the n2del = to the n2del's right child
  }
}

if (n2del ==0) {cout<<"Item not found "; return;} // if item is not found return
//if node has two children
if (n2del->lchild != 0 && n2del->rchild != 0)
{
  parent = n2del;
  temp = n2del->rchild;
  while(temp->lchild != 0)
  {
   parent = temp;
   temp = temp->lchild;
  }
  n2del->data = temp->data; //swap values
  n2del = temp;
}

BinNode * n2delchild; // variable to hold the addres off child of deleting node
if(n2del->lchild == 0) n2delchild = n2del->rchild;
else n2delchild = n2del->lchild;

if (parent == 0) root = n2delchild;
else if (parent->lchild == n2del) parent->lchild = n2delchild;
else parent->rchild = n2delchild;

delete n2del;
}

//Search function
bool BinTree::search(int item)
{
return searchAux(root, item);
}

bool BinTree::searchAux(BinNode * node, int item)
{
if(node != NULL)
{
  if(node->data == item)
  {
   return true;
  }
  else if (item < node->data)
  {
   searchAux(node->lchild, item);
  }
  else
  {
   searchAux(node->rchild, item);
  }
}
else
  return false;
}

//Copy Constructor
BinTree::BinTree (BinTree & T)
{
root = cloneAux(T.root); //T is the root
}

BinTree::BinNode * BinTree::cloneAux(BinNode * n)
{
BinNode * temp =0;

if(n != 0) //root is not = to 0
{
  temp = new BinNode(n->data); //temp creates a new node
  temp->lchild = cloneAux(n->lchild); //clone is called again to create any of the left children
  temp->rchild = cloneAux(n->rchild); //clone is called to create right children
}
return temp;
}

void BinTree::graph(ostream & out)
{ graphAux(out, 0, root); }

void BinTree::graphAux(ostream & out, int indent,
                             BinNode * subtreeRoot)
{
if (subtreeRoot != 0)
    {
      graphAux(out, indent + 8, subtreeRoot->rchild);
      out << setw(indent) << " " << subtreeRoot->data << endl;
      graphAux(out, indent + 8, subtreeRoot->lchild);
    }
}

//main
#include<iostream>
#include"BinTree.h"
#include<ctime>
#include<cstdlib>
using namespace std;
void displayTree(BinTree);
int main()
{
    BinTree T;
    int item2add;
    int item2remove;
    char again;
    srand(time(NULL));
    for(int i = 0; i<15; i++)
{
        item2add = rand()% 100;
        T.insert(item2add);
        cin.get();
        T.display();
    }

    do{
    cout<<"Enter an item to remove ";
    cin>>item2remove;

    T.erase(item2remove);
    T.display();
    cout<<"Want to remove more item (Y/N) ";
    cin >>again;
    } while(again == 'Y');

    displayTree(T);
    T.graph(cout);
    system("pause");

return 0;
}

void displayTree(BinTree T1){
cout<<"In function after cloning ";
T1.display();
}

Explanation / Answer

Complete Program:

//BinTree.h
#include <iostream>
#include<iomanip>
using namespace std;

class BinTree
{
class BinNode
{
public:
  int data; //holds the data
  BinNode * lchild, * rchild; //points to the left and right child
  BinNode():lchild(0), rchild(0){} //setting variables = 0
  BinNode(int value):data(value),lchild(0), rchild(0){} //setting data - to the value and variables = 0
};

int SizeAux(BinNode *);
void MirrorImageAux(BinNode *);
int isBSTAux(BinNode *);
int heightAux(BinNode *);
int leafCountAux(BinNode *);

public:
BinTree():root(0){} //constructor to set root = 0
BinTree(BinTree &T);
bool search(int);
void insert(int);
void erase(int);
~BinTree(); //destructor
void display();
void graph(ostream & out);

int Size();
BinTree MirrorImage();
int isBST();
int height();
int leafCount();
};

void BinTree::display()
{
displayAux(root);
}

void BinTree::displayAux(BinNode *node)
{
if (node != 0)
{
  displayAux(node->lchild);
  cout<<" "<<node->data<<" ";
  displayAux(node->rchild);
}

}

//Insert function
void BinTree::insert(int value)
{
insertAux(root, value); //call insertAux with root and value
}

void BinTree::insertAux(BinNode * &node, int item) //must pass by reference!
{
if (node == 0) //if node = 0 then add a new node
{
  node = new BinNode(item);
}
else if (node->data > item)
{
  insertAux(node->lchild, item);
}
else if(node->data < item)
{
  insertAux(node->rchild, item);
}
else
{
  cout << "Node exists already. ";
}
}

//Delete function
void BinTree::erase(int item)
{
BinNode * n2del = root, * parent = 0, * temp;

if (n2del ==0)
{
cout<<"Item not found ";
return;
} // if item is not found return

//if node has two children
if (n2del->lchild != 0 && n2del->rchild != 0)
{
  parent = n2del;
  temp = n2del->rchild;
  while(temp->lchild != 0)
  {
   parent = temp;
   temp = temp->lchild;
  }
  n2del->data = temp->data; //swap values
  n2del = temp;
}

BinNode * n2delchild; // variable to hold the addres off child of deleting node
if(n2del->lchild == 0)
n2delchild = n2del->rchild;
else
n2delchild = n2del->lchild;

if (parent == 0)
  root = n2delchild;
else if (parent->lchild == n2del)
  parent->lchild = n2delchild;
else
  parent->rchild = n2delchild;

delete n2del;
}

//Search function
bool BinTree::search(int item)
{
return searchAux(root, item);
}

//Copy Constructor
BinTree::BinTree (BinTree & T)
{
root = cloneAux(T.root); //T is the root
}

BinTree::BinNode * BinTree::cloneAux(BinNode * n)
{
BinNode * temp =0;

void BinTree::graph(ostream & out)
{
graphAux(out, 0, root);
}

void BinTree::graphAux(ostream & out, int indent, BinNode * subtreeRoot)
{
if (subtreeRoot != 0)
{
  graphAux(out, indent + 8, subtreeRoot->rchild);
  out << setw(indent) << " " << subtreeRoot->data << endl;
  graphAux(out, indent + 8, subtreeRoot->lchild);
}
}

int BinTree::Size()
{
return SizeAux(root);
}

int BinTree::SizeAux(BinNode * subtreeRoot)
{
if(subtreeRoot == 0)
return 0;
else
return 1 + SizeAux(subtreeRoot->lchild) + SizeAux(subtreeRoot->rchild);
}

BinTree BinTree::MirrorImage()
{
BinTree mirror(*this);

BinNode *current = mirror.root;

MirrorImageAux(current);

return mirror;
}

void BinTree::MirrorImageAux(BinNode * newRoot)
{
if (newRoot == 0)
  return;
else
{
  MirrorImageAux(newRoot->lchild);
  MirrorImageAux(newRoot->rchild);

  BinNode *temp = newRoot->lchild;
  newRoot->lchild = newRoot->rchild;
  newRoot->rchild = temp;
}
}

int BinTree::isBST()
{
return isBSTAux(root);
}

int BinTree::isBSTAux(BinNode * subtreeRoot)
{
static BinNode* prev = 0;

if(subtreeRoot == 0)
return 1;

if(!isBSTAux(subtreeRoot->lchild))
return 0;

if(prev!=0 && subtreeRoot->data<=prev->data)
return 0;

prev = subtreeRoot;
return isBSTAux(subtreeRoot->rchild);
}

int BinTree::height()
{
return heightAux(root);
}

int BinTree::heightAux(BinNode * subtreeRoot)
{
if(subtreeRoot == NULL)
return 0;

if(!subtreeRoot->lchild && !subtreeRoot->rchild)
return 1;

int leftHeight = heightAux(subtreeRoot->lchild);
int rightHeight = heightAux(subtreeRoot->rchild);

if(leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}

int BinTree::leafCount()
{
return leafCountAux(root);
}

int BinTree::leafCountAux(BinNode * subtreeRoot)
{
if(subtreeRoot == 0)
return 0;

if(subtreeRoot->lchild == 0 && subtreeRoot->rchild == 0)
  return 1;
else
  return leafCountAux(subtreeRoot->lchild) + leafCountAux(subtreeRoot->rchild);
}

---------------------------------------------------------------------

//main
#include<iostream>
#include"BinTree.h"
#include<ctime>
#include<cstdlib>
using namespace std;

void displayTree(BinTree);

int main()
{
BinTree T;
int item2add;
int item2remove;
char again;
srand(time(NULL));
for(int i = 0; i<10; i++)
{

  item2add = rand()% 100;
  T.insert(item2add);
  cin.get();
  T.display();
}

/*do
{
cout<<"Enter an item to remove ";
cin>>item2remove;

  T.erase(item2remove);
  T.display();

  cout<<"Want to remove more item (Y/N) ";
  cin >>again;
} while(again == 'Y');*/

//displayTree(T);
T.graph(cout);

BinTree morrorTree = T.MirrorImage();

cout << " Mirror:" << endl;
morrorTree.graph(cout);
cout << " Number of nodes in BST: " << T.Size() << endl;
cout << "isBST(): " << T.isBST() << endl;
cout << "Height: " << T.height() << endl;
cout << "Number of leaf noded: " << T.leafCount() << endl;

system("pause");
return 0;
}

void displayTree(BinTree T1)
{
cout<<"In function after cloning ";
T1.display();
}

Navigate

Add approximately 4 grams of sodium acetate to 4 mL of 6 M acetic acid. Dilute w

Add at least one conditional expression to your program. Examples: In the progra

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

Add as member functions to the class BST: in addition to above add following fun

Question

Explanation / Answer

Related Questions

Navigate