|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4 
|
alright i dont even know what im doing anymore i tried some stuff and i think it made it worse. I do not even know what works and what doesnt anymore it seems like i just keep running into new problems. This time even on the first recursion it did not put the least value as the new root. I dont know heres what i have if someone knows how to do something with it to get it to work it would be appreciated. I think what it is doing is just replacing the number in the left child with the really big number it makes the new root which is also the same number that it prints for the number its deleting.
//Carl Layton
//cs351
// add, print and delete a number from a binary min heap
#include <iostream>
using namespace std;
// node containing int value and left and right pointers
// constructor, get value, get right, get left, set value, set left, set right
class heapNode
{
private:
int value;
public:
heapNode *left;
heapNode *right;
//constructor
heapNode(int newValue)
{
value = newValue;
left = NULL;
right = NULL;
}
//get value
int getValue()
{
return value;
}
//get right
heapNode* getRight()
{
return right;
}
//get left
heapNode* getLeft()
{
return left;
}
//set value
void setValue(int newValue)
{
value = newValue;
}
// set right
void setRight(heapNode *newRight)
{
right = newRight;
}
// set left
void setLeft(heapNode *newLeft)
{
left = newLeft;
}
}; // end of heapNode class
//insert print and delete methods for the min heap
class heap
{
private:
heapNode *root;
int counter;
public:
//constructor
heap()
{
counter = 0;
root = NULL;
}
//insert new value, check to see if swap is needed
void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
{
if(ar[pos] == 0)
{
if (parent->getLeft() == NULL)
parent->setLeft(newNode);
else
realInsert(ar, pos-1, parent->left, newNode);
if(parent->getLeft()->getValue() < parent->getValue())
{
int tempParentLeft = parent->getLeft()->getValue();
int tempParent = parent->getValue();
parent->setValue(tempParentLeft);
parent->left->setValue(tempParent);
}
}
else if(ar[pos] == 1)
{
if (parent->getRight() == NULL)
parent->setRight(newNode);
else
realInsert(ar, pos-1, parent->right, newNode);
if(parent->getRight()->getValue() < parent->getValue())
{
int tempParentRight = parent->getRight()->getValue();
int tempParent = parent->getValue();
parent->setValue(tempParentRight);
parent->right->setValue(tempParent);
}
}
}
// find the spot to put new value
void insertSpot(int option)
{
heapNode *newNode = new heapNode(option);
counter++;
if(root == NULL)
{
root = newNode;
}
else
{
int arrayValue;
bool isOne = false;
int ar[32];
int i;
int temp = counter;
for(i = 0; i < 32; i++)
{
arrayValue = temp % 2;
temp = temp / 2;
ar[i] = arrayValue;
}
for(i = 0; i < 32; i++)
cout << ar[i] << " ";
cout << endl;
i=31;
while(i >= 0)
{
if(ar[i] == 1)
isOne = true;
if(isOne == true)
break;
i--;
}
i--;
cout << "Broke loop with i = " << i << endl;
realInsert(ar, i, root, newNode);
}
}
//call printNode
void print()
{
cout << "Printing the heap...\n";
printNode(root, 0);
}
//print tree with spaces for levels of the tree
void printNode(heapNode *node, int level)
{
if(node != NULL)
{
printNode(node->getLeft(), level + 1);
for(int i = 0; i < level; i++)
cout << "\t";
cout << node->getValue();
cout << "\n";
printNode(node->getRight(), level + 1);
}
}
// get root
heapNode* getRoot()
{
return root;
}
int realDelete(int ar[], int pos, heapNode *parent)
{
heapNode *tempNode;
if(parent->getLeft() == NULL)
{
if (ar[pos] == 0)
{
tempNode = parent;
parent = NULL;
}
else
realDelete(ar, pos-1, parent->left);
}
else if(parent->getRight() == NULL)
{
if (ar[pos] == 1)
{
tempNode = parent;
parent = NULL;
}
else
realDelete(ar, pos-1, parent->right);
}
return tempNode->getValue();
}
//perculate down to reorganize tree
void purculateDown(heapNode *parent)
{
if(parent->getValue() > parent->left->getValue())
{
int tempParentLeft = parent->getLeft()->getValue();
int tempParent = parent->getValue();
parent->setValue(tempParentLeft);
parent->left->setValue(tempParent);
}
else if(parent->getValue() > parent->right->getValue())
{
int tempParentRight = parent->getRight()->getValue();
int tempParent = parent->getValue();
parent->setValue(tempParentRight);
parent->right->setValue(tempParent);
}
}
//delete the root
/*int realDelete(int ar[], int pos, heapNode *parent)
{
heapNode *tempNode = NULL;
if(pos == 0)
{
if (ar[pos] == 0)
{
tempNode = root;
parent = NULL;
}
else if(ar[pos] == 1)
{
tempNode = root;
parent = NULL;
}
}
else
realDelete(ar, pos-1, parent);
return tempNode->getValue();
}*/
// find the the last spot for deletion
void deleteSpot()
{
if (root == NULL)
cout << "Error. The tree is empty.\n";
else if(counter == 1)
{
root = NULL;
}
else
{
int arrayValue;
bool isOne = false;
int ar[32];
int i;
int temp = counter;
for(i = 0; i < 32; i++)
{
arrayValue = temp % 2;
temp = temp / 2;
ar[i] = arrayValue;
}
for(i = 0; i < 32; i++)
cout << ar[i] << " ";
cout << endl;
i=31;
while(i >= 0)
{
if(ar[i] == 1)
isOne = true;
if(isOne == true)
break;
i--;
}
i--;
cout << "Broke loop with i = " << i << endl;
realDelete(ar, i, root);
root->setValue(realDelete(ar, i, root));
cout << "Deleted Value = " << root->getValue() << endl;
purculateDown(root);
counter--;
}
}
}; // end of heap class
// menu with add, print, delete choices call methods from heap class
int main()
{
int option;
int value;
heap *myHeap;
myHeap = new heap();
while(option != 4)
{
cout << "1. Add a value. \n"
<< "2. Print the heap. \n"
<< "3. Delete the root. \n"
<< "4. Quit. \n"
<< "Please make a selection: ";
cin >> option;
if(option == 1)
{
cout << "Please enter a value: ";
cin >> value;
myHeap->insertSpot(value);
}
if(option == 2)
myHeap->print();
if(option == 3)
myHeap->deleteSpot();
}
return 0;
} |