Here is what I have I have so far #ifndef BINARY_TREE #define BINARY_TREE #inclu

Question

Here is what I have I have so far

#ifndef BINARY_TREE
#define BINARY_TREE

#include <iostream>

template<class T>

class bTree
{
private:
   struct treeNode
   {
       treeNode * left;
       treeNode * right;
       T data;
   };
   void insert(treeNode*& current, treeNode*& newNode)
   {
       if (current == NULL)
       {
           current = newNode;
       }
       else if (current->left == NULL)
       {
           temp = current;
           current = current->right;
           delete temp;
       }
       else if (current->right == NULL)
       {
           temp = current;
           current = current->left;
           delete temp;
       }
       else
       {
           temp = current->right;
           while (temp->left != NULL)
           {
               temp = temp->left;
           }
           temp->left = current->left;
           temp = current;
           current = current->right;
           delete temp;
       }
   };
   void makeDeletion(treeNode *&current)
   {
       if(current == NULL)
       {
           return;
       }
       else if (current->left == NULL)
       {
           temp = current;
           current = current->right;
           delete temp;
       }
   }
   void deleteN(T value, treeNode &*current)
   {
       if (current->data == value)
       {
           makeDeletion(current);
       }
       else if (value > current->data)
       {
           deleteN(value, current->right);
       }
       else
       {
           deleteN(value, current->left);
       }
   };
   void displayInOrder(treeNode *current, std::ostream &out)
   {
       if (current == NULL)
       {
           return;
       }
       displayInOrder(current->left, out);
       out << current->data;
       out << " ";
       displayInOrder(current->right, out);
   };
   void displayPreOrder(treeNode *current, std::ostream &out)
   {
       if (current == NULL)
       {
           return;
       }
       out << current->data;
       out << " ";
       displayPreOrder(current->left, out);
       displayPreOrder(current->right, out);
   };
   void displayPostOrder(treeNode *current, std::ostream &out)
   {
       if (current == NULL)
       {
           return;
       }
      
       displayPostOrder(current->left, out);
       displayPostOrder(current->right, out);
       out << current->data;
       out << " ";
   };
protected:
   treeNode * root;
   int numNodes;

public:
   bTree()
   {
       numNode = 0;
       root = NULL;
   };
   bTree(T value)
   {
       numNodes = 1;
       root = new treeNode;
       root->data = value;
       root->left = NULL;
       root->right NULL;

   };
   void insertNode(T value)
   {
       treeNode * newNode = new treeNode;
       newNode->left = NULL;
       newNode->right = NULL;
       newNode->data = value;
       insert(root, newNode);
   };
   ~bTree()
   {
       while (root != NULL)
       {

       }
   };
   void printInOrder(std::ostream)
   {
       printInOrder(root, out);
   };
   void printPreOrder(std::ostream)
   {
       printPreOrder(root, out);
   };
   void printPostOrder(std::ostream)
   {
       printPostOrder(root, out);
   };
};
#endif

Free Plagiarisr x O How Sherlock x D 5 ways Sherlo x Dashboard x D Lab C Programming x D Programming x boost Iterate x C D file:///C: /Users/ For this programming assignment you will be creating a Binary Search Tree. You must as a minimum implement the following methods: Default Constructor Constructor that takes a single int in Destructor Copy constructor An insert element A delete element A contains method A height method Print in-order method Print pre-order method Print post-order method overwrite the double operator Two tree are equal f the trees contains the exact same values in the exact same order. Boolean method to check if the tree is full. Boolean method to check if a path exist in the tree is equal to a passed in sum. ES O Type here to search 511/2017 R120

Explanation / Answer

/*
* C++ Program To Implement BST
*/
# include <iostream>
# include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *left;
struct node *right;
}*root;

/*
* Class Declaration
*/
class BST
{
public:
void find(int, node **, node **);
void insert(int);
void del(int);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
/*
* Main Contains Menu
*/
int main()
{
int choice, num;
BST bst;
node *temp;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<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 choice : ";
cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<"Enter the number to be inserted : ";
   cin>>temp->info;
bst.insert(root, temp);
case 2:
if (root == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>num;
bst.del(num);
break;
case 3:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
   case 4:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal of BST:"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 6:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
}

/*
* Find Element in the Tree
*/
void BST::find(int item, node **par, node **loc)
{
node *ptr, *ptrsave;
if (root == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (item == root->info)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{
if (item == ptr->info)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->left;
   else
   ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}

/*
* Inserting Element into the Tree
*/
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
   }
   else
   {
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}

/*
* Delete Element from the tree
*/
void BST::del(int item)
{
node *parent, *location;
if (root == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{
cout<<"Item not present in tree"<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location);
}

/*
* Case A
*/
void BST::case_a(node *par, node *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}

/*
* Case B
*/
void BST::case_b(node *par, node *loc)
{
node *child;
if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{
root = child;
}
else
{
if (loc == par->left)
par->left = child;
else
par->right = child;
}
}

/*
* Case C
*/
void BST::case_c(node *par, node *loc)
{
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL)
{
ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL)
{
root = suc;
}
else
{
if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}

/*
* Pre Order Traversal
*/
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->info<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}
/*
* In Order Traversal
*/
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<" ";
inorder(ptr->right);
}
}

/*
* Postorder Traversal
*/
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->info<<" ";
}
}

/*
* Display Tree Structure
*/
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
   }
cout<<ptr->info;
display(ptr->left, level+1);
}
}

output:

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---