Question: #include using namespace std; struct BinNode { int key; BinNode *left; BinNode *right; }; class myBST { public: myBST () { root = NULL; }
#include
using namespace std;
struct BinNode {
int key;
BinNode *left;
BinNode *right;
};
class myBST {
public:
myBST () { root = NULL; }
~myBST ();
BinNode* findInBST(int k); // return NULL if not found
void insertToBST(int k);
void preOrderTraversal();
void postOrderTraversal();
void inOrderTraversal();
void rotatedPrintTree();
private:
BinNode* root;
void free_helper(BinNode* node);
// BinNode* find_helper(BinNode* node, int k); //optional helper function for findInBST
// void insert_helper(BinNode* node, int k); //optional helper function for insertToBST
void preOrder(BinNode* node);
void postOrder(BinNode* node);
void inOrder(BinNode* node);
void rotatedPrint(BinNode* node, int d);
};
myBST::~myBST() {
free_helper(root);
}
void myBST::free_helper(BinNode* node) {
if(node != NULL) {
free_helper(node->left);
free_helper(node->right);
delete node;
}
}
// //***************************
// //recursive implementation***
// //***************************
// BinNode* myBST::findInBST(int k) {
// }
// BinNode* myBST::find_helper(BinNode* node, int k) {
// }
//*******************************
/on-recursive implementation***
//*******************************
BinNode* myBST::findInBST(int k) {
}
// //***************************
// //recursive implementation***
// //***************************
// void myBST::insertToBST(int k) {
// }
// void myBST::insert_helper(BinNode* node, int k) {
// }
//*******************************
/on-recursive implementation***
//*******************************
void myBST::insertToBST(int k) {
}
//***********************************
//preOrderTraversal implementation***
//***********************************
void myBST::preOrderTraversal() {
preOrder(root);
cout
}
void myBST::preOrder(BinNode* node) {
}
//************************************
//postOrderTraversal implementation***
//************************************
void myBST::postOrderTraversal() {
postOrder(root);
cout
}
void myBST::postOrder(BinNode* node) {
}
//**********************************
//inOrderTraversal implementation***
//**********************************
void myBST::inOrderTraversal() {
inOrder(root);
cout
}
void myBST::inOrder(BinNode* node) {
}
//***********************************
//print the tree (left rotated)******
//***********************************
void myBST::rotatedPrintTree() {
rotatedPrint(root, 0);
}
void myBST::rotatedPrint(BinNode* node, int d) {
if(node == NULL)
return;
if (node->right != NULL)
rotatedPrint(node->right, d+1);
for(int i = 0; i
cout
cout key
if (node->left != NULL)
rotatedPrint(node->left, d+1);
}
int main()
{
myBST testTree;
int user_input = 0;
while (user_input != -1) {
cout
cout
cout
cin >> user_input;
if (user_input >= 0 and user_input
testTree.insertToBST(user_input);
else if (user_input != -1)
cout
}
cout
testTree.rotatedPrintTree();
cout
testTree.preOrderTraversal();
cout
testTree.postOrderTraversal();
cout
testTree.inOrderTraversal();
user_input = 0;
while (user_input != -1) {
cout
cout
cout
cin >> user_input;
if (user_input >= 0 and user_input
BinNode* temp = testTree.findInBST(user_input);
if(temp == NULL)
cout
else {
cout
if(temp->left != NULL)
cout left->key
if(temp->right != NULL)
cout right->key
}
}
else if (user_input != -1)
cout
}
return 0;
}
In this assignment, you are asked to implement several functions in a Binary Search Tree (BST) class, called myBST, in bst.cpp. 1. Implement the public function findInBST (). You can choose to do this using recursion or not. If you choose to use recursion, a helper private function find helper () may be helpful. (non-recursive is the default; if you want to use recursion, you'll need to comment/ uncommented certain parts in the code.) 2. Implement the public function insertToBST (). You can choose to do this using recursion or not. If you choose to use recursion, a helper private function insert_helper ) may be helpful. (non-recursive is the default; if you want to use recursion, you'll need to comment/ uncommented certain parts in the code.) 3. Implement the private functions preOrder , postOrder (), and inOrder ) which are used to implement public functions preOrderTraversal (), postOrderTraversal (), and inOrderTraversal ), respectively. preOrder, postorder, and inOrder should be recursive functions, and no loop should be used in them Bevond writing codes in this assignment (Just to think about, no submission or gradin The function rotatedPrintTree ( ) prints the BST in a "left-rotated" fashion, i.e., the root on the left and the leaves on the right. For example, 20 10 15 10 20 15 Read carefully the functions for printing the tree (left-rotated), and think about how this function works. Also, think about why we use this function to print the left-rotated tree. Think about writing a function to normally (not rotated) print an arbitrary tree. Which printing is easier to implement? In this assignment, you are asked to implement several functions in a Binary Search Tree (BST) class, called myBST, in bst.cpp. 1. Implement the public function findInBST (). You can choose to do this using recursion or not. If you choose to use recursion, a helper private function find helper () may be helpful. (non-recursive is the default; if you want to use recursion, you'll need to comment/ uncommented certain parts in the code.) 2. Implement the public function insertToBST (). You can choose to do this using recursion or not. If you choose to use recursion, a helper private function insert_helper ) may be helpful. (non-recursive is the default; if you want to use recursion, you'll need to comment/ uncommented certain parts in the code.) 3. Implement the private functions preOrder , postOrder (), and inOrder ) which are used to implement public functions preOrderTraversal (), postOrderTraversal (), and inOrderTraversal ), respectively. preOrder, postorder, and inOrder should be recursive functions, and no loop should be used in them Bevond writing codes in this assignment (Just to think about, no submission or gradin The function rotatedPrintTree ( ) prints the BST in a "left-rotated" fashion, i.e., the root on the left and the leaves on the right. For example, 20 10 15 10 20 15 Read carefully the functions for printing the tree (left-rotated), and think about how this function works. Also, think about why we use this function to print the left-rotated tree. Think about writing a function to normally (not rotated) print an arbitrary tree. Which printing is easier to implement
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help