C++ I had to create a binary search tree and I have completed all functions exce

Question

C++

I had to create a binary search tree and I have completed all functions except for remove and height. Both must be done recursively with the usage of a private helper function. Please help!

I have included an algorithm for the remove function that we must follow.

Program Specifications:

-use a node-based implementation of a tree

-each node in your tree should hold a string (note: a string can hold more than one word) and also contain an integer count (When a duplicate string is entered, it just increases the count +1, not add another node)

Specifications for the function (in BSTree class)

-int height(const string &) const: Compute and return the height of a particular string in the tree. The height of a leaf node is 0 (count the number of edges on the longest path). Return -1 if the string does not exist.

-void remove(const string &): Remove a specified string from the tree. Be sure to maintain all binary search tree properties. If removing a node with a count greater than 1, just decrement the count, otherwise, if the count is simply 1, remove the node. You MUST follow the remove algorithm shown in the slides and discussed in class or else your program will not pass the test functions. When removing, if removing a leaf node, simply remove the leaf. Otherwise, if the node to remove has a left child, replace the node to remove with the largest string value that is smaller than the current string to remove (i.e. find the largest value in the left subtree of the node to remove). If the node has no left child, replace the node to remove with the smallest value larger than the current string to remove (i.e. find the smallest value in the right subtree of the node to remove).

My Nodes are:

struct Node{
string data;
int count;
Node *left;
Node *right;
Node(string data): data(data), left(0), right(0){}
};

Deletion Traverse tree and search for node to remove Five possible situations Item not found Removing a leaf Removing a node with one child right only Removing a node with one child left only Removing a node with two children Binary Search Trees 19 Deletion Removing a node with children Otherwise the node has children find replacement node If the left child exists Replace node information with the largest value smaller than the value to remove find Max(leftChild) Else there is a right child Replace node information with the smallest value larger than value to remove findMin(rightChild)

Explanation / Answer

Please find my implementation.

struct Node{
   string data;
   int count;
   Node *left;
   Node *right;
   Node(string data): data(data), left(0), right(0){}
};

void remove(const string &str){
   root = deleteNode(root, str)
}

// Helper function
Node* deleteNode(Node* root, string key)
{
// base case
if (root == NULL) return root;

// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root->data)
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > root->data)
root->right = deleteNode(root->right, key);

// if key is same as root's key, then This is the node
// to be deleted
else if(root->count > 1){
   root->count = root->count - 1; // decreasing count
}
else
{
// node with only one child or no child
if (root->left == NULL)
{
Node *temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL)
{
Node *temp = root->left;
delete root;
return temp;
}

// node with two children: Get the inorder successor (smallest
// in the right subtree)
Node* temp = minValueNode(root->right);

// Copy the inorder successor's content to this node
root->data = temp->data;

// Delete the inorder successor
root->right = deleteNode(root->right, temp->data);
}
return root;
}

/* Given a non-empty binary search tree, return the node with minimum
key value found in that tree. Note that the entire tree does not
need to be searched. */
Node * minValueNode(Node* node)
{
Node* current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;

return current;
}

/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = height(node->left);
int rDepth = height(node->right);

/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.