Thread: Iterative Tree Traversal using a stack

Hi guys,

In my final thoughts on my scheduling algo, I have elected to imitate a recursive call with a stack. Thanks for the advice Codeplug. The pseudo code for my algo is as follows:

Code:

while(!empty())
    peek at top item; // This involves scheduling it, etc
    push() on next branches; // Put the next level of calls on stack
        continue if there were pushes done
    pop(); // Only do this if we didn't push anything on
        this mimics the return of the recursive function call
end while

All is well, except for one thing: After going down, then coming back up, I'll peek at the same node more than once. I somehow need to skip it, or pop it off the 2nd time I see it. Picture this tree for example:

Code:

            1
     /      |     \
    2      2      2
  / | \  / | \  / | \
  3 3 3  3 3 3  3 3 3

My goal is to travers the tree in normal order:
1 to 2 via left branch
2 to 3 via left branch
2 to 3 via middle branch
2 to 3 via right branch
1 to 2 via middle branch
2 to 3 via left branch
etc.....

Using my algorithm, I "visit" a node, and do the scheduling, etc, at the beginning of my while loop when I peek at the top. Later, I pop it off to simulate the recursive call. Thus, for example, when I've gone down the left third of the tree, my stack looks like this:

Code:

r m l r m l r m l
  1  |  2  |  3

Where r, m, l mean right, middle, left for the branches, and the numbers below are for what node we're talkinga about. After I've explored all three paths from 2 to 3, my stack will look like this:

Code:

r m l r m l
  1  |  2

This is where I run into a problem. Based on my algo, I will now peek at 2's left path, and push from there. Well, I already did that! How do I indicate that I need to pop that item, and insted travers 2's middle path?

My code is below, if it's any help. Kind of messy right now, with lots of global data (used to make my previous recursive solution faster) Any ideas??????

Thanks!

Code:

void solveIter ()
{
    stack<StackStructType> callStack;
    StackStructType current;

    current.job = 0;
    current.comp = '-';
    callStack.push(current);
    for (int i = Job::getMachPerJob() - 1; i >= 0 ; i--)
    {
        current.comp = jobs[current.job].getComp(i);   
        callStack.push(current);
    }
    while (!callStack.empty())
    {
        current = callStack.top();
        
        if (current.comp != '-' && !jobs[current.job].isScheduled())
        {
            numOfJobs++;
            if (numOfJobs > currentBest)
            {
                currentBest = numOfJobs;
                best = jobs;
            }
            computers[current.comp - 97].addJob(jobs[current.job].getEnd());
            jobs[current.job].setSchedule(current.comp);
        }
        if (current.job + 1 < jobSize)
        {
            current.job += 1;
            current.comp = '-';
            callStack.push(current);
            for (int i = Job::getMachPerJob() - 1; i >= 0; i--)
            {
                if (computers[jobs[current.job].getComp(i) - 97].isAvailable(jobs[current.job].getStart()))
                {
                    current.comp = jobs[current.job].getComp(i);   
                    callStack.push(current);
                }
            }
            continue;
        }
        current = callStack.top();
        callStack.pop();
        if (current.comp != '-')
        {
            numOfJobs--;
            computers[current.comp - 97].removeJob();
        }
    }
}