0

This is the code that I have for inserting a node, but I don't know how to do the delete function. Any tips would be helpful

// Constructor
Tree::Tree() 
{
     root = NULL;
}

// Destructor
Tree::~Tree() 
{
     freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL )
    {
       freeNode(leaf->Left());
       freeNode(leaf->Right());
       delete leaf;
    }
}

// Add a node
void Tree::addNode(int key) 
{
     // No elements. Add the root
     if ( root == NULL )
     {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
        root = n;
     }
     else 
     {
       cout << "add other node ... " << key << endl;
       addNode(key, root);
     }
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) 
{
    if ( key <= leaf->Key() ) {
       if ( leaf->Left() != NULL )
          addNode(key, leaf->Left());
       else {
          Node* n = new Node();
          n->setKey(key);
          leaf->setLeft(n);
       }
    }
    else {
       if ( leaf->Right() != NULL )
          addNode(key, leaf->Right());
       else {
          Node* n = new Node();
          n->setKey(key);
          leaf->setRight(n);
       }
    }
}

// Print the tree in-order
// Traverse the left sub-tree, root, right sub-tree
void Tree::inOrder(Node* n) {
    if ( n ) {
       inOrder(n->Left());
       cout << n->Key() << " ";
       inOrder(n->Right());
    }
}
1
Contributor
1
Reply
13
Views
2 Years
Discussion Span
Last Post by TheFearful
0

This is what I added, but I don't know how to implement it in my driver file.

//Delete a node
void Node::deleteNode(Node*& tree)
{
    int data;
    Node* tempPtr;
    tempPtr = tree;
    if(tree ->left == NULL)
    {
        tree = tree ->right;
        delete tempPtr;
    }
    else if(tree->right == NULL)
    {
        tree = tree ->left;
        delete tempPtr;
    }
    else
    {
        getPredecessor(tree->left, data);
        tree->key = data;
        Delete(tree ->left, data);
    }
}

void Node::Delete(Node*& tree, int data)
{
    if(data < tree->key)
    {
        Delete(tree ->left, data);
    }
    else if(data > tree->key)
    {
        Delete(tree ->right, data);
    }
    else
    {
        deleteNode(tree);
    }
}

void Node::getPredecessor(Node* tree, int& data)
{
    while(tree ->right != NULL)
    {
        tree = tree ->right;
    }
    data = tree ->key;
}
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.