#include <iostream> #include <string> using namespace std; class binaryTree { pr
ID: 3773128 • Letter: #
Question
#include <iostream>
#include <string>
using namespace std;
class binaryTree
{
private:
struct treeNode
{
string name;
treeNode *left;
treeNode *right;
};
treeNode *root;
void insert(treeNode *&nodePtr, treeNode *&newNode)
{
if(nodePtr==nullptr)
nodePtr=newNode;
else if (newNode->name < nodePtr->name)
insert(nodePtr->left, newNode);
else
insert(nodePtr->right, newNode);
}
void destroySubTree(treeNode *nodePtr)
{
if (nodePtr)
{
if(nodePtr->left)
destroySubTree(nodePtr->left);
if(nodePtr->right)
destroySubTree(nodePtr->right);
delete nodePtr;
}
}
void deleteNode(string nam, treeNode *&nodePtr)
{
if (nam<nodePtr->name)
deleteNode(nam, nodePtr->left);
else if (nam> nodePtr->name)
deleteNode(nam, nodePtr->right);
else
makeDeletion(nodePtr);
}
void makeDeletion(treeNode *&nodePtr)
{
treeNode *tempNodePtr=nullptr;
if (nodePtr == nullptr)
cout << "Cannot delete an empty node" << endl;
else if (nodePtr->right == nullptr)
{
tempNodePtr=nodePtr;
nodePtr=nodePtr->left;
delete tempNodePtr;
}
else
{
tempNodePtr=nodePtr->right;
while(tempNodePtr->left)
tempNodePtr=tempNodePtr->left;
tempNodePtr->left =nodePtr->left;
tempNodePtr=nodePtr;
nodePtr = nodePtr->right;
delete tempNodePtr;
}
}
void displayInOrder(treeNode *nodePtr) const
{
if(nodePtr)
{
displayInOrder(nodePtr->left);
cout << nodePtr->name << endl;
displayInOrder(nodePtr->right);
}
}
void displayPreOrder(treeNode *nodePtr) const
{
if(nodePtr)
{
cout << nodePtr->name << endl;
displayPreOrder(nodePtr->left);
displayPreOrder(nodePtr->right);
}
}
void displayPostOrder(treeNode *nodePtr) const
{
if(nodePtr)
{
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
cout << nodePtr->name << endl;
}
}
public:
binaryTree()
{
root=nullptr;
}
~binaryTree()
{
destroySubTree(root);
}
void insertNode(string nam)
{
treeNode *newNode =nullptr;
newNode = new treeNode;
newNode->name=nam;
newNode->left = newNode->right = nullptr;
insert(root,newNode);
}
bool searchNode(string nam)
{
treeNode *nodePtr = root;
while(nodePtr)
{
if(nodePtr->name == nam)
return true;
else if(nam<nodePtr->name)
nodePtr=nodePtr->left;
else
nodePtr=nodePtr->right;
}
return false;
}
void remove(string nam)
{
deleteNode(nam, root);
}
void displayInOrder() const
{
displayInOrder(root);
}
void displayPreOrder() const
{
displayPreOrder(root);
}
void displayPostOrder() const
{
displayPostOrder(root);
}
};
binaryTree tree;
void menu(void)
{
cout << "What would you like to do with the tree? " << endl;
cout << " I to insert nodes" << endl;
cout << " S to search the tree" << endl;
cout << " D to delete nodes" << endl;
cout << " C to see your tree" << endl;
cout << " Q to quit" << endl;
}
void insert()
{
string nam;
int numNodes;
cout << "How many nodes would you like to insert in the tree?" << endl;
cin >> numNodes;
for(int count=0; count<numNodes; count++)
{
cout << "Enter a name for the tree: ";
cin >> nam;
tree.insertNode(nam);
}
cout << "Your nodes have been inserted into the tree" << endl;
}
void seeTree()
{
cout << "Here is your tree in order traversal: " << endl;
tree.displayInOrder();
cout << endl;
cout << "Here is your tree pre order traversal: " << endl;
tree.displayPreOrder();
cout << endl;
cout << "Here is your tree post order traversal: " << endl;
tree.displayPostOrder();
cout << endl;
}
void search()
{
string nam;
cout << "What would you like to search for? " << endl;
cin >> nam;
if(tree.searchNode(nam))
cout << nam << " was found in the tree." << endl;
else
cout << nam << " was not found in the tree." << endl;
}
void takeOut()
{
string nam;
cout << "Here are the names in the tree: " << endl;
tree.displayInOrder();
cout << "What would you like to delete?" << endl;
cin >> nam;
tree.remove(nam);
cout << nam << " was deleted from the tree" << endl;
}
void doChoice(char choice)
{
switch(choice)
{
case 'I': case 'i' : insert(); break;
case 'S': case 's' : search(); break;
case 'C': case 'c' : seeTree(); break;
case 'D': case 'd' : takeOut(); break;
}
}
int main()
{
char choice;
do
{
menu();
cin >> choice;
doChoice(choice);
} while ((choice != 'Q') && (choice !='q'));
return 0;
}
Explanation / Answer
binarytree.cpp
Code:
main.cpp
Code:
the code to be used for trversing and displayng classes using toString function will include:
mport java.util.*;
import java.io.*;
import java.lang.String;
public class LinkedBSTPT<String extends Comparable<String>> implements BSTPT<String>
{
private Node<String> root;
private Node<String> temp;
private int size;
public LinkedBSTPT()
{
root=null;
size=0;
}
public List<String> inorderTraverse()
{
List<String> list = new ArrayList<String>();
inorderTraverse(root, list);
return list;
}
private void inorderTraverse(Node<String> tree, List<String> list)
{
if(tree!= null)
{
inorderTraverse(tree.left, list);
list.add(tree.value);
inorderTraverse(tree.right, list);
}
}
public Iterator<String> iterator()
{
return inorderTraverse().iterator();
}
public int size()
{
return 1;
}
public boolean isEmpty()
{
return false;
}
public String contains(String element)
{
return contains(root, element);
}
private String contains(Node<String> tree, String element)
{
if(tree==null)
return null;
else
{
int relation = element.compareTo(tree.value);
if(relation==0)
return tree.value;
else if(relation<0)
return contains(tree.left, element);
else
return contains(tree.right, element);
}
}
public String add(String element)
{
Node<String> newNode = new Node<String>(element);
if(root==null)
{
root=newNode;
size++;
temp=root;
return null;
}
else
{
if(temp.right==null)
temp.right=newNode;
else
{
if(temp.left==null)
{
temp.left=newNode;
temp=temp.left;
}
}
return temp.value;
}
}
/*public String toString()
{
return toString(root, 0);
}
private String toString(Node<String> tree, int level)
{
String str = "";
if(tree != null)
{
str += toString(tree.right(), level+1);
for(int i = 1; i <= level; i++)
str = str + "|";
str += tree.value().toString() + " ";
str += toString(tree.left(), level + 1);
}
return str;
}
*/
private class Node<String>
{
private String value;
private Node<String> left, right;
private Node(String v)
{
this(null,v,null);
}
private Node(Node<String> l, String v, Node<String> r)
{
left = l;
value = v;
right = r;
}
public Node left()
{
return this.left;
}
public Node right()
{
return this.right;
}
public String value()
{
return this.value;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.