Chez 0 Report post Posted June 7, 2006 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 Share this post Link to post Share on other sites
bakuryu 0 Report post Posted July 4, 2006 Ok so the destructor is ~BSTree. I have written another function void delLeafNodes(Node*); void delLeafNodes(Node* n){ if (n->left) delLeafNodes (n->left); if (n->right) delLeafNodes (n->right); // control comes here only when node n has no childs. So delete node n delete n; n = NULL; // not required but I prefer }BSTree::~BSTree(){ delLeafNodes(root); // root = NULL will already be set by the delLeafNodes function. So no need to specify it again} Share this post Link to post Share on other sites
