Write your own class that implements a binary search tree. Use the following UML

Question

Write your own class that implements a binary search tree. Use the following UML diagram and attribute descriptions. Place all the code for the class in a single header file named Troe.h. Be sure to include preprocessor guards remove - a private method that is called by the public remove method. Accepts the root pointer, by reference, and a value to search for and remove from the tree as it's only arguments. find - a public method that calls the private find method, passing t's argument and the root pointer to the private find method. Retums the value returned by the private find method. find - a private method that accepts a root pointer and value to search for in the tree. Rleturms true if it's found, false otherwise. print- a public method that calls the private print method, passing the root pointer to the private print method. print a private method that accepts the root pointer as it's only argument Prints the contents of the tree using in-order traversal rinr: Node"): void clear - a public method that cals the private clear method, passing the root Updates: 3/8/18: Note -clearr: Node'&) : void should be private Submissions update : Plas your entire class ins own header file rared Tree.h. Don't forget your preprocessor gaurds Class Atributes pointer to the private clear method. clear-a private method that accepts the root pointer by reference. Frees al memory used by the tree. Node - a private, nested struct i- an int that stores the value in the tree. left a Node pointer that stores the memory address of the left child right - a Node pointer that stores the memory address of the right child. root- a Node pointer that stores the memory address of the root node. constructor-initializes root to null destructor-frees all memory used by the Tree. Accessors should be marked const The only method that interacts with the user is public print It has a cout statement, but no cin statements. No other method contains cin or cou statemens. You are not writing an entire program, just a class After calling clear, root should be set back to null add - a public method that calls the private add method, passing it the root pointer and it's argument add - a private method that is called by public add. Accepts the root pointer by reference and and integer to add to the tree as it's only arguments remove - a public method that calls the private remove method, passing it the root pointer and it's argument.

Explanation / Answer

// i've tried my level best to achieve ur requirements in cpp . Try to fetch some of ur requirements here in this

// code. I hope u will. Thank u in advance....

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int key;
    struct node *left, *right;
};
struct node* search(struct node* root, int key)
{
    // Base Cases: root is null or key is present at root
    if (root == NULL || root->key == key)
       return root;
  
    // Key is greater than root's key
    if (root->key < key)
       return search(root->right, key);

    // Key is smaller than root's key
    return search(root->left, key);
}
// A utility function to create a new BST node
struct node *newNode(int item)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key);

    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    /* return the (unchanged) node pointer */
    return node;
}
struct node * minValueNode(struct node* node)
{
    struct node* current = node;

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

    return current;
}

/* Given a binary search tree and a key, this function deletes the key
   and returns the new root */
struct node* deleteNode(struct node* root, int 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->key)
        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->key)
        root->right = deleteNode(root->right, key);

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

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

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

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}
// Driver Program to test above functions
int main()
{
    /* Let us create following BST
              50
           /    
          30      70
         /     /
       20   40 60   80 */
    struct node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // print inoder traversal of the BST
    inorder(root);

    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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