postorder traversal using a stack?

can anyone tell me if this would be the correct code or have suggestions for improvement?



stack <tnode*> st;

cout << "Post-order traversal: ";

p=root;

while(p!=0)
{
while(p->Llink != 0)
{
s.push(p);
p = p->Llink;
}//end while

cout << p->data << " ";

while(p->Rlink != 0)
{
cout << p->data << " ";
p = s.top();
s.pop();
}//end while

if (p->Rlink != 0)
p = p->Rlink;
else p = 0;

}//end while

Hard to say, frankly. You've given us partial code which is incomplete at best, and flat-out wrong at its worst.

Unless 'tnode' was "typedef'd", I'm not familiar with the type. (Wouldn't be unusual, but I throw this in anyway.)

Your stack variable, 'st', is never used in the code you've presented. (You use 's'.)

'p' is undeclared in the code you post. (Is it, presumably, declared as a pointer?)

Terse...yes. Unkind...I don't mean it to be, and I hope you'll understand. Browse the Board. (Search out posts by Prelude. Read the links that are posted in his "signature". He doesn't always remember which Board he's on, but, what the heck? :) )

My point - if I'd get to it - is that your code "snippet" simply doesn't give me enough to go on. I'm not going to "guess".

-Skipper

Mindblowing news, Prelude isn't a he :).

I looked at the code, but honestly couldn't tell either. The simpliest way to check it will be to write a recursive post-order (so simple you can't mess it up) as well as the stack based traversal, and make sure that the stack based one outputs the same as the recursive post-order with every case you test.

Quote:

---

Mindblowing news, Prelude isn't a he.

---

We are definitely going to have to come up with a generic something-or-other to handle this without the "he/she" or "himself/herself" thing.

This is twice, in an embarassingly short period of time, that I've made a fool of myself by making the same mistake. (Did the same thing with SilentWolf.) You'd think I'd learn, wouldn't you? But, nooooo...

Thanks, SilentStrike, and my apologies, Prelude, wherever you are. :)

-Skipper

someone needs to create a standard way of saying he / she or him / her for the internet. And DO NOT try heshe. People might get the wrong idea ;D

edit: spelling

[s]he?

>can anyone tell me if this would be the correct code or have suggestions for improvement?
Well, a thorough paper run of your algorithm is always a good idea. You might want to try keeping as close to the recursive method as possible syntax-wise. Remember, push the node, push the right subtree, then the left subtree:

Code:

---

void postorder ( struct tree *t )
{
  init ( SIZE );
  push ( t );
  while ( !empty() ) {
    if ( t->right != NULL ) push ( t->right );
    if ( t->left != NULL ) push ( t->left );
    t = pop();
    cout<< t->data <<" ";
  }
}

---

Then work from there if you have any problems, but be sure to get it working on paper before writing any code. Otherwise you'll be tempted to make changes in the hope that it will work "this time" and you won't think as much as hack. :)

>and my apologies, Prelude, wherever you are.
No need, I'm used to all of this by now. :D

-Prelude