In this Assignment. You will be implementing your own Tree ADT. Be sure to check
ID: 3869098 • Letter: I
Question
In this Assignment. You will be implementing your own Tree ADT. Be sure to check for errors.
#include "tree_head.hpp"
#include <iostream>
using namespace std;
int main()
{
Tree t;
t.push(4);
t.push(2);
t.push(1);
t.push(3);
t.push(6);
t.push(5);
cout<<"t is : "<<endl;
t.print();
Tree t3(t);
t3.push(7);
cout<<"t is : "<<endl;
t.print();
cout<<"t3 is : "<<endl;
t3.print();
Tree t2;
t2.push(2);
t2.push(1);
t2.push(3);
t2 = t;
t2.push(8);
t2.push(9);
t2.push(11);
cout<<"t2 is : "<<endl;
t2.print();
cout<<"t is : "<<endl;
t.print();
t2.deleteNode(1);
t2.deleteNode(5);
cout<<"t2 is : "<<endl;
t2.print();
TreeNode *node = t.find(5);
cout << "found: " << node->value << endl;
node = t.find(100000);
cout << "t.find(100000): " << node << endl;
}
//
// tree_imp.hpp
// Trees
//
// Created by Pat Khai on 7/23/17.
// Copyright © 2017 Pat Khai. All rights reserved.
//
#ifndef _TREE_H
#define _TREE_H
#include <cstdlib> // necessary in order to use NULL
class TreeNode
{
public:
TreeNode() : left(NULL), right(NULL) {}
TreeNode* left;
TreeNode* right;
int value;
};
class Tree
{
public:
// Default constructor
Tree();
// Copy constructor
Tree(const Tree& other);
//Destructor
~Tree();
// overloaded Assignment Operator
Tree& operator=(const Tree& other);
// Similar to insert function we discussed earlier
// creates node and inserts it at appropriate position.
void push(int value);
// Returns the address of the node containing the value.
TreeNode* find(int value) const;
// Print the tree data
void print() const;
// Deletes the node with value in the tree and deallocates its memory.
void deleteNode(int value);
private:
// Root of the tree.
TreeNode* start;
//copyOther
// you should implement and use this helper function inside your
// copy constructor and overloadedAssignment operator.
void copyOther(const Tree& other);
// clear
// you should implement and use this function inside your
// destructor to delete all the nodes and free memory
void clear();
// pushFrom
// Recursively push a single element into a tree.
// Use it in your push function.
void pushFrom(TreeNode* startingPoint, TreeNode* nodeToPush);
// findFrom
// Recursively find a single element in a tree.
TreeNode* findFrom(TreeNode* startingPoint, int value) const;
// printFrom
//
// Recursively print the values in a tree. Use
// pre-order traversal.
//
// If a tree looks like this:
//
// 6
// /
// /
// 5 8
// / /
// / /
// 0 7 9
//
// then it should be printed like this:
//
// 6
// 5
// 0
// 8
// 7
// 9
//
// Helper function that you should use inside your print function
void printFrom(TreeNode* startintPoint, int numSpaces) const;
// copyFrom
// Recursively copy another tree's nodes. Use
// pre-order traversal. Use this in CopyOther function.
void copyFrom(TreeNode* startintPoint);
// deleteFrom
// should implement and use in the delete function.
// Deletes the node with the value specified in the below function.
void deleteFrom(TreeNode* startintPoint, int value);
// clearFrom
// Recursively delete nodes. Use post-order traversal.
// Use it in clear function.
void clearFrom(TreeNode* startingPoint);
};
#endif /* tree_imp_hpp */
Explanation / Answer
The code for the above description is as follows:
BinaryTree.cpp
# include <iostream>
# include <cstdlib>
using namespace std;
struct nde
{
int informat;
struct nde *lt;
struct nde *rt;
}*roots;
class BinaryTree
{
public:
void search(int, nde **, nde **);
void ins(int);
void delete(int);
void firstCase(nde *,nde *);
void secCase(nde *,nde *);
void thirdCase(nde *,nde *);
void pre(nde *);
void inOrd(nde *);
void post(nde *);
void print(nde *, int);
BinaryTree()
{
roots = NULL;
}
};
int main()
{
int ch, no;
BinaryTree bt;
nde *temporary;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BinaryTree"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Inorder Traversal"<<endl;
cout<<"4.Preorder Traversal"<<endl;
cout<<"5.Postorder Traversal"<<endl;
cout<<"6.Display"<<endl;
cout<<"7.Quit"<<endl;
cout<<"Enter your ch : ";
cin>>ch;
switch(ch)
{
case 1:
temporary = new nde;
cout<<"Enter the number to be inserted : ";
cin>>temporary->informat;
bt.ins(roots, temporary);
case 2:
if (roots == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>no;
bt.delete(no);
break;
case 3:
cout<<"Inorder Traversal of BinaryTree:"<<endl;
bt.inOrd(roots);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal of BinaryTree:"<<endl;
bt.pre(roots);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal of BinaryTree:"<<endl;
bt.post(roots);
cout<<endl;
break;
case 6:
cout<<"Display BinaryTree:"<<endl;
bt.print(roots,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<"Wrong ch"<<endl;
}
}
}
void BinaryTree::search(int items, nde **prnt, nde **locate)
{
nde *pntr, *ptSave;
if (roots == NULL)
{
*locate = NULL;
*prnt = NULL;
return;
}
if (items == roots->informat)
{
*locate = roots;
*prnt = NULL;
return;
}
if (items < roots->informat)
pntr = roots->lt;
else
pntr = roots->rt;
ptSave = roots;
while (pntr != NULL)
{
if (items == pntr->informat)
{
*locate = pntr;
*prnt = ptSave;
return;
}
ptSave = pntr;
if (items < pntr->informat)
pntr = pntr->lt;
else
pntr = pntr->rt;
}
*locate = NULL;
*prnt = ptSave;
}
void BinaryTree::ins(nde *trees, nde *nwNde)
{
if (roots == NULL)
{
roots = new nde;
roots->informat = nwNde->informat;
roots->lt = NULL;
roots->rt = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (trees->informat == nwNde->informat)
{
cout<<"Element already in the trees"<<endl;
return;
}
if (trees->informat > nwNde->informat)
{
if (trees->lt != NULL)
{
ins(trees->lt, nwNde);
}
else
{
trees->lt = nwNde;
(trees->lt)->lt = NULL;
(trees->lt)->rt = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (trees->rt != NULL)
{
ins(trees->rt, nwNde);
}
else
{
trees->rt = nwNde;
(trees->rt)->lt = NULL;
(trees->rt)->rt = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
void BinaryTree::delete(int items)
{
nde *parent, *location;
if (roots == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
search(items, &parent, &location);
if (location == NULL)
{
cout<<"Item not present in trees"<<endl;
return;
}
if (location->lt == NULL && location->rt == NULL)
firstCase(parent, location);
if (location->lt != NULL && location->rt == NULL)
secCase(parent, location);
if (location->lt == NULL && location->rt != NULL)
secCase(parent, location);
if (location->lt != NULL && location->rt != NULL)
thirdCase(parent, location);
free(location);
}
void BinaryTree::firstCase(nde *prnt, nde *locate )
{
if (prnt == NULL)
{
roots = NULL;
}
else
{
if (locate == prnt->lt)
prnt->lt = NULL;
else
prnt->rt = NULL;
}
}
void BinaryTree::secCase(nde *prnt, nde *locate)
{
nde *children;
if (locate->lt != NULL)
children = locate->lt;
else
children = locate->rt;
if (prnt == NULL)
{
roots = children;
}
else
{
if (locate == prnt->lt)
prnt->lt = children;
else
prnt->rt = children;
}
}
void BinaryTree::thirdCase(nde *prnt, nde *locate)
{
nde *pntr, *ptSave, *succeed, *prntSuc;
ptSave = locate;
pntr = locate->rt;
while (pntr->lt != NULL)
{
ptSave = pntr;
pntr = pntr->lt;
}
succeed = pntr;
prntSuc = ptSave;
if (succeed->lt == NULL && succeed->rt == NULL)
firstCase(prntSuc, succeed);
else
secCase(prntSuc, succeed);
if (prnt == NULL)
{
roots = succeed;
}
else
{
if (locate == prnt->lt)
prnt->lt = succeed;
else
prnt->rt = succeed;
}
succeed->lt = locate->lt;
succeed->rt = locate->rt;
}
void BinaryTree::pre(nde *pntr)
{
if (roots == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (pntr != NULL)
{
cout<<pntr->informat<<" ";
pre(pntr->lt);
pre(pntr->rt);
}
}
void BinaryTree::inOrd(nde *pntr)
{
if (roots == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (pntr != NULL)
{
inOrd(pntr->lt);
cout<<pntr->informat<<" ";
inOrd(pntr->rt);
}
}
void BinaryTree::post(nde *pntr)
{
if (roots == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (pntr != NULL)
{
post(pntr->lt);
post(pntr->rt);
cout<<pntr->informat<<" ";
}
}
void BinaryTree::print(nde *pntr, int lvl)
{
int uu;
if (pntr != NULL)
{
print(pntr->rt, lvl+1);
cout<<endl;
if (pntr == roots)
cout<<"Root->: ";
else
{
for (uu = 0;uu < lvl;uu++)
cout<<" ";
}
cout<<pntr->informat;
print(pntr->lt, lvl+1);
}
}
Please rate the answer if it helped......Thankyou
Hope it helps.....