-
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
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:
am i correct?
-
>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).
-
hum, i'm kind of confused. do you mean that the tree after the execution will be the same as before?
-
Yes, unless I've misunderstood what you're trying to do.