|
|
 |
|
|
Thread Tools | Display Modes |
Apr 5th, 2006, 12:18 AM
|
#61 |
|
Expert Programmer
Join Date: Jun 2005
Posts: 884
Rep Power: 4
 |
cout << node->left->getValue();
cout << node->getValue();
cout << node->right->getValue();
printNode(node->getLeft(), level + 1);
printNode(node->getRight(), level + 1);You don't want to print just the left and right value before and after this node's value, you want to print the left and right tree. You just have to move your recursive calls around a bit. Try: printNode(node->getLeft(), level + 1);
for(int i = 0; i < level; i++)
cout << "\t";
cout << node->getValue();
cout << "\n";
printNode(node->getRight(), level + 1); |
|
|
|
Apr 5th, 2006, 2:23 AM
|
#62 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
that works amazingly now time for the delete...
|
|
|
|
|
Apr 5th, 2006, 12:24 PM
|
#63 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
alright here is my first attempt at the delete method. I do not know how to test it because i do not know how to make all those parameters available in main to test it. Does it look right?
Here is just the delete method //delete the root
int realDelete(int ar[], int pos, heapNode *parent, heapNode *deleteNode, heapNode *root)
{
if(ar[pos] == 0)
{
if (parent->getLeft() == NULL)
{
deleteNode->setValue(root->getValue());
root->setValue(parent->getValue());
}
if(root->getValue() < parent->left->getValue())
parent->setValue(parent->left->getValue());
else
realDelete(ar, pos-1, parent->left, deleteNode, root);
}
else if(ar[pos] == 1)
{
if (parent->getRight() == NULL)
{
deleteNode->setValue(root->getValue());
root->setValue(parent->getValue());
}
if(root->getValue() < parent->right->getValue())
parent->setValue(parent->right->getValue());
else
realDelete(ar, pos-1, parent->right, deleteNode, root);
}
return deleteNode->getValue();
}Here is the whole program so far the insert and print work // 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 *deleteNode, heapNode *root)
{
if(ar[pos] == 0)
{
if (parent->getLeft() == NULL)
{
deleteNode->setValue(root->getValue());
root->setValue(parent->getValue());
}
if(root->getValue() < parent->left->getValue())
parent->setValue(parent->left->getValue());
else
realDelete(ar, pos-1, parent->left, deleteNode, root);
}
else if(ar[pos] == 1)
{
if (parent->getRight() == NULL)
{
deleteNode->setValue(root->getValue());
root->setValue(parent->getValue());
}
if(root->getValue() < parent->right->getValue())
parent->setValue(parent->right->getValue());
else
realDelete(ar, pos-1, parent->right, deleteNode, root);
}
return deleteNode->getValue();
}
/*
int delete(rootValue)
{
heapNode *tempNode = new heapNode(value, *left, *right)
go down the heap to the last one
make it root
last nodeValue = null
while(not at the bottom level of tree)
{
if(newRoot < *left)
break;
elseif(newRoot > *left)
swap with left;
}
return tempNode;
}
*/
}; // end of heap class
// menu with add, print, delete choices call methods from heap class
int main()
{
heap *myHeap;
myHeap = new heap();
int option=9;
while (option != 0) {
cout << "Please enter a number: ";
cin >> option;
myHeap->insertSpot(option);
myHeap->print();
}
myHeap->print();
return 0;
} |
|
|
|
|
Apr 5th, 2006, 9:08 PM
|
#64 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
how would i call this method in main?
|
|
|
|
|
Apr 5th, 2006, 9:13 PM
|
#65 |
|
Expert Programmer
Join Date: Jun 2005
Posts: 884
Rep Power: 4
|
I guess you need to find the last element in the heap in a similar way to the way you did for the insert, except you want to find the last spot, rather than the spot to place a new item. I think this is where testing for left == NULL or right == NULL won't work, you need to check the value of pos == 0 instead.
Note that somewhere you are actually going to have to remove that last element, once you have put its value in the root, you can't just leave it in the heap. You will also need to change the counter value. Also note that you don't need to pass in root as a parameter to realinsert, as it is a member variable of the heap class. |
|
|
|
|
Apr 6th, 2006, 2:05 AM
|
#66 | |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
Quote:
// 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;
}
//how to call in main and where to decrement counter?
//delete the root
int realDelete(int ar[], int pos, heapNode *parent, heapNode *deleteNode, heapNode *root)
{
if(ar[pos] == 0)
{
if (parent->getLeft() == NULL)
{
deleteNode->setValue(root->getValue());
root->setValue(parent->getValue());
}
if(root->getValue() < parent->left->getValue())
parent->setValue(parent->left->getValue());
else
realDelete(ar, pos-1, parent->left, deleteNode, root);
}
else if(ar[pos] == 1)
{
if (parent->getRight() == NULL)
{
deleteNode->setValue(root->getValue());
root->setValue(parent->getValue());
}
if(root->getValue() < parent->right->getValue())
parent->setValue(parent->right->getValue());
else
realDelete(ar, pos-1, parent->right, deleteNode, root);
}
return deleteNode->getValue();
}
/*
int delete(rootValue)
{
heapNode *tempNode = new heapNode(value, *left, *right)
go down the heap to the last one
make it root
last nodeValue = null
while(not at the bottom level of tree)
{
if(newRoot < *left)
break;
elseif(newRoot > *left)
swap with left;
}
return tempNode;
}
*/
}; // 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();
}
return 0;
} |
|
|
|
|
|
Apr 6th, 2006, 3:54 AM
|
#67 | |
|
Expert Programmer
Join Date: Jun 2005
Posts: 884
Rep Power: 4
|
Quote:
|
|
|
|
|
|
Apr 6th, 2006, 11:57 AM
|
#68 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
alright this is what i got I did a couple tests and do not really know what its doing
// 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;
}
//how to call in main and where to decrement counter?
//delete the root
int realDelete(int ar[], int pos, heapNode *parent, heapNode *deleteNode)
{
if(ar[pos] == 0)
{
if (parent->getLeft() == NULL)
{
deleteNode->setValue(root->getValue());
root->setValue(parent->getValue());
}
if(root->getValue() < parent->left->getValue())
parent->setValue(parent->left->getValue());
else
realDelete(ar, pos-1, parent->left, deleteNode);
}
else if(ar[pos] == 1)
{
if (parent->getRight() == NULL)
{
deleteNode->setValue(root->getValue());
root->setValue(parent->getValue());
}
if(root->getValue() < parent->right->getValue())
parent->setValue(parent->right->getValue());
else
realDelete(ar, pos-1, parent->right, deleteNode);
}
return deleteNode->getValue();
}
// find the spot to put new value
void deleteSpot(int option)
{
heapNode *newRoot = new heapNode(option);
heapNode *deleteNode = new heapNode(option);
counter--;
if(deleteNode->left == NULL)
{
root = newRoot;
}
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, deleteNode);
}
}
/*
int delete(rootValue)
{
heapNode *tempNode = new heapNode(value, *left, *right)
go down the heap to the last one
make it root
last nodeValue = null
while(not at the bottom level of tree)
{
if(newRoot < *left)
break;
elseif(newRoot > *left)
swap with left;
}
return tempNode;
}
*/
}; // 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(value);
}
return 0;
} |
|
|
|
|
Apr 6th, 2006, 3:56 PM
|
#69 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
ok i tried to do what you said and it compiles fine but it does not appear the delete actually does anything.
// 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)
{
root->setValue(parent->getValue());
tempNode = parent;
parent = NULL;
}
else if(ar[pos] == 1)
{
root->setValue(parent->getValue());
tempNode = parent;
parent = NULL;
}
}
else
realDelete(ar, pos-1, parent->right);
return tempNode->getValue();
}
// find the spot to put new value
void deleteSpot(int option)
{
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);
// replace value at root
// put call to perculateDown here
counter--;
}
}
/*
int delete(rootValue)
{
heapNode *tempNode = new heapNode(value, *left, *right)
go down the heap to the last one
make it root
last nodeValue = null
while(not at the bottom level of tree)
{
if(newRoot < *left)
break;
elseif(newRoot > *left)
swap with left;
}
return tempNode;
}
*/
}; // 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(value);
}
return 0;
} |
|
|
|
|
Apr 6th, 2006, 4:00 PM
|
#70 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 346
Rep Power: 4
|
ok i made one more quick change i got rid of the option stuff. The delete works fine if the tree is empty or only a root. However, more than that i get 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
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)
{
root->setValue(parent->getValue());
tempNode = parent;
parent = NULL;
}
else if(ar[pos] == 1)
{
root->setValue(parent->getValue());
tempNode = parent;
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);
// replace value at root
// put call to perculateDown here
counter--;
}
}
/*
int delete(rootValue)
{
heapNode *tempNode = new heapNode(value, *left, *right)
go down the heap to the last one
make it root
last nodeValue = null
while(not at the bottom level of tree)
{
if(newRoot < *left)
break;
elseif(newRoot > *left)
swap with left;
}
return tempNode;
}
*/
}; // 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 |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | |
| Display Modes | |
|
|
Linear Mode
