tree traversal

This is a discussion on tree traversal within the C++ Programming forums, part of the General Programming Boards category; can someone tell me if i did this right? Code: void TraversePreOrder(TreeNode *root, apstack<char> &s){ if(root!=0){ s.push(root->info); TraversePreOrder(root->left, s); TraversePreOrder(root->right, ...

  1. #1
    Registered User
    Join Date
    Sep 2001
    Posts
    85

    tree traversal

    can someone tell me if i did this right?

    Code:
    void TraversePreOrder(TreeNode *root, apstack<char> &s){
        if(root!=0){
            s.push(root->info);
            TraversePreOrder(root->left, s);
            TraversePreOrder(root->right, s);
        }
    }
    
    void TraversePostOrder(TreeNode *root, apstack<char> &s){
        if(root!=0){
            TraversePostOrder(root->left, s);
            TraversePostOrder(root->right, s);
            s.pop(root->info);
        }
    }
    if root initially points to

    Code:
            A
       B      C
     D  E   F  G
    what is the resulting tree after the following is executed

    apstack<char> stack;
    TraversePreOrder(root,stack);
    TraversePostOrder(root,stack);

    after the the first function the stack would contain GFCEDBA, with g at the top, right?

    after the second function, the tree would be:

    Code:
             A
         C      B
       G  F   E  D
    am i correct?
    Last edited by qwertiop; 01-30-2002 at 05:14 PM.

  2. #2
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    >after the the first function the stack would contain GFCEDBA, with g at the top, right?

    Yes.

    >after the second function, the tree would be: ..snip

    No, post order will walk to the far right leaf before adding altering a value from your stack, in this case it will make it 'G', then to the furthest right 'left leaf' (if there is one) in this case making it 'F', and then to the parent, and so on....

    You should get the original tree. Pre-order is the reverse of post-order. So reversing a post-order using a stack, you'll get the values inserted as if you were inserting using a pre-order traversal (which is how they were removed).

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    85
    hum, i'm kind of confused. do you mean that the tree after the execution will be the same as before?

  4. #4
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    Yes, unless I've misunderstood what you're trying to do.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Tree traversal
    By recluse in forum C Programming
    Replies: 4
    Last Post: 12-05-2004, 03:00 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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