Traverse binary tree not recursively

       public static void PreOrder<T>(BinaryTreeNode<T> root, Action<BinaryTreeNode<T>> action)
        {
            if (root == null)
            {
                return;
            }
            Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
            stack.Push(root);
            while (stack.Count != 0)
            {
                BinaryTreeNode<T> current = stack.Pop();
                if (current != null)
                {
                    action(current);
                }
                if (current.RightChild != null)
                {
                    stack.Push(current.RightChild);
                }
                if (current.LeftChild != null)
                {
                    stack.Push(current.LeftChild);
                }
            }
        }
 
public static void InOrder<T>(BinaryTreeNode<T> root, Action<BinaryTreeNode<T>> action)
        {
            if (root == null)
            {
                return;
            }
            Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
            BinaryTreeNode<T> current = root;
            do
            {
                while (stack.Count != 0 && current == null)
                {
                    current = stack.Pop();
                    action(current);
                    current = stack.Pop();
                }
                if (current != null)
                {
                    stack.Push(current.RightChild);
                    stack.Push(current);
                    current = current.LeftChild;
                }
            } while (stack.Count != 0);
        }
 
        public static void LastOrder<T>(BinaryTreeNode<T> root, Action<BinaryTreeNode<T>> action)
        {
            if (root == null)
            {
                return;
            }
            Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
            BinaryTreeNode<T> current = root;
            do
            {
                if (current.HasChildren)
                {
                    stack.Push(current);
                    if (current.LeftChild != null)
                    {
                        if (current.RightChild != null)
                        {
                            stack.Push(current.RightChild);
                        }
                        current = current.LeftChild;
                    }
                    else
                    {
                        current = current.RightChild;
                    }
                }
                else
                {
                    action(current);
                    while (stack.Count != 0 && current.IsChildrenOf(stack.Peek()))
                    {
                        current = stack.Pop();
                        action(current);
                    }
                    if (stack.Count != 0)
                    {
                        current = stack.Pop();
                    }
                }
            } while (stack.Count != 0);
        }
Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s