I have tried to write the destructor function to get the memory allocated for each node in the BST , then each node should be freed. It's called void BST::destructTree(Node * root) in bst.cpp. Also, I...

1 answer below »

I have tried to write the destructor function to get the memory allocated for each node in the BST , then each node should be freed. It's called void BST::destructTree(Node * root) in bst.cpp. Also, I have tried to write functions to check whether it's a tree or not, but none of them seem to work out.

bst-jztf21uh.zip 2020-10-05-2-yu4cc2yn.png

Answered Same DayOct 06, 2021

Answer To: I have tried to write the destructor function to get the memory allocated for each node in the BST ,...

Riya answered on Oct 06 2021

152 Votes

bst/bst.cpp
#include
#include "bst.h"
using namespace std;
template
BST::BST() : root(NULL)
{
}
template
BST::~BST()
{
    destructTree(root);// This would be a good place to delete the nodes in the tree
}
// Inserts a new node at the front of the list
template
void BST::insert(T item)
{
    // First search for the insertion point
    Node* y = NULL;
    Node* x = root;
    while (x != NULL)
    {
        y = x; // Remember previous node
        // Update x to a child pointer
        if (item < x->getItem())
            x = x->getLeft();
        else
            x = x->getRight();
    }
    // At this point, y points to the node where we should
    // insert the new node.
    // Create a new node with the insertion value
    Node* newNode = new Node(item);
    newNode->setParent(y); // Set parent to Y
    if (y == NULL)
    {
        root = newNode; // First node
    }
    else
    {
        // Set new node as left or right child of y
        if (item < y->getItem())
            y->setLeft(newNode);
        else
            y->setRight(newNode);
    }
}
template
Node* BST::find(T item)
{
    if (root == NULL)
        return NULL;
    return treeSearch(root, item);
}
template
void BST::onchange(Node* p,int data)
{
    p->setitem(data);
}
template
Node* BST::treeSearch(Node* p, T item)
{
    if (p == NULL)
        return NULL;
    if (p->getItem() == item)
        return p;
    if (item < p->getItem())
        return treeSearch(p->getLeft(), item);
    else
        return treeSearch(p->getRight(), item);
}
template
void BST::traverse()
{
    inOrder(root);
}
template
void BST::inOrder(Node* p)
{
    if (p != NULL)
    {
        inOrder(p->getLeft());
        cout << p->getItem() << endl;
        inOrder(p->getRight());
    }
}
template
Node* BST::successor(Node* p)
{
    if (p->getRight() != NULL)
    {
        p = p->getRight();
        while (p->getLeft() != NULL)
        {
            p = p->getLeft();
        }
        return p;
    }
    else
    {
        Node* parent = p->getParent();
        while ((parent != NULL) && (p == parent->getRight()))
        {
            p = parent;
            parent = parent->getParent();
        }
        return parent;
    }
}
template
void BST::deleteNode(Node* z)
{
    if (z->getLeft() == NULL)
        transplant(z, z->getRight());
    else if (z->getRight() == NULL)
        transplant(z,...

SOLUTION.PDF

I have tried to write the destructor function to get the memory allocated for each node in the BST , then each node should be freed. It's called void BST::destructTree(Node * root) in bst.cpp. Also, I...

Answer To: I have tried to write the destructor function to get the memory allocated for each node in the BST ,...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment