0331_반복 방식으로 구현한 이진트리 순회

-재귀를 사용하지 않고

 

반복 방식으로 구현한 이진트리 순회 // 재귀를 사용 안하겠다.
재귀를 사용하지않으면 스택을 사용하게 된다.
루트 노드를 스택에 넣는다.
  스택이 빌떄 까지 루프를 돈다.
  스택에서 팝하여 노드를 출력
  오른족 노드가 있으면 스택에 저장
  왼쪽 노드가 있으면 스택에 저장. 

 

 

----

 

 

  public void PreOrderIterative()
        {
            //스택생성
            var stack = new Stack<BinaryNode>();
            //루트를 스택에 넣는다. //Push
            stack.Push(this.root);
            //스택요소가 있으면 반복한다.
            while (stack.Count > 0) {
                //꺼낸다.
                var node = stack.Pop(); // 제일 위에 있는 걸 꺼낸다.
                //출력한다.
                Console.Write("{0}", node.data);
                //오른쪽에 넣는다. // 나중에 나오는게 왼쪽이니깐, 오른쪽부터 넣는다.
                if (node.right != null) {
                    stack.Push(node.right);
                }
                //왼쪽에 넣는다.
                if (node.left != null) {
                    stack.Push(node.left);
                }
            
            }
        }
    }

 

 

 

스택의 카운터가 0아 아니면 순회

-> 스택의 제일 위에 있는 값을 꺼냄

-> 그 값을 출력함

-> 그 값의 오른쪽 있으면 스택에 담음, 왼쪽 있으면 스택에 담음

-> 스택의 카운터 비교 ( 0 아니면 계속 순회)

-> 제일 위에 있는 값 꺼냄

-> 그 값을 출력함

-> 그 값의 오른쪽 있으면 스택에 담음, 왼쪽 있으면 스택에 담음

------>. 계속 반복

 

이런 알고리즘으로 계속 순회하다가.

카운터가 0이 되면 끝나게 된다.

 

----

다른 예시

 

using System;

namespace study18

{
    public class App
    {
        public App()
        {
            Console.WriteLine("App");
            BinaryTree tree = new BinaryTree("A");
            tree.root.left = new BinaryNode("B");
            tree.root.right = new BinaryNode("C");
            tree.root.left.right = new BinaryNode("D");
            tree.root.right.right = new BinaryNode("E");
            tree.root.left.right.left = new BinaryNode("F");
            tree.root.left.right.right = new BinaryNode("G");
            tree.root.right.right.left = new BinaryNode("H");

            //tree.PreorderTraversal();
            //Console.WriteLine(" ");
            //tree.InorderTraversal();
            //Console.WriteLine(" ");
            //tree.PostorderTraversal();
            //Console.WriteLine(" ");
            tree.PreOrderIterative();
        }
    }
}

 

 

 

공책이랑 비교했을때 똑같이 결과가 나옴