Question

In: Computer Science

Binary Search Tree (Part 1): Note: This is the first part of a 2-part lab. Only...

Binary Search Tree (Part 1):

Note: This is the first part of a 2-part lab. Only this part is due on Oct 29. But please get it working or you will struggle 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, bool leftFlag)(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 binary search 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 in the 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 my lab.

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 associated with BST.hpp, right below this section, although I am giving you some of the methods in there as well)

/*BST.cpp: You must write the BST.cpp and complete the following methods:*/

bool insert(string s) (7): this method takes as an input parameter a string (which will go into the phrase field of the data when a node is created to be inserted) and returns true if the data is inserted successfully, false otherwise.

Be aware: when you insert a new node into the binary search tree, this method should call the setHeights method to adjust the heights

TNode *find(string s) (4):finds whether s is in the phrase part of the data in the tree,and, if it is, returns the node holding s. Otherwise it returns NULL.

void printTreeIO(Tnode *n)(3): recursive function that prints out the data in the tree in order

void printTreePre(Tnode *n) (3): a recursive function that prints out the datain the tree in pre-order

void printTreePost(Tnode *n) (3): a recursive function that prints out the data in the tree in post-order

TNode *remove(string s)(8) – this method removes a node from the tree, and returns that node. There are 3 cases when you remove a node: either the node being removed has no children (left or right), in which case this method calls the method removeNoKids, the node you are removing has only one child, in which case the method calls removeOneKid (with a Boolean flag set to true if there is a left child, and false if there is a right child), or the node being removed has both a left and a right child, in which you replace the node being removed with the appropriate replacement child, and then remove the node used as a replacement 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): for removing a node with no children

TNode *removeOneKid(TNode *tmp, bool leftFlag)(7): for removing a node with one child, with the leftFlag indicating whether the node’s child is either the left child or the right child.

void setHeight(TNode *n)(10): This method sets the heights of the nodes in a tree. Once a node is inserted, only the node’s ancestors can have their height changed. Thus you should set the height of the node being inserted (to 1) and then adjust the heights of the node’s parent, grandparent, etc. up until either the 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 call printTreeIO(TNode *t),printTreePre(TNode *t), and printTreePost(TNode *t) while printint out which

Function is being called.

YOU MUST STILL WRITE THE RECURSIVE VERSION OF THESE FUNCTIONS!!!*/

void BST::printTreeIO() { // Just the start – you must write the recursive 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 <iostream>

using namespace std;

class Phrase{

friend class TNode;

friend class BST;

string phrase;

public:

Phrase(string s);

Phrase();

};

#endif /* PHRASE_HPP_ */

/*Phrase.cpp*/

#include <iostream>

#include <string>

#include "Phrase.hpp"

using namespace std;

Phrase::Phrase(string s) {

phrase = s;

}

Phrase::Phrase() {

phrase = "";

}

############################################################################

/*TNode.hpp*/

#ifndef TNODE_HPP_

#define TNODE_HPP_

#include <iostream>

#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 <iostream>

#include <string>

#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 "<<data->phrase<<endl;

}

void TNode::printNode() {

cout << data->phrase<<","<<height<<endl;

}

#################################################################################

/*bstmain.cpp*/

#include "BST.hpp"

#include <iostream>

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;

}

Solutions

Expert Solution

Code:

#include "TNode.hpp"
#include "BST.hpp"
#include <iostream>
#include <stdlib.h>
using namespace std;

BST::BST() {
        root = NULL;
}

BST::BST(string s) {
        root = new TNode(s);
}

void BST::printTreeIO() {
        if (root == NULL ) {
                cout << "Empty Tree" << endl;
        }
        else {
                cout << endl<<"Printing In Order:" <<endl;
                printTreeIO(root);
        }
}

void BST::printTreeIO(TNode *t) {
        if (root == NULL ) {
                cout << "Empty Tree" << endl;
        }
        else {
                cout << endl <<"Printing In Order:" << endl;
                printTreeIO(root->left);
                root->printNode();
                printTreeIO(root->right);
        }
}

void BST::printTreePre() {
        if (root == NULL ) {
                cout << "Empty Tree" << endl;
        }
        else {
                cout << endl<<"Printing PreOrder:" <<endl;
                printTreePre(root);
        }
}

void BST::printTreePre(TNode *t) {
        if (root == NULL ) {
                cout << "Empty Tree" << endl;
        }
        else {
                cout << endl <<"Printing PreOrder:" <<endl;
                root->printNode();
                printTreeIO(root->left);
                printTreeIO(root->right);
        }
}

void BST::printTreePost() {
        if (root == NULL ) {
                cout << "Empty Tree" << endl;
        }
        else {
                cout << endl<<"Printing PostOrder:" <<endl;
                printTreePost(root);
        }
}

void BST::printTreePost(TNode *t) {
        if (root == NULL ) {
                cout << "Empty Tree" << endl;
        }
        else {
                cout << endl <<"Printing PostOrder:" <<endl;
                printTreeIO(root->left);
                printTreeIO(root->right);
                root->printNode();
        }
}


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);
        }
}

bool BST::insert(string s) {
        if (root == NULL) {
                root = new TNode(s);
                return true;
        }
        else {
                TNode * n = root;
                while (n != NULL) {
                        if (s < n->data->phrase) {
                                if (n->left == NULL) {
                                        n->left = new TNode(s);
                                        n->left->parent = n;
                                        return true;
                                }
                                else {
                                        n->left = n;
                                }
                        }
                        else if (s > n->data->phrase) {
                                if (n->right == NULL) {
                                        n->right = new TNode(s);
                                        n->right->parent = n;
                                        return true;
                                }
                                else {
                                        n->right = n;
                                }
                        }
                        else {
                                return false;
                        }
                }
        }
        return false;
}

