[3.31] Binary Tree Preorder 연습

private void PreorderTraversalImpl(Node node)
{
    if (node == null) return;

    Console.Write("{0} ", node.data);
    PreorderTraversalImpl(node.left);
    PreorderTraversalImpl(node.right);
}

public void PreorderIterative()
{
    Stack<Node> stack = new Stack<Node>();
    stack.Push(this.root);

    while (stack.Count > 0)
    {
        var temp = stack.Pop();
        Console.Write("{0} ", temp.data);

        if (temp.right != null)
        {
            stack.Push(temp.right);
        }
        if (temp.left != null)
        {
            stack.Push(temp.left);
        }
    }
}

using System;

namespace Study02
{
    public class App
    {
        public App()
        {
            BinaryTree tree = new BinaryTree("A");
            var B = tree.SetLeft(tree.GetRoot(), "B");
            var c = tree.SetRight(tree.GetRoot(), "C");
            var d = tree.SetLeft(B, "D");
            var e = tree.SetRight(B, "E");
            var f = tree.SetRight(c, "F");

            Console.Write("재귀를 사용한 전위순회 : ");
            tree.PreorderTraversal();
            Console.WriteLine();

            Console.Write("스택(반복)을 사용한 전위순회 : ");
            tree.PreorderIterative();
            Console.WriteLine();
        }
    }
}

스택을 사용한 Preorder Tree Traversal 그림

재귀, 스택을 이용한 순회가 동일한 결과를 가리킨다.