goood solutions for tree traversal

TracyJanuary 26, 2011 at 7:20 pm

@1337c0d3r:
I'm quite sure that my code of using one stack for post-order traversal works. You can use the same example above to go through it. I made iterative in-order, pre-order and post-order traversal as similar as possible:

void postorderNoR(const Node *root)
{
stack s;
const Node *itr = root;

while (itr || !s.empty()) {
if (!itr) {
while (!s.empty() &&
itr == s.top()->right) {
itr = s.top();
s.pop();
printf("%d ",itr->value);
}
itr = s.empty() ? NULL : s.top()->right;
}
else
{
s.push(itr);
itr = itr->left;
}
}
}

// *********************

void inorderNoR(const Node *root)
{
stack s;
const Node *itr = root;

while (itr || !s.empty()){
if (!itr){
itr = s.top();
s.pop();
printf("%d ",itr->value);
itr = itr->right;
}
else{
s.push(itr);
itr = itr->left;
}
}
}

// *********************

void preorderNoR(const Node *root)
{
stack s;
const Node *itr = root;

while (itr || !s.empty()){
if (!itr){
itr = s.top();
s.pop();
itr = itr->right;
}
else{
printf("%d ",itr->value);
s.push(itr);
itr = itr->left;
}
}
}

0