postorder traversal using a stack?

This is a discussion on postorder traversal using a stack? within the C++ Programming forums, part of the General Programming Boards category; can anyone tell me if this would be the correct code or have suggestions for improvement? stack <tnode*> st; cout ...

  1. #1
    Unregistered
    Guest

    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

  2. #2
    Registered User
    Join Date
    Apr 2002
    Posts
    362
    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
    "When the only tool you own is a hammer, every problem begins to resemble a nail." Abraham Maslow

  3. #3
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  4. #4
    Registered User
    Join Date
    Apr 2002
    Posts
    362
    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
    "When the only tool you own is a hammer, every problem begins to resemble a nail." Abraham Maslow

  5. #5
    Banned frenchfry164's Avatar
    Join Date
    Oct 2001
    Posts
    1,552
    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

  6. #6
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    [s]he?
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.

    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-11-2006, 11:41 PM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 09:12 PM
  4. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 05:27 PM
  5. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 05:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21