|
exact code for postorder traversal of tree without use of recursion -----
Microsoft Interview Questions and Answers
(Continued from previous question...)
43. exact code for postorder traversal of tree without use of recursion -----
Question:
exact code for postorder traversal of tree without use of recursion.
structure of tree is:
struct btree
{
struct btree*left;
int*data;
struct btree*right;
}
maybe an answer1:
This code is easy to remember because it is similar in structure to the recursive version. Uses a single stack with bool flag embedded in node to track state of node.
Simple, neat and petite.
template
struct Node {
Node(T _data) : item(false),data(_data),
left(0), right(0){}
Node() : item(false),data(), left(0), right(0){}
Node* asItem() { item=true; return this;}
Node* asLink() { item=false; return this;}
bool isItem() const {return item; }
bool item; T data; Node* left; Node* right;
};
typedef Node<int> Tree;
void postOrderIterative(Tree* root) {
if(!root) return;
std::stack<Tree*> s; s.push( root->asLink() );
while( !s.empty() ) {
root = s.top(),s.pop();
if( root->isItem() ) {
std::cout << root->data << std::endl;
} else {
s.push( root->asItem() );
if( root->right ) s.push(root->right->asLink());
if( root->left ) s.push(root->left->asLink());
}
}
}
maybe an answer2:
use this one which the simplest way to do postorder iteratively
void PostOrder(struct node *T)
{
struct node *temp=T;
stack *s1=NULL,*s2=NULL;
if(temp==NULL)
return;
Push(temp,s1);
while(!isEmpty(s1))
{
temp=Pop(s1);
Push(temp,s2);
if(temp->left)
Push(temp->left,s1);
if(temp->right)
Push(temp->right,s2); // Push(temp->right,s1);
}
while(!isEmpty(s2))
printf("%d",(Pop(s2))->data);
}
(Continued on next question...)
Other Interview Questions
| 