Solved

Level Order traversal of left child right sibling implementation.

Posted on 2009-04-04
16
1,461 Views
Last Modified: 2013-12-14
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?
0
Comment
Question by:Kibbe
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 9
  • 7
16 Comments
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24069265
Under the homework rule, you have to make a start yourself, and ask for specific help, we cannot start it for you.

Sounds like you should already have a program with tree/heap implemented. If not, thats the 1st step of this assignment.
0
 

Author Comment

by:Kibbe
ID: 24069273
Ah i figured it out myself, I had written

void PairingHeap::levelorder(PairingNode *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->leftChildPtr);
                        
                        while (temp->rightSiblingPtr != NULL)
                        {
                              levelorderQueue.push(temp->rightSiblingPtr);
                              temp = temp->rightSiblingPtr;
                        }
                  }
      }
}//end level order traversal

the while(temp->rightSiblingPtr != 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
0
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24069284
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.
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:Kibbe
ID: 24069293
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->leftChildPtr);
      delete temp;//maybe take this out?
      temp = NULL;//-------------------
}

PairingNode* PairingHeap::joinSiblings(PairingNode* 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(heapVector.begin());
      while (!heapVector.empty())
      {
            first = merge(first, heapVector.at(0)); //first element
            heapVector.erase(heapVector.begin());
      }
      return first;
}
0
 

Author Comment

by:Kibbe
ID: 24069301
also i've narrowed down that the seg fault is occuring in the while loop of joinSiblings
0
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24069309
     if (root->leftChildPtr == NULL)
            root = NULL;
      root = joinSiblings(root->leftChildPtr);  // what happens here if root is null? NULL pointer access at root->

Always check p if you are going to use p->


0
 

Author Comment

by:Kibbe
ID: 24069312
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
      }
0
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24069318
>>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.

0
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24069324
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.
0
 

Author Comment

by:Kibbe
ID: 24069328
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;
0
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24069341
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 (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!
}

Open in new window

0
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24069345
>>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.
0
 

Author Comment

by:Kibbe
ID: 24069350
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
0
 
LVL 40

Accepted Solution

by:
mrjoltcola earned 250 total points
ID: 24069357
Sure, you could rewrite it as below, instead of using temp to assign 'first' to it, assign first->rightSiblingPtr to temp, then after you null first->rightSiblingPtr, temp still points to the sibling, and  you can move first to point to temp.


  // assume you checked if(first != NULL)
 
  PairingNode* temp = first->rightSiblingPtr;
  first->rightSiblingPtr = NULL;  // temp is now the only reference to the sibling
  first = temp;

Open in new window

0
 

Author Comment

by:Kibbe
ID: 24069382
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

---------------------------------------------------
0
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24069408
Yes, it appears to be deleting the node (1) and its left child maybe?
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Ever wonder how to "do" object oriented programming (OOP)?
Before You Read The Article Please make sure you understand these two concepts: Variable Scope (http://www.php.net/manual/en/language.variables.scope.php) and Property Visibility (http://www.php.net/manual/en/language.oop5.visibility.php).  And to …
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…

729 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question