Binary Tree Heap getNodeIndex hung

[liyingbo]

I am debugging a Binary Tree Heap code. It hung at getNodeIndex() when it is hit the top of the heap, which is called by percolateUp(). Please teach me why this happened and how to fix it? Thank you!

The output is:
after it insert 0, and move 0 to the top, it show inorder, then it prompted:

N1: the node index is 005479E0 The node value is 0
Print Node index after getNodeIndex: 005479E0

Here is the code:

#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <stack>
#include <assert.h>
using namespace std;

bool HIT_HEAP_ROOT = false;

template<class T>
class node {
public:
node(T v= NULL, node<T> *par = NULL, node<T>* left = NULL, node<T>* right = NULL)
: value(v), parent(par), leftChild(left), rightChild(right) { }

// operations
node<T>* copy(node<T> *);
node<T>* getParentIndex(node<T>*, T);
node<T>* getNodeIdex(node<T>*, T);
void percolateUp(node<T>*, int, node<T>*, node<T>*);
void release();
int count(T & testElement);
void insert(node<T> *);
int size();
node<T>* merge(node<T>*, node<T>*);

// data fields
T value;
node<T>* parent;
node<T>* leftChild;
node<T>* rightChild;
};


template<class T> int node<T>::size()
// count number of elements in subtree rooted at node
{
int count = 1;
if (leftChild != NULL)
count += leftChild->size();
if (rightChild != NULL)
count += rightChild->size();
return count;
}


template<class T>
void node<T>::insert(node<T>* newNode)
// insert a new element into a binary search tree
{
//if (newElement < value)
if (newNode->value < value)
if (leftChild != NULL)
leftChild->insert(newNode);
else {
newNode->parent = this;
leftChild = newNode;
}
else
if (rightChild != NULL)
rightChild->insert(newNode);
else {
newNode->parent = this;
rightChild = newNode;
}
}

template <class T>
node<T> * node<T>::merge(node<T> * left, node<T> * right)
// merge two subtrees into one
{
if (left == NULL)
return right;
if (right == NULL)
return left;
node<T> * child = merge(left, right->leftChild);
child->parent = right;
right->leftChild = child;
return right;
}



template<typename T>
void preorder(node<T>* root, string spaces) {
string leadings = spaces + " ";
cout << leadings << root->value << endl;
if (root->leftChild != NULL){
preorder(root->leftChild, leadings);
}
if (root->rightChild != NULL){
preorder(root->rightChild, leadings);
}
}

template<typename T>
void inorder(node<T>* root, string spaces) //inorder: LDR
{

string leadings = spaces + " ";
if (root->leftChild != NULL)
inorder(root->leftChild, leadings); //recursively process left subtree

cout << leadings << root->value << endl; // process date field

if (root->rightChild != NULL)
inorder(root->rightChild, leadings);
}

template<typename T>
void postorder(node<T>* root, string spaces) { //postorder: LRD
string leadings = spaces + " ";
if (root->leftChild != NULL){
postorder(root->leftChild, leadings);
}

if (root->rightChild != NULL){
postorder(root->rightChild, leadings);
}

cout << leadings << root->value << endl;

}

template<typename T>
node<T>* getNodeIndex(node<T>* heap, T svalue)
{

if (heap->value == svalue)
{
cout << "N1: The node index is " << heap << " The node value is: " << heap->value << "reach heap root. " << endl;
HIT_HEAP_ROOT = true;
exit 0;
}
else if ( svalue < heap->value)
{
if (heap->leftChild != NULL)
{
if (heap->leftChild->value == svalue)
{
cout << "N2: The node index is " << heap->leftChild << " The node value is: " << heap->leftChild->value << endl;
return heap->leftChild;
}
else
return getNodeIndex(heap->leftChild, svalue);
}

}
else if (svalue > heap->value)
{
if (heap->rightChild != NULL)
{
if (heap->rightChild->value == svalue)
{
cout << "N3: The node index is " << heap->rightChild->parent << "The node value is: " << heap->rightChild->value << endl;
return heap->rightChild;
}
else
return getNodeIndex(heap->rightChild, svalue);
}

}

}


template<typename T>
node<T>* getParentIndex(node<T>* heap, T svalue)
{

if (svalue == heap->value)
{
cout << "P1: The parent index is " << heap->parent << " parent value is: " << heap->parent->value << "reach heap root. " << endl;
HIT_HEAP_ROOT = true;
exit 0;
}
else if (svalue < heap->value )
{
if (heap->leftChild != NULL)
{
if (heap->leftChild->value == svalue)
{
cout << "P2: The parent index is " << heap->leftChild->parent << " parent value is: " << heap->leftChild->parent->value << endl;
return heap->leftChild->parent;
}
else
return getParentIndex(heap->leftChild, svalue);
}
}
else if (svalue > heap->value)
{
if (heap->rightChild != NULL)
{
if (heap->rightChild->value == svalue)
{
cout << "P3: The parent index is " << heap->rightChild->parent << " parent value is: " << heap->rightChild->parent->value << endl;
return heap->rightChild->parent;
}
else
return getParentIndex(heap->rightChild, svalue);
}

}

}


template<typename T>
void percolateUp(node<T>* heap, int value, node<T>* nodeIndex, node<T>* parentIndex)
{


nodeIndex = getNodeIndex(heap, value);
cout << "Print Node index after getNodeIndex: " << nodeIndex << "\n" << endl;
if (HIT_HEAP_ROOT == true)
{
cout << "search hit the heap root, exit. " << endl;
exit 0;
}
parentIndex = getParentIndex(heap, value);
cout << "Parent index is: " << parentIndex << endl;



if (nodeIndex->value < parentIndex->value)
{
int temp = 0;
temp = nodeIndex->value;
nodeIndex->value = parentIndex->value;
parentIndex->value = temp;
inorder(heap, "");
percolateUp(heap, value, nodeIndex, parentIndex);
}


}







void main() {

int index;
int randNum = 0;
// int numbers[10];
int seed;
// std::stack<int> mystack;

int data[11];
// node<int> nIndex;
node<int>* heap1;
node<int>* nodeIndex = NULL;
node<int>* parentIndex = NULL;

cout << "Please type in an int as random seeds." << endl;
cin >> seed;
srand(seed);

heap1 = new node<int>((int)100);
data[0] = 100;

for (index = 1; index <= 10; index++)
{
data[index] = rand() % 100 + 1;
// insert1(index);
heap1->insert(new node<int>(data[index]));
cout << "insert " << data[index] << "at position " << index << " ";
}

cout << "The heap1 tree inorder is: " << endl;
inorder(heap1, "");
// cout << "The heap1 tree postorder is: " << endl;
// postorder(heap1, "");
cout << "The size of heap1 tree is " << heap1->size() << " nodes. " << endl;

//int dataIndex=5;
//int dataValue = data[dataIndex];
int dataValue = 0;
cout << "\n\n\n" << endl;
cout << "the inserted value is " << dataValue << endl;

heap1->insert(new node<int>(0));
percolateUp(heap1, 0, nodeIndex, parentIndex);


cout << "After perculate, the heap1 inorder is: " << endl;
inorder(heap1, "");

system("pause");
}

[liyingbo]

I found the problem. I should use return 0 instead of exit 0 since the function return type is int. If just use return with a int value then it report syntax error. Fixed.