All in all my program works how I want it to except that when it's done running, I have some active allocations that I want to get rid of. I was introduced to pointers a couple of months ago and my Chop function is my feeble attempt to deallocate (i don't know if that's even the right term). What needs to be deallocated and what's a good way to go about doing it? Thanks for the help.
with the test data:
1
a
1
a
print
I end up with two active allocations
Code:
#include <iostream>
#include<string>
#include<sstream>
using namespace std;
template <class T>
struct NodeType{
T info;
NodeType * left;
NodeType * right;
};
template<class T>
struct Tree{
NodeType<T> * root;
};
template<class T>
T GetSuccessor(NodeType<T> *& successor){
successor = successor->right;
while(successor->left!=NULL)
successor = successor->left;
return successor->info;
}
template<class T>
NodeType<T> * Retrieve(Tree<T> myTree, T item){
NodeType<T> * node = myTree.root;
while(item != node->info){
if(item < node->info)
node = node->left;
else
node = node->right;
}
return node;
}
template<class T>
void Insert(NodeType<T> *& node, T item){
if(node == NULL){
node = new NodeType<T>;
node->left = NULL;
node->right = NULL;
node->info = item;
}
else if(item < node->info)
Insert(node->left, item);
else
Insert(node->right, item);
}
template<class T>
void Delete(Tree<T> & myTree, T item){
NodeType<T> * node = myTree.root;
NodeType<T> * parent = myTree.root;
while(item!=node->info){
parent = node;
if(item < node->info){
node = node->left;
}
else{
node = node->right;
}
}//node = the node to be deleted
bool isleft = (parent->left==node); //true if the node to be deleted is a left child
//if the node is a leaf
if(node->right==NULL && node->left==NULL){
if(myTree.root->info == item)
myTree.root = NULL;
else if(isleft)
parent->left = NULL;
else
parent->right = NULL;
}
//else the node has two children
else if(node->right!=NULL && node->left!=NULL){
//cout << "Deleting node->info: " << node->info << endl;
T data = GetSuccessor(node); //get the successor
node = Retrieve(myTree, item);
Delete(myTree, data);
node->info = data;
}
//if the node's only child is left
else if(node->left!=NULL){
if(node == myTree.root) //if the node to be deleted is the root
myTree.root = node->left; //the root is now it's left (and only) child
else if(isleft) //check if the node to be deleted is a left child
parent->left = node->left; //if so replace the parent's left child with the node's left child
else //else the node is a right child
parent->right = node->left; //so replace the parent's right child with the node's left child
}
//if the node's only child is right
else if(node->right!=NULL){
if(node == myTree.root) //if the node to be deleted is the root
myTree.root = node->right; //the root is now it's right (and only) child
else if(isleft) //check if the node to be deleted is a left child
parent->left = node->right; //if so replace the node's parent's left child with the node's right child
else //else the node is a right child
parent->right = node->right; //so replace the node's parent's right child with the node's right child
}
}
template <class T>
void Chop(NodeType<T> * n){
if(n!=NULL){
if(n->left!=NULL)
Chop(n->left);
if(n->right!=NULL)
Chop(n->right);
}
delete n;
}
template<class T>
void PrintChildren(NodeType<T> *& n){
cout << " [";
if(n->left!=NULL && n->right!=NULL) cout << "left, right";
else if(n->left!=NULL) cout << "left";
else if(n->right!=NULL) cout << "right";
cout << "]" << endl;
}
template <class T>
void InOrder(NodeType<T> *& n){
if(n == NULL)
cout << " empty tree.";
else{
if(n->left != NULL)
InOrder<T>(n->left);
cout << " " << n->info;
//PrintChildren<T>(n);
if(n->right != NULL)
InOrder<T>(n->right);
}
}
template <class T>
void PreOrder(NodeType<T> *& n){
if(n == NULL)
cout << " empty tree.";
else{
cout << " " << n->info;
//PrintChildren<T>(n);
if(n->left != NULL)
PreOrder<T>(n->left);
if(n->right != NULL)
PreOrder<T>(n->right);
}
}
template <class T>
void PostOrder(NodeType<T> *& n){
if(n == NULL)
cout << "empty tree.";
else{
if(n->left != NULL)
PostOrder<T>(n->left);
if(n->right != NULL)
PostOrder<T>(n->right);
cout << " " << n->info;
//PrintChildren<T>(n);
}
}
template <class T>
void PrintDot(NodeType<T> *& n){
if(n == NULL)
cout << "empty tree.";
else{
if(n->left!=NULL){
cout << n->info << "->" << n->left->info << " [label=L];\n";
PrintDot(n->left);
}
if(n->right!=NULL){
cout << n->info << "->" << n->right->info << " [label=R];\n";
PrintDot(n->right);
}
}
}
int main(){
Tree<string> myTree;
int n;
string key;
string str;
string item;
myTree.root = NULL;
//inserts
cin >> n;
for(int i=0;i<n;i++){
cin >> item;
Insert<string>(myTree.root, item);
}
//deletes
cin >> n;
for(int i=0;i<n;i++){
cin >> key;
Delete<string>(myTree, key);
}
//print
cin >> str;
if(str == "print"){
cout << "InOrder:";
InOrder<string>(myTree.root);
}
else if(str == "printpre"){
cout << "PreOrder:";
PreOrder<string>(myTree.root);
}
else if(str == "printpost"){
cout << "PostOrder:";
PostOrder<string>(myTree.root);
}
else if(str == "dot"){
cout << "digraph \"Binary Search Tree\" {\n";
PrintDot<string>(myTree.root);
cout << "}" << endl;
}
//empty tree
Chop(myTree.root);
}
Also, is it possible to configure my mingw compiler to tell me how many active allocations there are after running a program such as this?
need help deallocating
Originally Posted by kocaloka
