|
|
 |
|
|
Thread Tools | Display Modes |
Apr 6th, 2006, 4:50 PM
|
#71 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
 |
ok i dont know how much different this code is from the previous post but i noticed some more tendencies when running the program. If the tree is complete that is each parent has 2 children there is no segmentation fault it just does not delete anything. If not all the parents have 2 children then there is a segmentation fault. I have no idea why this is but i have to have this done by midnight so any help would be appreciated
// 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
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;
}
//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->right);
return tempNode->getValue();
}
// find the spot to put new value
void deleteSpot()
{
//heapNode *newRoot = new heapNode(option);
//heapNode *deleteNode = new heapNode(option);
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);
//set value at root
// put call to perculateDown here
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;
} |
|
|
|
Apr 6th, 2006, 5:38 PM
|
#72 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
ok i get a segmentation fault everytime there is more than one level. Like if all the tree is is the root and 2 children then there is not segmentation fault but nothing is deleted. Also after i tell it to delete and see nothing has been deleted if i go to enter another value it does not enter the new value anymore. However, when there is more than one level like maybe 8 values in the tree or something like that i get the segmentation fault whether the tree is complete or not.
// 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
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;
}
/*void 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);
}
} */
//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->left);
return tempNode->getValue();
}
// find the spot to put new value
void deleteSpot()
{
//heapNode *newRoot = new heapNode(option);
//heapNode *deleteNode = new heapNode(option);
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);
//set value at root
// put call to perculateDown here
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;
} |
|
|
|
|
Apr 6th, 2006, 6:10 PM
|
#73 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
ok im just trying to rush this because it has to be done by midnight but besides adding the value i also have to rebalance the tree. I have a method in there that does this commented out so i can still fully focus on the realDelete method. I think the whole program is done now i just need to get it working properly. Here is the whole program.
// 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;
}
/*void 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);
}
} */
//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();
}
//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);
}
} */
// find the the last spot for deletion
void deleteSpot()
{
//heapNode *newRoot = new heapNode(option);
//heapNode *deleteNode = new heapNode(option);
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));
//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;
} |
|
|
|
|
Apr 6th, 2006, 6:40 PM
|
#74 | ||
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
alright i made a couple changes and i think i am really close now to it all working. I think the purculating part works. The only problems now are 1. after i delete once i can not enter another number. 2. it prints a weird number in after the delete. 3. it does not return the deleted value.
here is the code: // 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();
}
//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();
}*/
//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);
}
}
// find the the last spot for deletion
void deleteSpot()
{
//heapNode *newRoot = new heapNode(option);
//heapNode *deleteNode = new heapNode(option);
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));
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;
}Here is an example of the output after inserting a tree and then printing it and then deleting the root once and then reprinting Quote:
Here is the same tree after deleting 2 times Quote:
|
||
|
|
|
|
Apr 6th, 2006, 8:08 PM
|
#75 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
alright one more update. I changed some things to see if it would help doesnt look like it did anything except when i just have one value and delete it it says the value deleted is correct and then it gives a segmentation fault.
// 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();
}
//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();
}*/
//perculate down to reorganize tree
void purculateDown(int ar[], int pos, heapNode *parent)
{
if(ar[pos] == 0)
{
if(parent->getValue() > parent->left->getValue())
{
int tempParentLeft = parent->getLeft()->getValue();
int tempParent = parent->getValue();
parent->setValue(tempParentLeft);
parent->left->setValue(tempParent);
}
else
purculateDown(ar, pos-1, parent->left);
}
else if(ar[pos] == 0)
{
if(parent->getValue() > parent->right->getValue())
{
int tempParentRight = parent->getRight()->getValue();
int tempParent = parent->getValue();
parent->setValue(tempParentRight);
parent->right->setValue(tempParent);
}
else
purculateDown(ar, pos-1, parent->right);
}
}
// find the the last spot for deletion
void deleteSpot()
{
//heapNode *newRoot = new heapNode(option);
//heapNode *deleteNode = new heapNode(option);
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(ar, i, 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;
} |
|
|
|
|
Apr 6th, 2006, 8:37 PM
|
#76 |
|
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;
} |
|
|
|
|
| Bookmarks |
