Homework SourseI have a Programming is Binary Tree Search BTS for strings w
I have a Programming is Binary Tree Search (BTS) for strings with pointers, but I do not know how to change BTS for strings using arrays.
Can you help me to change the method, please?
This is programming:
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
struct myNode
{
string data;
struct myNode *lNode;
struct myNode *rNode;
} *roNode;
class myBTS
{
public:
void seek(string, myNode **, myNode **);
void add(myNode *, myNode*);
void rem(string);
void caseOne(myNode *, myNode *);
void caseTwo(myNode *, myNode *);
void caseThree(myNode *, myNode *);
void print(myNode *, char);
myBTS()
{
roNode = NULL;
}
};
// Main method
int main ()
{
int myOptions;
string rData;
myBTS mybst;
myNode *tmp;
while (1)
{
cout << \"-----------------------------------------\" << endl;
cout << \"Welcome to Binary Search Tree Programming\" << endl;
cout << \"-----------------------------------------\" << endl;
cout << \"1. Add Data \" << endl;
cout << \"2. Remove Data \" << endl;
cout << \"3. Print Data \" << endl;
cout << \"4. Exit \" << endl;
cout << \"Enter Option : \";
cin >> myOptions;
switch(myOptions)
{
case 1:
tmp = new myNode;
cout << \"Enter data to add : \";
cin >> tmp->data;
mybst.add(roNode, tmp);
break;
case 2:
if (roNode == NULL)
{
cout << \"Tree empty!!!\" << endl;
continue;
}
else
{
cout << \"Enter data to remove: \";
cin >> rData;
mybst.rem(rData);
}
break;
case 3:
cout << \"Print Tree:\" << endl;
mybst.print(roNode,1);
cout << endl;
break;
case 4:
exit (1);
default:
cout << \"Wrong Option!!!\" << endl;
}
}
}
// Data in BTS
void myBTS::seek(string sData, myNode **myPar, myNode **myLoc)
{
myNode *ptr1, *ptr2;
if (roNode == NULL)
{
*myLoc = NULL;
*myPar = NULL;
return;
}
if (sData == roNode-> data)
{
*myLoc = roNode;
*myPar = NULL;
return;
}
if (sData < roNode-> data)
ptr1 = roNode->lNode;
else
ptr1 = roNode-> rNode;
ptr2 = roNode;
while (ptr1 != NULL)
{
if (sData == ptr1->data)
{
*myLoc = ptr1;
*myPar = ptr2;
return;
}
ptr2 = ptr1;
if (sData < ptr1 -> data)
ptr1 = ptr1 ->lNode;
else
ptr1 = ptr1 -> rNode;
}
*myLoc = NULL;
*myPar = ptr2;
}
// Add Data into BTS
void myBTS::add(myNode *myTree, myNode *myNewNode)
{
if (roNode == NULL)
{
roNode = new myNode;
roNode -> data = myNewNode ->data;
roNode -> lNode = NULL;
roNode -> rNode = NULL;
cout << \"Root data is added successfully\" << endl;
return;
}
if (myTree -> data == myNewNode -> data)
{
cout << \"Data already in BTS\" << endl;
return;
}
if (myTree -> data > myNewNode -> data)
{
if (myTree ->lNode != NULL)
{
add (myTree -> lNode, myNewNode);
}
else
{
myTree -> lNode = myNewNode;
(myTree -> lNode) -> lNode = NULL;
(myTree -> lNode) -> rNode = NULL;
cout << \"Data added to the Left successfully\" << endl;
return;
}
}
if (myTree -> rNode != NULL)
{
add(myTree -> rNode, myNewNode);
}
else
{
myTree -> rNode = myNewNode;
(myTree -> rNode) -> lNode = NULL;
(myTree -> rNode) -> rNode = NULL;
cout << \"Data added to the Right successfully\" << endl;
return;
}
}
//Remove data from BTS
void myBTS:: rem(string sData)
{
myNode *myParent, *myLocation;
if (roNode == NULL)
{
cout << \"Empty BTS\" << endl;
return;
}
seek (sData, &myParent, &myLocation);
if (myLocation == NULL)
{
cout << \"Data not in BTS\" << endl;
return;
}
if (myLocation -> lNode == NULL && myLocation -> rNode == NULL)
caseOne (myParent, myLocation);
if (myLocation -> lNode != NULL && myLocation -> rNode == NULL)
caseTwo (myParent, myLocation);
if (myLocation -> lNode == NULL && myLocation -> rNode != NULL)
caseTwo (myParent, myLocation);
if (myLocation -> lNode != NULL && myLocation -> rNode != NULL)
caseTwo (myParent, myLocation);
free(myLocation);
}
// Case One
void myBTS:: caseOne (myNode *myPar, myNode *myLoc)
{
if (myPar == NULL)
{
roNode = NULL;
}
else
{
if (myLoc == myPar -> lNode)
myPar -> lNode = NULL;
else
myPar -> rNode = NULL;
}
}
// Case Two
void myBTS:: caseTwo (myNode *myPar, myNode *myLoc)
{
myNode *child;
if (myLoc -> lNode != NULL)
child = myLoc -> lNode;
else
child = myLoc -> rNode;
if (myPar == NULL)
{
roNode = child;
}
else
{
if (myLoc == myPar -> lNode)
myPar -> lNode = child;
else
myPar -> rNode = child;
}
}
// Case Three
void myBTS:: caseThree (myNode *myPar, myNode *myLoc)
{
myNode *ptr1, *ptr2, *successor, *parsuccessor;
ptr2 = myLoc;
ptr1 = myLoc -> rNode;
while (ptr1 -> lNode != NULL)
{
ptr2 = ptr1;
ptr1 = ptr1 -> lNode;
}
successor = ptr1;
parsuccessor = ptr2;
if (successor -> lNode == NULL && successor -> rNode == NULL)
caseOne(parsuccessor, successor);
else
caseTwo(parsuccessor, successor);
if (myPar == NULL)
{
roNode = successor;
}
else
{
if (myLoc == myPar -> lNode)
myPar -> lNode = successor;
else
myPar -> rNode = successor;
}
successor -> lNode = myLoc -> lNode;
successor -> rNode = myLoc -> rNode;
}
// Display Tree Structure
void myBTS::print(myNode *ptr1, char myLevel)
{
int i;
if (ptr1 != NULL)
{
print (ptr1 -> rNode, myLevel+1);
cout << endl;
if (ptr1 == roNode)
cout << \"Root-->: \";
else
{
for (i = 0; i < myLevel; i++)
cout << \" \";
}
cout << ptr1 -> data;
print (ptr1-> lNode, myLevel+1);
}
}
Solution
Solution:
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
struct myNode
{
string data;
struct myNode *lNode;
struct myNode *rNode;
} *roNode;
class myBTS
{
public:
void seek(string, myNode **, myNode **);
void add(myNode *, string);
void rem(string);
void caseOne(myNode *, myNode *);
void caseTwo(myNode *, myNode *);
void caseThree(myNode *, myNode *);
void print(myNode *, char);
myBTS()
{
roNode = NULL;
}
};
// Main method
int main ()
{
int myOptions;
string rData, iData;
myBTS mybst;
myNode *tmp;
while (1)
{
cout << \"-----------------------------------------\" << endl;
cout << \"Welcome to Binary Search Tree Programming\" << endl;
cout << \"-----------------------------------------\" << endl;
cout << \"1. Add Data \" << endl;
cout << \"2. Remove Data \" << endl;
cout << \"3. Print Data \" << endl;
cout << \"4. Exit \" << endl;
cout << \"Enter Option : \";
cin >> myOptions;
switch(myOptions)
{
case 1:
tmp = new myNode;
cout << \"Enter data to add : \";
cin >> iData;
mybst.add(roNode, iData);
break;
case 2:
if (roNode == NULL)
{
cout << \"Tree empty!!!\" << endl;
continue;
}
else
{
cout << \"Enter data to remove: \";
cin >> rData;
mybst.rem(rData);
}
break;
case 3:
cout << \"Print Tree:\" << endl;
mybst.print(roNode,1);
cout << endl;
break;
case 4:
exit (1);
default:
cout << \"Wrong Option!!!\" << endl;
}
}
}
// Data in BTS
void myBTS::seek(string sData, myNode **myPar, myNode **myLoc)
{
myNode *ptr1, *ptr2;
if (roNode == NULL)
{
*myLoc = NULL;
*myPar = NULL;
return;
}
if (sData == roNode-> data)
{
*myLoc = roNode;
*myPar = NULL;
return;
}
if (sData < roNode-> data)
ptr1 = roNode->lNode;
else
ptr1 = roNode-> rNode;
ptr2 = roNode;
while (ptr1 != NULL)
{
if (sData == ptr1->data)
{
*myLoc = ptr1;
*myPar = ptr2;
return;
}
ptr2 = ptr1;
if (sData < ptr1 -> data)
ptr1 = ptr1 ->lNode;
else
ptr1 = ptr1 -> rNode;
}
*myLoc = NULL;
*myPar = ptr2;
}
// Add Data into BTS
void myBTS::add(myNode *myTree, string myNewNode)
{
myNode *myParent, *myLocation;
seek (myNewNode, &myParent, &myLocation);
if (roNode == NULL)
{
roNode = new myNode;
roNode -> data = myNewNode;
roNode -> lNode = NULL;
roNode -> rNode = NULL;
cout << \"Root data is added successfully\" << endl;
return;
}
if (myTree -> data == myNewNode)
{
cout << \"Data already in BTS\" << endl;
return;
}
if (myTree -> data > myNewNode)
{
if (myTree ->lNode != NULL)
{
add (myTree -> lNode, myNewNode);
}
else
{
myTree -> lNode = myParent;
(myTree -> lNode) -> lNode = NULL;
(myTree -> lNode) -> rNode = NULL;
cout << \"Data added to the Left successfully\" << endl;
return;
}
}
if (myTree -> rNode != NULL)
{
add(myTree -> rNode, myNewNode);
}
else
{
myTree -> rNode = myParent;
(myTree -> rNode) -> lNode = NULL;
(myTree -> rNode) -> rNode = NULL;
cout << \"Data added to the Right successfully\" << endl;
return;
}
}
//Remove data from BTS
void myBTS:: rem(string sData)
{
myNode *myParent, *myLocation;
if (roNode == NULL)
{
cout << \"Empty BTS\" << endl;
return;
}
seek (sData, &myParent, &myLocation);
if (myLocation == NULL)
{
cout << \"Data not in BTS\" << endl;
return;
}
if (myLocation -> lNode == NULL && myLocation -> rNode == NULL)
caseOne (myParent, myLocation);
if (myLocation -> lNode != NULL && myLocation -> rNode == NULL)
caseTwo (myParent, myLocation);
if (myLocation -> lNode == NULL && myLocation -> rNode != NULL)
caseTwo (myParent, myLocation);
if (myLocation -> lNode != NULL && myLocation -> rNode != NULL)
caseTwo (myParent, myLocation);
free(myLocation);
}
// Case One
void myBTS:: caseOne (myNode *myPar, myNode *myLoc)
{
if (myPar == NULL)
{
roNode = NULL;
}
else
{
if (myLoc == myPar -> lNode)
myPar -> lNode = NULL;
else
myPar -> rNode = NULL;
}
}
// Case Two
void myBTS:: caseTwo (myNode *myPar, myNode *myLoc)
{
myNode *child;
if (myLoc -> lNode != NULL)
child = myLoc -> lNode;
else
child = myLoc -> rNode;
if (myPar == NULL)
{
roNode = child;
}
else
{
if (myLoc == myPar -> lNode)
myPar -> lNode = child;
else
myPar -> rNode = child;
}
}
// Case Three
void myBTS:: caseThree (myNode *myPar, myNode *myLoc)
{
myNode *ptr1, *ptr2, *successor, *parsuccessor;
ptr2 = myLoc;
ptr1 = myLoc -> rNode;
while (ptr1 -> lNode != NULL)
{
ptr2 = ptr1;
ptr1 = ptr1 -> lNode;
}
successor = ptr1;
parsuccessor = ptr2;
if (successor -> lNode == NULL && successor -> rNode == NULL)
caseOne(parsuccessor, successor);
else
caseTwo(parsuccessor, successor);
if (myPar == NULL)
{
roNode = successor;
}
else
{
if (myLoc == myPar -> lNode)
myPar -> lNode = successor;
else
myPar -> rNode = successor;
}
successor -> lNode = myLoc -> lNode;
successor -> rNode = myLoc -> rNode;
}
// Display Tree Structure
void myBTS::print(myNode *ptr1, char myLevel)
{
int i;
if (ptr1 != NULL)
{
print (ptr1 -> rNode, myLevel+1);
cout << endl;
if (ptr1 == roNode)
cout << \"Root-->: \";
else
{
for (i = 0; i < myLevel; i++)
cout << \" \";
}
cout << ptr1 -> data;
print (ptr1-> lNode, myLevel+1);
}
}
Result:
-----------------------------------------
Welcome to Binary Search Tree Programming
-----------------------------------------
1. Add Data
2. Remove Data
3. Print Data
4. Exit
Enter Option : 1
Enter data to add : ax
Root data is added successfully
-----------------------------------------
Welcome to Binary Search Tree Programming
-----------------------------------------
1. Add Data
2. Remove Data
3. Print Data
4. Exit
Enter Option : 1
Enter data to add : er
Data added to the Right successfully
-----------------------------------------
Welcome to Binary Search Tree Programming
-----------------------------------------
1. Add Data
2. Remove Data
3. Print Data
4. Exit
Enter Option : 1
Enter data to add : cx
Data added to the Right successfully
