Write the following traversals.Depth-first Traversals: Pre-order, In-order, Post-order Breadth-first Traversal: Level-ordervoid preOrderTraversalRecursive(Node n)
{
if (n == null)
return;
visit(n);
preOrderTraversalRecursive(n.left);
preOrderTraversalRecursive(n.right);
}
void preOrderTraversalIterative(Node n)
{
if (n == null)
return;
Stack<Node> s = new Stack<Node>();
s.Push(n);
while (s.Count > 0)
{
n = s.Pop();
visit(n);
if (n.right != null)
s.Push(n.right);
if (n.left != null)
s.Push(n.left);
}
}
void inOrderTraversalRecursive(Node n)
{
if (n == null)
return;
inOrderTraversalRecursive(n.left);
visit(n);
inOrderTraversalRecursive(n.right);
}
void inOrderTraversalIterative(Node n)
{
Stack<Node> s = new Stack<Node>();
while(s.Count > 0 || n != null)
{
if (n != null)
{
s.Push(n);
n = n.left;
}
else
{
n = s.Pop();
visit(n);
n = n.right;
}
}
}
void postOrderTraversalRecursive(Node n)
{
if (n == null)
return;
postOrderTraversalRecursive(n.left);
postOrderTraversalRecursive(n.right);
visit(n);
}
void postOrderTraversalIterative(Node n)
{
Stack<Node> s = new Stack<Node>();
Node last = null, peek = null;
while (s.Count > 0 || n != null)
{
if (n != null)
{
s.Push(n);
n = n.left;
}
else
{
peek = s.Peek();
if (peek.right != null && last != peek.right)
n = peek.right;
else
{
visit(peek);
last = s.Pop();
}
}
}
}
void levelOrderTraversal(Node n)
{
if (n == null)
return;
Queue<Node> q = new Queue<Node>();
q.Enqueue(n);
while (q.Count > 0)
{
n = q.Dequeue();
visit(n);
if (n.left != null)
q.Enqueue(n.left);
if (n.right != null)
q.Enqueue(n.right);
}
}
|