Binary Tree traversal (Non-recursive/iterative)

♠ Posted by GeekyFry in ,,,,, at 10:32 AM

How to traverse Binary tree iteratively



Pre-Order traversal:
1
2
3
4
5
6
7
8
9
10
11
void preOrder(Node * t)
{
  StackPush(t);
  while(!isStackEmpty())
  {
    t = StackPop();
    (*visit)(t); /* print or perform some fn on visiting this node */
    StackPush(t->right);
    StackPush(t->left);
  }
}
———————————————————
In-Order traversal:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InOrder(Node * t)
{
    do
    {
      while(t)
      {
        StackPush(t);
        t = t->left();
      }
      t = StackPop();
      (*visit)(t); /* print or perform some fn on visiting this node */
      t = t->right;
    } while (t || !isStackEmpty())
}
———————————————————

0 comments:

Post a Comment