Kibbe
asked on
Level Order traversal of left child right sibling implementation.
I have a data structure (a min pairing heap) that I need to print in level order. The ADT is implemented using the leftmost child right list of siblings implementation (a node has a pointer to it's leftmost child and to it's sibling) which I need to print out in level order, so if the data structure happened to look like
1
2 4
5 7 6 8
it would print 1245768. Note: I'm using C++. Can someone help me with this implementation?
1
2 4
5 7 6 8
it would print 1245768. Note: I'm using C++. Can someone help me with this implementation?
ASKER
Ah i figured it out myself, I had written
void PairingHeap::levelorder(Pa iringNode *treePtr,
FunctionType visit)
{
queue<PairingNode*> levelorderQueue; //make temp queue for level order traversal
PairingNode *temp = root; //make a copy of the root
if (temp != NULL)
{
levelorderQueue.push(temp) ; //enqueue the root
while (!levelorderQueue.empty())
{
/*cout<<"in while loop"<<endl;*/
temp = levelorderQueue.front(); //temp becomes first item in queue
levelorderQueue.pop(); //pop first item in queue
visit(temp->item);//this basically means cout temp (visit is a function designed to output)
cout<<' '; //spacers
if (temp->leftChildPtr != NULL)
levelorderQueue.push(temp- >leftChild Ptr);
while (temp->rightSiblingPtr != NULL)
{
levelorderQueue.push(temp- >rightSibl ingPtr);
temp = temp->rightSiblingPtr;
}
}
}
}//end level order traversal
the while(temp->rightSiblingPt r != NULL) needed to be if instead of while
at least i THINK this works
Is that enough of a start for you to tell me if I have it right? I know without the whole header/cpp you might not understand, but it should be relatively clear there
void PairingHeap::levelorder(Pa
FunctionType visit)
{
queue<PairingNode*> levelorderQueue; //make temp queue for level order traversal
PairingNode *temp = root; //make a copy of the root
if (temp != NULL)
{
levelorderQueue.push(temp)
while (!levelorderQueue.empty())
{
/*cout<<"in while loop"<<endl;*/
temp = levelorderQueue.front(); //temp becomes first item in queue
levelorderQueue.pop(); //pop first item in queue
visit(temp->item);//this basically means cout temp (visit is a function designed to output)
cout<<' '; //spacers
if (temp->leftChildPtr != NULL)
levelorderQueue.push(temp-
while (temp->rightSiblingPtr != NULL)
{
levelorderQueue.push(temp-
temp = temp->rightSiblingPtr;
}
}
}
}//end level order traversal
the while(temp->rightSiblingPt
at least i THINK this works
Is that enough of a start for you to tell me if I have it right? I know without the whole header/cpp you might not understand, but it should be relatively clear there
Well, it looks ok to me at first glance. I think your fix is appropriate. Does it output as you expect? That is the important thing.
ASKER
I believe so! Now if you don't mind helping with a followup question, i keep getting a segfault when I try to delete min, I have tried writing two functions to delete min (my merge function clearly works since it was able to build the data structure from an input set)
here are my two deletion functions if you don't mind looking:
void PairingHeap::deleteMinimum ()
{
PairingNode* temp = root;
if (root->leftChildPtr == NULL)
root = NULL;
root = joinSiblings(root->leftChi ldPtr);
delete temp;//maybe take this out?
temp = NULL;//-------------------
}
PairingNode* PairingHeap::joinSiblings( PairingNod e* first)
{
if (first->rightSiblingPtr == NULL)
return first;
//create vector to hold all the siblings
vector <PairingNode*> heapVector;
while (first->rightSiblingPtr != NULL) //toss all the heaps into the queue/array/vector/call it what you like :)
{
heapVector.push_back(first ); //enqueue
PairingNode* temp = first; //break the bonds between siblings
first->rightSiblingPtr = NULL; //broken
first = temp->rightSiblingPtr; //repeat for next sibling
}
//merge the remaining trees
first = heapVector.at(0);
heapVector.erase(heapVecto r.begin()) ;
while (!heapVector.empty())
{
first = merge(first, heapVector.at(0)); //first element
heapVector.erase(heapVecto r.begin()) ;
}
return first;
}
here are my two deletion functions if you don't mind looking:
void PairingHeap::deleteMinimum
{
PairingNode* temp = root;
if (root->leftChildPtr == NULL)
root = NULL;
root = joinSiblings(root->leftChi
delete temp;//maybe take this out?
temp = NULL;//-------------------
}
PairingNode* PairingHeap::joinSiblings(
{
if (first->rightSiblingPtr == NULL)
return first;
//create vector to hold all the siblings
vector <PairingNode*> heapVector;
while (first->rightSiblingPtr != NULL) //toss all the heaps into the queue/array/vector/call it what you like :)
{
heapVector.push_back(first
PairingNode* temp = first; //break the bonds between siblings
first->rightSiblingPtr = NULL; //broken
first = temp->rightSiblingPtr; //repeat for next sibling
}
//merge the remaining trees
first = heapVector.at(0);
heapVector.erase(heapVecto
while (!heapVector.empty())
{
first = merge(first, heapVector.at(0)); //first element
heapVector.erase(heapVecto
}
return first;
}
ASKER
also i've narrowed down that the seg fault is occuring in the while loop of joinSiblings
if (root->leftChildPtr == NULL)
root = NULL;
root = joinSiblings(root->leftChi ldPtr); // what happens here if root is null? NULL pointer access at root->
Always check p if you are going to use p->
root = NULL;
root = joinSiblings(root->leftChi
Always check p if you are going to use p->
ASKER
that's a good point, except that I check for root = null before calling that function. but it's true, i would be accessing null otherwise. It appears that it's really breaking in
while (first->rightSiblingPtr != NULL) //toss all the heaps into the queue/array/vector/call it what you like :)
{
heapVector.push_back(first ); //enqueue
PairingNode* temp = first; //break the bonds between siblings
first->rightSiblingPtr = NULL; //broken
first = temp->rightSiblingPtr; //repeat for next sibling
}
while (first->rightSiblingPtr != NULL) //toss all the heaps into the queue/array/vector/call it what you like :)
{
heapVector.push_back(first
PairingNode* temp = first; //break the bonds between siblings
first->rightSiblingPtr = NULL; //broken
first = temp->rightSiblingPtr; //repeat for next sibling
}
>>that's a good point, except that I check for root = null before calling that function
Nope, not quite. You are explicitily setting root = null the line before, if the if() condition is true. Note the 2nd line in the 3 line excerpt I included.
Nope, not quite. You are explicitily setting root = null the line before, if the if() condition is true. Note the 2nd line in the 3 line excerpt I included.
If you are using Visual Studio, run it under debug mode and when it generates the exception, debug to find the line it broke on and examine the values of the pointers.
ASKER
ah yes, good point. I fixed that part of it, but I just did some basic cout's at various part of the code to see what the last line executed is (yes yes, shame on me for not taking the time to learn how to use a decent debugger) and it's breaking at the line
first = temp->rightSiblingPtr;
first = temp->rightSiblingPtr;
Bugs below. Usually walking through a data structure this is bad form:
while(ptr->next) ...
Its better form to do:
while(ptr)
or at least
while(ptr && ptr->next)
The reason I say it is due to the mistake you made below. See my comments inline. When 2 pointers point to the same node, modifying one of the members of that node affects both pointers, because it is the same object.
while(ptr->next) ...
Its better form to do:
while(ptr)
or at least
while(ptr && ptr->next)
The reason I say it is due to the mistake you made below. See my comments inline. When 2 pointers point to the same node, modifying one of the members of that node affects both pointers, because it is the same object.
while (first->rightSiblingPtr != NULL) // I RECOMMEND if(first && first->rightSiblingPtr)
{
heapVector.push_back(first);
PairingNode* temp = first; // TEMP = FIRST, SO ANY CHANGES TO FIRST MEMBERS APPLY TO TEMP
first->rightSiblingPtr = NULL; // temp->rightSiblingPtr now = NULL as as well
first = temp->rightSiblingPtr; // first now equals NULL!
}
>>I just did some basic cout's
Another point of advice. When code is crashing don't use cout to debug, use cerr. Why? cout is buffered. Code can crash before the buffer is flushed. cerr will write immediately, no buffering.
Another point of advice. When code is crashing don't use cout to debug, use cerr. Why? cout is buffered. Code can crash before the buffer is flushed. cerr will write immediately, no buffering.
ASKER
Ok, I should have realized that affecting one affects the other, so is there a clear way to 'break' the links between the new collection of heaps without losing them all in the process (since if i say first->rightSiblingPtr = NULL we lose all of the siblings and their children, etc
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
ah shoot, for some reason the deletion still isn't working, though the segfault is gone...now it's a logic problem
i'm getting strange output for the deletions, as illustrated by my output:
--------------------
Pairing Heap Portion
--------------------
1 2 3 4 5 6 7 8 9 10
Levelorder
1 10 9 8 7 6 5 4 3 2
deleting min #1
Levelorder
3 4 5 6 7 8 9 10
deleting min #2
Levelorder
4 5 6 7 8 9 10
deleting min #3
Levelorder
5 6 7 8 9 10
-------------------------- ---------- ---------- -----
10 9 8 7 6 5 4 3 2 1
Levelorder
1 2 3 4 5 6 7 8 9 10
deleting min #1
Levelorder
2 3 4 5 6 7 8 9 10
deleting min #2
Levelorder
3 4 5 6 7 8 9 10
deleting min #3
Levelorder
4 5 6 7 8 9 10
-------------------------- ---------- ---------- -----
1 3 5 7 9 2 4 6 8 10
Levelorder
1 10 8 6 4 2 9 7 5 3
deleting min #1
Levelorder
2 5 7 9 4 6 8 10
deleting min #2
Levelorder
5 9 7
deleting min #3
Levelorder
9
-------------------------- ---------- ---------- -----
i'm getting strange output for the deletions, as illustrated by my output:
--------------------
Pairing Heap Portion
--------------------
1 2 3 4 5 6 7 8 9 10
Levelorder
1 10 9 8 7 6 5 4 3 2
deleting min #1
Levelorder
3 4 5 6 7 8 9 10
deleting min #2
Levelorder
4 5 6 7 8 9 10
deleting min #3
Levelorder
5 6 7 8 9 10
--------------------------
10 9 8 7 6 5 4 3 2 1
Levelorder
1 2 3 4 5 6 7 8 9 10
deleting min #1
Levelorder
2 3 4 5 6 7 8 9 10
deleting min #2
Levelorder
3 4 5 6 7 8 9 10
deleting min #3
Levelorder
4 5 6 7 8 9 10
--------------------------
1 3 5 7 9 2 4 6 8 10
Levelorder
1 10 8 6 4 2 9 7 5 3
deleting min #1
Levelorder
2 5 7 9 4 6 8 10
deleting min #2
Levelorder
5 9 7
deleting min #3
Levelorder
9
--------------------------
Yes, it appears to be deleting the node (1) and its left child maybe?
Sounds like you should already have a program with tree/heap implemented. If not, thats the 1st step of this assignment.