TNode* BST::find(string s){
        while (root != NULL) {
                if (s > root->data->phrase) {
                        root = root->right;
                }
                else if (s < root->data->phrase) {
                        root = root->left;
                }
                else {
                        return root;
                }
        }
        return NULL;
}

TNode* BST::remove(string s){
        TNode * rem = find(s);
        if(rem->right == NULL && rem->left == NULL){              //NO CHILDREN
                removeNoKids(rem);
        }
        else if(rem->right == NULL ^ rem->left == NULL){  //ONE CHILD
                if(rem->left == NULL){                                                       //The child is to the right
                        removeOneKid(rem, false);
                }
                else if(rem->right == NULL){                                 //The child is to the left
                        removeOneKid(rem, true);
                }
        }
        else if(rem->right != NULL && rem->left != NULL){ //TWO CHILDREN
                TNode * temp = rem;
                temp = temp->left;
                while(temp->right != NULL){
                        temp = temp->right;
                }
                rem->data->phrase = temp->data->phrase;
                if(temp->left == NULL){
                        removeNoKids(temp);
                }
                else{
                        removeOneKid(temp, true);
                }
        }
        return rem;
}

TNode * BST::removeNoKids(TNode * temp){
        if(temp->parent->data->phrase < s){                         //Our node is to the right
                temp->parent->right == NULL;
        }
        else{                                                                                   //Our node is to the left
                temp->parent->left == NULL;
        }
        return temp;
}

TNode * BST::removeOneKid(TNode * temp, bool leftFlag){
        if(temp->parent->data->phrase > s){                         //Our node is to the left
                if(leftFlag){                                                           //Child is on the left
                        temp->parent->left = temp->left;
                        temp->left->parent = temp->parent;
                }
                else{                                                                           //Child is on the right
                        temp->parent->left = temp->right;
                        temp->right->parent = temp->parent;
                }
        }
        else{                                                                                   //Our node is to the right
                if(leftFlag){                                                           //Child is on the left
                        temp->parent->right = temp->left;
                        temp->left->parent = temp->parent;
                }
                else{                                                                           //Child is on the right
                        temp->parent->right = temp->right;
                        temp->right->parent = temp->parent;
                }
        }
        return temp;
}

void BST::setHeight(TNode * n){
        int prevHeight = 1;
        int newHeight = 0;
        n = n->parent;
        while(prevHeight != newHeight && n->parent != NULL){
                prevHeight = n->height;
                newHeight = (n->right->height < n->left->height) ? n->left->height : n->right->height;
                newHeight++;
                n->height = newHeight;
        }
}

Screenshots:

-------------------------END---------------------

Please give a thumbs up(upvote) if you liked the answer.


Related Solutions

Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the...
Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the template provided under the PolyLearn assignment, using the class TreeNode that is also provided. You may (should) implement helper methods that make your code easier to write, read, and understand. You will also need to write test cases of your own as you develop the methods. You may use iterative and/or recursive functions in your implementation. The following starter files are available . •...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree worst case and best case time. Learning Outcomes Describe AVL tree structure Trace and implement AVL tree operations Explain and prove AVL tree performance
PLEASE READ CAREFULY AND EXPLAIN YOUR WORK: (JavaScript) only Search the Tree: A binary search tree...
PLEASE READ CAREFULY AND EXPLAIN YOUR WORK: (JavaScript) only Search the Tree: A binary search tree is a data structure that consists of JavaScript objects called "nodes". A tree always has a root node which holds its own integer value property and can have up to two child nodes (or leaf nodes), a left and right property. A leaf node holds a value attribute and, likewise, a left and right attribute each potentially pointing to another node in the binary...
​Define a tree. Distinguish between a tree and a binary tree. Distinguish between a binary tree and a binary search tree.
Define a tree. Distinguish between a tree and a binary tree. Distinguish between a binary tree and a binary search tree.
Beginning with an empty binary search tree, what binary search tree is formed when you insert...
Beginning with an empty binary search tree, what binary search tree is formed when you insert the following values in the given order – consider there alphabetical position for comparison. a. W, T, N, J, E, B, A b. W, T, N, A, B, E, J c. A, B, W, J, N, T, E d. B, T, E, A, N, W, J Alphabetical positions: A-1, B-2, E-5, J-10, N-14,T-20,W-23
Question 2: Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary...
Question 2: Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary Search Tree in ascending or deceasing order. The order type is an input to the method and can be "ascending" or "descending". The ascending input would return the node values of the tree beginning with the smallest and ending with the largest, descending returns the opposite. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify...
Binary Tree Create a binary search tree using the given numbers in the order they’re presented....
Binary Tree Create a binary search tree using the given numbers in the order they’re presented. State if the resulting tree is FULL and/or BALANCED. 37, 20, 18, 56, 40, 42, 12, 5, 6, 77, 20, 54
1. Modify a binary search tree implementation code (that AVL tree code depends on) to print...
1. Modify a binary search tree implementation code (that AVL tree code depends on) to print out the data value for each node it encounters in the insert operation. Remember that the module AVL tree code gets part of its functionality from the BST type, since an AVL tree is a binary search tree, but adds some additional functionality. 2. Add code to the main method to meet the following requirements: (a) Create an AVL tree to hold names stored...
Write the binary tree representation for the Binary Search for also 17 elements and give the...
Write the binary tree representation for the Binary Search for also 17 elements and give the worst-case
1. Draw a binary search tree as a single root node holding a string as the...
1. Draw a binary search tree as a single root node holding a string as the data element. Each string inserted into a node in the tree will be for a character in a game. Then, draw a new tree each time you insert a new node into the tree holding a string Insert 4 nodes total, including the root. This means the new nodes will need to be inserted at the correct child to maintain the BST property.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT