C++ Binary Search Tree Destructor/remove Methods howto?

[Chez 0]

I have a binary search tree and I need to put a destructor on it. Ideally it would be called when I exit the program. How would a destructor look if it should delete all the nodes of a tree (recursively prefered).

 

Also, how would I go about removing a node from my tree and then replacing it so the tree is still ordered inorder-wise?

 

replacing specs:

* If the node x is a leaf, then it can simply be clipped off.

* If x has a single child then it can be replaced by its child.

* Otherwise, if x has two children, find the leftmost child in x's right subtree. This node, which is x's in-order successor, will have either zero or one children and can be removed using the previous two cases. Then this node can be used to "replace" x in the tree, so that xcan safely be deleted.

 

Here's what i have so far:

//******************************************************************

// Main.C

//******************************************************************

#include "Tree.h"

#include <iostream>

using namespace std;

 

// ----Main Class----

//

// Calls the appropriate method based on user input.

// a = add

// r = remove

// s = size

// c = contains

// p = print

// q = quit

//

 

int main ( )

{

BSTree mytree; // creates new tree

 

// Creates a buffer array for the input line to be stored on

char buffer[200];

while ( !cin.eof() )

{

 

cin.getline ( buffer, 200 );

 

// Scans the input line for a certain character predefined

// in the assignment. Input is set as the location of the

// found character + 2 to increment position to the parameter

// variable. Subtracting '0' gives the value of the character.

for (int i = 0 ; buffer != '\0' ; i++ )

{

//------ADD------

if ( buffer == 'a' )

{

int * input = new int;

int k;

for (k = i ; buffer[k+2] != '\0' ; k++)

*input = (*input*10) + (buffer[k+2] - '0');

 

if(mytree.add( input ))

cout << *input << " successfully added to tree" << endl;

i = k+1;

}

 

//------REMOVE------

else if ( buffer == 'r' )

{

int * input = new int;

for (int k = i ; buffer[k+2] != '\0' ; k++)

*input = (*input*10) + (buffer[k+2] - '0');

 

if (mytree.contains ( *input ) == 1)

{

mytree.remove( *input );

}

else

cout << *input << " is not located in the tree" << endl;

}

 

//------CONTAINS------(done)

else if ( buffer == 'c' )

{

int * input = new int;

for (int k = i ; buffer[k+2] != '\0' ; k++)

*input = (*input*10) + (buffer[k+2] - '0');

 

if (mytree.contains( *input ) == 1)

cout << *input << " is in the tree" << endl;

else

cout << *input << " is not in the tree" << endl;

}

 

//------SIZE------

else if ( buffer == 's' )

{

cout << "The tree contains " << mytree.size() << " elements" << endl;

}

 

//------PRINT------

else if ( buffer == 'p' )

{

mytree.print( );

cout << "Tree done." << endl;

}

 

//------QUIT------

else if ( buffer == 'q' )

{

~BSTree() { delete [] mytree; }

return 0;

}

}

}

}

 

//******************************************************************

// Node.h

//

//

//******************************************************************

 

#ifndef NODE_H

#define NODE_H

 

#include "Tree.h"

#include <iostream>

using namespace std;

 

//******************************************************************

// class NODE

//

// The layout of each node. Stores a left and right child pointer

// as well as the data of the current node.

//******************************************************************

class NODE

{

public:

NODE* left;

NODE* right;

int *data;

} ;

 

#endif

 

//******************************************************************

// Tree.C

//

//

//******************************************************************

 

#include "Tree.h"

#include <iostream>

using namespace std;

 

//******************************************************************

// BSTree()

// Creates a new tree

//

// Initially null

//******************************************************************

BSTree::BSTree()

{

root = 0;

}

 

 

//******************************************************************

// ~BSTree()

// Destroys the tree

//

// Seals any memory leaks upon exit

//******************************************************************

BSTree::~BSTree()

{

delete root;

}

 

 

//******************************************************************

// add(int)

// Adds a new node to the tree

// int <data> - the value being inserted

// Return - true or false, depending on if the node was inserted

// Calls a recursive method to do tree traversals

//******************************************************************

bool BSTree::add ( int * data )

{

if (root == 0)

{

NODE* newnode = new NODE;

newnode->data = data;

newnode->left = 0;

newnode->right = 0;

root = newnode;

return 1;

}

else

return (findNode(root, data) != NULL );

}

 

 

//******************************************************************

// findNode(NODE*, int)

// Recursive method called by add(int) to traverse the tree, searching

// for the correct location to add a node.

// NODE* <root> - the root pointer, int <data> - the value to be added

// Return - node pointer to be evaluated by add(int)

//******************************************************************

NODE* BSTree::findNode(NODE *root, int *data)

{

if (root == 0)

{

NODE* newnode = new NODE;

newnode->data = data;

newnode->left = 0;

newnode->right = 0;

root = newnode;

return root;

}

else if (*data < *(root->data))

root->left = this->findNode(root->left, data);

else if (*data > *(root->data))

root->right = this->findNode(root->right, data);

else // data already in tree

{

cout << *data << " is already in the tree" << endl;

return 0;

}

return root;

}

 

 

//******************************************************************

// print()

// Prints the tree on its side, with correct indentation.

//

//

