I have a Programming is Binary Tree Search (BTS) for strings with pointers, but
ID: 3927519 • Letter: I
Question
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);
}
}
Explanation / Answer
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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.