[4.1] Binary Tree Traversal 복습

using System;

namespace Study03
{
    public class App
    {
        public App()
        {
            /*
             *          A
             *         / \
             *        /   \
             *       B     C
             *      / \   /
             *     /   \ /
             *    D    E F
             */
            BinaryTree tree = new BinaryTree();
            Node root = tree.SetRoot("A");
            Node b = tree.SetLeft(root, "B");
            Node c = tree.SetRight(root, "C");
            Node d = tree.SetLeft(b, "D");
            Node e = tree.SetRight(b, "E");
            Node f = tree.SetLeft(c, "F");

            Console.Write("Preorder Traversal : ");
            tree.PreorderTraversal();
            Console.Write("Inorder Traversal : ");
            tree.InorderTraversal();
            Console.Write("Postorder Traversal : ");
            tree.PostorderTraversal();
        }
    }
}

 

using System;
using System.Collections.Generic;

namespace Study03
{
    public class Node
    {
        public string data;
        public Node left;
        public Node right;
        public Node(string data)
        {
            this.data = data;
        }
    }

    public class BinaryTree
    {
        private Node root;
        public BinaryTree()
        {
            this.root = null;
        }

        public Node SetRoot(string data)
        {
            this.root = new Node(data);
            return this.root;
        }

        public Node SetLeft(Node parent, string data)
        {
            if (parent.left == null)
            {
                parent.left = new Node(data);
            }
            return parent.left;
        }

        public Node SetRight(Node parent, string data)
        {
            if (parent.right == null)
            {
                parent.right = new Node(data);
            }
            return parent.right;
        }

        public void PreorderTraversal()
        {
            PreorderTraversalImpl(this.root);
            Console.WriteLine();
        }

        public void InorderTraversal()
        {
            InorderTraversalImpl(this.root);
            Console.WriteLine();
        }

        public void PostorderTraversal()
        {
            PostorderTraversalImpl(this.root);
            Console.WriteLine();
        }

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

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

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

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

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

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

        //Preorder Traversal을 Stack으로 구현
        public void PrintPreorderIterative()
        {
            Stack<Node> stack = new Stack<Node>();
            stack.Push(this.root);

            while (stack.Count > 0)
            {
                var temp = stack.Pop();
                if (temp.right != null)
                {
                    stack.Push(temp.right);
                }
                if (temp.left != null)
                {
                    stack.Push(temp.left);
                }
                Console.Write("{0} ", temp.data);
            }
            Console.WriteLine();
        }

        //Inorder Traversal을 Stack으로 구현
        public void PrintInorderIterative()
        {
            Stack<Node> stack = new Stack<Node>();
            var node = this.root;

            while (node != null)
            {
                stack.Push(node);
                node = node.left;
            }

            while (stack.Count > 0)
            {
                var popNode = stack.Pop();
                Console.Write("{0} ", popNode.data);
                if (popNode.right != null)
                {
                    var temp = popNode.right;
                    while (temp != null)
                    {
                        stack.Push(temp);
                        temp = temp.left;
                    }
                }
            }
            Console.WriteLine();
        }

        //Inorder Traversal을 Stack으로 구현, 중복부분 생략
        public void PrintInorderIterative2()
        {
            Stack<Node> stack = new Stack<Node>();
            var node = root;

            while (node != null || stack.Count > 0)
            {
                while (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }

                node = stack.Pop();
                Console.Write("{0} ", node.data);

                node = node.right;
            }
            Console.WriteLine();
        }

        //Postorder Traversal을 Stack으로 구현
        public void PrintPostorderIterative()
        {
            //스택을 만든다 
            var stack = new Stack<Node>();
            //변수에 루트를 넣는다 
            var node = root;
            //왼쪽 끝까지 오른쪽 노드와 루트노드를 넣는다 
            while (node != null)
            {
                if(node.right != null)
                {
                    stack.Push(node.right);
                }
                stack.Push(node);
                node = node.left;
            }

            //스택에 요소가 있으면 반복 
            //꺼낸다 
            //Top에 있는 요소와 비교한다 
            //같다면 
            //꺼낸다 
            //루트를 넣는다 
            while(stack.Count > 0)
            {
                node = stack.Pop();
                if(node.right != null && stack.Count > 0 && node.right == stack.Peek())
                {
                    stack.Pop();
                    stack.Push(node);
                    node = node.right;

                    //마지막 왼쪽노드가 없을때까지 반복 
                    //우측노드 넣고 루트 넣고 
                    //왼쪽 노드 확인 

                    while (node != null)
                    {
                        if(node.right != null)
                        {
                            stack.Push(node.right);
                        }
                        stack.Push(node);
                        node = node.left;
                    }
                }
                //틀리다면 
                //출력한다 
                else
                {
                    Console.Write("{0} ", node.data);
                }
            }
        }
    }
}