// Calls a recursive method to print the tree during traversal

//******************************************************************

void BSTree::print( )

{

printTree( root, 1 );

}

 

 

//******************************************************************

// printTree(NODE*, int)

// Recursive method called by print() to traverse the tree and print

// the node values with correct indentation.

// NODE* <root> - the root pointer, int <level> - the current level

//******************************************************************

void BSTree::printTree( NODE *root, int level )

{

if ( root != 0 )

{

printTree(root->right, level+1);

for(int i=0 ; i<3*level ; i++)

cout << " ";

cout << *(root->data) << endl;

printTree(root->left, level+1);

}

}

 

 

//******************************************************************

// contains(int)

// Evaluates whether or not a given value is present in the tree

// int <target> - the value to be compared with each node in the tree

// Return - True if the value is found in the tree, false otherwise

// Calls a recursive method to do tree traversals and comparisons

//******************************************************************

bool BSTree::contains ( int target)

{

return hasValue(root, target);

}

 

 

//******************************************************************

// hasValue(NODE*, int)

// Recursive method called by contains(int) to traverse the tree and

// compare each apprpriate node with the given target value.

// NODE* <root> - the root pointer, int <target> - the target value

// Return - True is the value is found, false otherwise

//******************************************************************

bool BSTree::hasValue ( NODE *root, int target )

{

if ( root == 0 ) return 0;

else

{

if ( target == *(root->data)) return 1;

else

{

if ( target < *(root->data) )

return ( this->hasValue ( root->left, target ) );

else

return ( this->hasValue ( root->right, target ) );

}

}

}

 

 

//******************************************************************

// size()

// Method that returns the numbers of elements in the tree

//

// Return - number of elements in the tree

// Calls a recursive method to traverse the tree and count each node

//******************************************************************

int BSTree::size ( )

{

return hasSize( root);

}

 

 

//******************************************************************

// hasSize(NODE*)

// Recursive function called by size() to traverse the tree and count each

// node.

// NODE* < root> - the root pointer

// Return - number of elements in the tree

//******************************************************************

int BSTree::hasSize(NODE* root)

{

if (root==0)

return(0);

else

return(this->hasSize(root->left) + 1 + this->hasSize(root->right));

}

 

 

//******************************************************************

// Remove(int)

// Removes a value-specific node from the tree and organizes the result

// to maintain an ordered inorder print (ascending).

// int <target> - the value to be removed

// Return - the node pointer

// Calls two recursive methods. One to do the actual deleting, and the

// other to find the target node.

//******************************************************************

int* BSTree::remove( int target )

{

NODE* location = findIt(root, target);

DeleteNode( location );

}

 

 

//******************************************************************

// DeleteNode(NODE*)

// Recursive method called by the remove(int) method to delete the

// given node and organize the tree

// NODE* <root> - the root pointer

//

//******************************************************************

void BSTree::DeleteNode(NODE* root) {

NODE* temp = root;

if (root->left == NULL && root->right == NULL)

{

delete temp;

}

else if (root->left != NULL && root->right == NULL)

{

root = root->left;

delete temp;

}

else if (root->left == NULL && root->right != NULL)

{

root = root->right;

delete temp;

}

else {

temp = root->left;

while (temp->right != NULL)

temp = temp->right;

 

root->data = temp->data;

DeleteNode(temp);

}

}

 

 

//******************************************************************

// findIt(NODE*, int)

// Recursive method called by the remove(int) method to seek out and

// return the location of the target node.

// NODE* <root> - the root pointer, int <target> - the value to seek out

// Return - the node location

//******************************************************************

NODE* BSTree::findIt(NODE *root, int target)

{

if (root == 0)

{

cout << "** ERROR: NOT FOUND **" << endl;

return 0;

}

else if (target < *(root->data))

root->left = this->findIt(root->left, target);

else if (target > *(root->data))

root->right = this->findIt(root->right, target);

else // 'target data' = 'root data'

return root;

 

return root;

 

}

/*

~BSTree()

{

if(root->left)

delete root->left[0];

if(Childs[1])

delete Childs[1];

}

// ...

delete Tree.Root;

}

 

void BSTree::clear()

{

deleteAll(root);

}

void BSTree::deleteAll(NODE* root)

{

delete BSTree();

 

}*/

 

//******************************************************************

// Tree.h

//

//******************************************************************

 

#ifndef TREE_H

#define TREE_H

 

#include "Node.h"

#include <iostream>

using namespace std;

 

//******************************************************************

// class BSTree

//

// Defines the methods to be used by the program.

// add - adds a new node to the tree in the correct locale

// contains - is the given value in the tree?

// print - prints the tree on its side

// size - returns the number of elements in the tree

// remove - removes a node and sorts it again

//******************************************************************

class BSTree

{

 

public:

BSTree();

~BSTree();

void clear ( );

bool add ( int * data );

NODE* findNode ( NODE *root, int * data);

bool contains ( int target );

void print ( );

int size ( );

int *remove(int k);

 

 

private:

NODE* root;

 

void deleteAll( NODE *root );

bool hasValue ( NODE *root, int target );

void printTree ( NODE *root, int level );

int hasSize ( NODE *root );

NODE* findIt ( NODE *root, int target );

void DeleteNode(NODE* root);

};

 

#endif