Binary Search Tree (Part 1):
Note: This is the first part of a 2-part lab. Onlythis part is due on Oct 29. But please get it working or you willstruggle with the second part.
For the second part, the data type will be changing.For now, it is a string.
Contents
Explanation: 2
BST.cpp: 2
Code you must write: 2
bool insert(string s) (7): 2
TNode *find(string s) (4): 2
void printTreeIO(Tnode *n)(3): 2
void printTreePre(Tnode *n) (3): 2
void printTreePost(Tnode *n) (3): 3
TNode *remove(string s)(8) 3
TNode *removeNoKids(TNode *tmp)(5): 3
TNode *removeOneKid(TNode *tmp, boolleftFlag)(7): 3
void setHeight(TNode *n)(10): 3
10 pts for getting everything to work together 3
Methods in CPP I’m Giving You: 3
BST::BST() 3
BST::BST(string s) 3
void BST::clearTree 3
void BST::clearTree(TNode *tmp) 3
void BST::printTreeIO 4
void BST::printTreePre() 4
void BST::printTreePost() 4
BST.HPP (Giving You): 4
/*Phrase.hpp*/ 5
/*Phrase.cpp*/ 5
/*TNode.hpp*/ 6
/*TNode.cpp*/ 6
/*bstmain.cpp*/ 7
Output: 8
Explanation:
For this lab you will be writing the basic methods for a binarysearch tree. The data in the binary search tree is of type Phrase(a class I am giving to you), and, while this lab is due in 1 week,be aware that many of the methods in this lab will be re-used inthe lab that follows it.
To visualize the binary search tree as you are working on it,you can draw it, or you can use numerous on-line visualizers,including this one:
https://www.cs.usfca.edu/~galles/visualization/BST.html
At the end of this document I have included the output from mylab.
The code I am giving you is:
- Phrase.hpp and Phrase.cpp
- TNode.hpp and TNode.cpp
- bstmain.cpp
- BST.hpp
You must write the methods in BST.cpp that are specified(below):
BST.cpp:
Code you must write:
The code you must write: BST.cpp (i.e., the methods associatedwith BST.hpp, right below this section, although I am giving yousome of the methods in there as well)
/*BST.cpp: You must write the BST.cpp and complete the followingmethods:*/
bool insert(string s) (7): this method takes asan input parameter a string (which will go into the phrase field ofthe data when a node is created to be inserted) and returns true ifthe data is inserted successfully, false otherwise.
Be aware: when you insert a new node into the binary searchtree, this method should call the setHeights method to adjust theheights
TNode *find(string s) (4):finds whether s is inthe phrase part of the data in the tree,and, if it is, returns thenode holding s. Otherwise it returns NULL.
void printTreeIO(Tnode *n)(3): recursivefunction that prints out the data in the tree in order
void printTreePre(Tnode *n) (3): a recursivefunction that prints out the datain the tree in pre-order
void printTreePost(Tnode *n) (3): a recursivefunction that prints out the data in the tree in post-order
TNode *remove(string s)(8) – this methodremoves a node from the tree, and returns that node. There are 3cases when you remove a node: either the node being removed has nochildren (left or right), in which case this method calls themethod removeNoKids, the node you are removing has only one child,in which case the method calls removeOneKid (with a Boolean flagset to true if there is a left child, and false if there is a rightchild), or the node being removed has both a left and a rightchild, in which you replace the node being removed with theappropriate replacement child, and then remove the node used as areplacement by calling either removeNoKids or removeOneKid,depending on which is appropriate.
NOTE: I used the rightmost of the left child as a replacement.To get my output, you must do the same.
TNode *removeNoKids(TNode *tmp)(5): forremoving a node with no children
TNode *removeOneKid(TNode *tmp, boolleftFlag)(7): for removing a node with one child, with theleftFlag indicating whether the node’s child is either the leftchild or the right child.
void setHeight(TNode *n)(10): This method setsthe heights of the nodes in a tree. Once a node is inserted, onlythe node’s ancestors can have their height changed. Thus you shouldset the height of the node being inserted (to 1) and then adjustthe heights of the node’s parent, grandparent, etc. up until eitherthe height of the node doesn’t change or you hit the root.
20 pts for getting everything to work together
Methods in CPP I’m Giving You:
BST::BST() {
root = NULL;
}
BST::BST(string s) {
root = new TNode(s);
}
void BST::clearTree() {
if (root == NULL) {
cout << \"Tree already empty\" <<endl;
}
else {
cout << endl << \"Clearing Tree:\"<< endl;
clearTree(root);
root = NULL;
}
}
void BST::clearTree(TNode *tmp) {
if (tmp == NULL) {
return;
}
else {
clearTree(tmp->left);
clearTree(tmp->right);
tmp->printNode();
delete(tmp);
}
}
/*Note: the following three functions’ sole job is to callprintTreeIO(TNode *t),printTreePre(TNode *t), andprintTreePost(TNode *t) while printint out which
Function is being called.
YOU MUST STILL WRITE THE RECURSIVE VERSION OF THESEFUNCTIONS!!!*/
void BST::printTreeIO() { // Just the start – you must write therecursive version
if (root == NULL ) {
cout << \"Empty Tree\" << endl;
}
else {
cout << endl<<\"Printing In Order:\"<<endl;
printTreeIO(root);
}
}
void BST::printTreePre() {
if (root == NULL ) {
cout << \"Empty Tree\" << endl;
}
else {
cout << endl<<\"Printing PreOrder:\"<<endl;
printTreePre(root);
}
}
void BST::printTreePost() {
if (root == NULL ) {
cout << \"Empty Tree\" << endl;
}
else {
cout << endl<<\"Printing PostOrder:\"<<endl;
printTreePost(root);
}
}
BST.HPP (Giving You):
Here is the accompanying BST.hpp code:
#ifndef BST_HPP_
#define BST_HPP_
#include \"TNode.hpp\"
class BST {
TNode *root;
public:
BST();
BST(string s);
bool insert(string s);
TNode *find(string s);
void printTreeIO();
void printTreeIO(TNode*n);
void printTreePre();
void printTreePre(TNode*n);
void printTreePost();
void printTreePost(TNode*n);
void clearTree();
void clearTree(TNode*tmp);
TNode *remove(string s);
TNode *removeNoKids(TNode *tmp);
TNode *removeOneKid(TNode *tmp,bool leftFlag);
void setHeight(TNode *n);
};
#endif /* BST_HPP_ */
#################################################################################
/*Phrase.hpp*/
#ifndef PHRASE_HPP_
#define PHRASE_HPP_
#include
using namespace std;
class Phrase{
friend class TNode;
friend class BST;
string phrase;
public:
Phrase(string s);
Phrase();
};
#endif /* PHRASE_HPP_ */
/*Phrase.cpp*/
#include
#include
#include \"Phrase.hpp\"
using namespace std;
Phrase::Phrase(string s) {
phrase = s;
}
Phrase::Phrase() {
phrase = \"\";
}
############################################################################
/*TNode.hpp*/
#ifndef TNODE_HPP_
#define TNODE_HPP_
#include
#include \"Phrase.hpp\"
using namespace std;
class TNode{
friend class BST;
TNode *left;
TNode *right;
TNode *parent;
Phrase *data;
int height;
public:
TNode(string s);
TNode();
~TNode();
void printNode();
};
#endif /* TNODE_HPP_ */
/*TNode.cpp*/
#include
#include
#include \"TNode.hpp\"
using namespace std;
TNode::TNode(string s) {
left = NULL;
right = NULL;
parent = NULL;
height = 1;
data = new Phrase(s);
}
TNode::TNode() {
left = NULL;
right = NULL;
parent = NULL;
height = 1;
data = new Phrase();
}
TNode::~TNode(){
cout <<\"Deleting\"<phrase<<endl;
}
void TNode::printNode() {
cout <phrase<<\",\"<endl;
}
#################################################################################
/*bstmain.cpp*/
#include \"BST.hpp\"
#include
using namespace std;
int main() {
string arr[] = {\"e\",\"g\",\"f\",\"a\",\"c\",\"d\",\"b\"};
BST *tree = new BST();
for (int i = 0; i < 7; i++){
cout << arr[i]<<\", \";
tree->insert(arr[i]);
}
cout << endl;
tree->printTreePre();
tree->printTreeIO();
tree->printTreePost();
tree->clearTree();
cout <<\"************************************\" <<endl;
string arr3[] ={\"i\",\"was\",\"contemplating\",\"the\",\"immortal\",\"words\",\"of\",\"socrates\",\"who\",\"said,\",\"i\",\"drank\",\"what\"};
for (int i = 0; i < 13;i++) {
cout << arr3[i]<<\", \";
tree->insert(arr3[i]);
}
cout << endl;
tree->printTreePre();
tree->printTreeIO();
tree->printTreePost();
cout << endl<<\"REMOVING DRANK\"<< endl;
tree->remove(\"drank\");
tree->printTreePre();
tree->printTreeIO();
tree->printTreePost();
cout << endl<<\"REMOVING IMMORTAL\"<< endl;
tree->remove(\"immortal\");
tree->printTreePre();
tree->printTreeIO();
tree->printTreePost();
cout << endl<<\"REMOVING WAS\"<< endl;
tree->remove(\"was\");
tree->printTreePre();
tree->printTreeIO();
tree->printTreePost();
cout << endl<<\"REMOVING I\" <<endl;
tree->remove(\"i\");
tree->printTreePre();
tree->printTreeIO();
tree->printTreePost();
tree->clearTree();
return 0;
}
