22. Write a recursive function member 1eve10 for class template BST that determi

Question

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 number of comparisons in searching a BST is equal to its height, that is, the number oflevels in the tree.Write a recursive function member hei ght 0 for class template BST to determine the height of the 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 of leaves in the left and right subtrees of the root?

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.

Explanation / Answer

#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);

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

public:
BinTree():root(0){}
BinTree(BinTree &T);
bool search(int);
void insert(int);
void erase(int);
~BinTree();
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);
}

}

BinTree::~BinTree()

{
destroyAux(root);
}

void BinTree::destroyAux(BinNode * node)
{
if(node != 0)
{
destroyAux(node->lchild);
destroyAux(node->rchild);
delete node;
}
}

void BinTree::insert(int value)
{
insertAux(root, value);
}

void BinTree::insertAux(BinNode * &node, int item)
{
if (node == 0)
{
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. ";
}
}

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

while (n2del != 0 && n2del->data != item)
{
if (n2del->data > item)
{
parent = n2del;
n2del = n2del->lchild;
}
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 (n2del->lchild != 0 && n2del->rchild != 0)
{
parent = n2del;
temp = n2del->rchild;
while(temp->lchild != 0)
{
parent = temp;
temp = temp->lchild;
}
n2del->data = temp->data;
n2del = temp;
}

BinNode * n2delchild;
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;
}

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;
}

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);
}
}

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');*/

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();
}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

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