[문제풀이] 07-05. 이진 트리 순회(DFS)

인프런, 자바(Java) 알고리즘 문제풀이

Recursive, Tree, Graph - 0705. 이진 트리 순회(DFS)

---

🗒️ 문제

---

🎈 나의 풀이

	 public static class Node {
        int data;
        Node lt, rt;

        public Node(int val) {
            data = val;
            lt = rt = null;
        }
    }

    public static void preorderTraversal(Node node) {
        if(node == null) return;
        System.out.print(node.data + " ");
        preorderTraversal(node.lt);
        preorderTraversal(node.rt);
    }

    public static void inorderTraversal(Node node) {
        if(node == null) return;
        inorderTraversal(node.lt);
        System.out.print(node.data + " ");
        inorderTraversal(node.rt);
    }

    public static void postorderTraversal(Node node) {
        if(node == null) return;
        postorderTraversal(node.lt);
        postorderTraversal(node.rt);
        System.out.print(node.data + " ");
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
        root.rt.lt = new Node(6);
        root.rt.rt = new Node(7);

        System.out.print("전위 순회 출력 : ");
        preorderTraversal(root);

        System.out.print("\n중위 순회 출력 : ");
        inorderTraversal(root);

        System.out.print("\n후위 순회 출력 : ");
        postorderTraversal(root);
    }

---

🖍️ 강의 풀이

  class Node{ 
      int data; 
      Node lt, rt; 
      public Node(int val) { 
          data=val; 
          lt=rt=null; 
      } 
  } 

  public class Main{ 
      Node root; 
      public void DFS(Node root){ 
          if(root==null) 
              return; 
          else{
              DFS(root.lt);
              System.out.print(root.data+" ");
              DFS(root.rt);
          }
      } 

      public static void main(String args[]) { 
          Main tree=new Main(); 
          tree.root=new Node(1); 
          tree.root.lt=new Node(2); 
          tree.root.rt=new Node(3); 
          tree.root.lt.lt=new Node(4); 
          tree.root.lt.rt=new Node(5); 
          tree.root.rt.lt=new Node(6); 
          tree.root.rt.rt=new Node(7);
          tree.DFS(tree.root); 
      } 
  } 

---

💬 짚어가기

DFS란?

해당 문제는 DFS(Depth-First Search) : 깊이 우선 탐색 알고리즘의 예시이다.
이는 그래프 탐색 방식의 하나로, 그래프 탐색이란 하나의 정점으로부터 시작하여 차례로
모든 정점들을 한 번씩 방문하는 것이다.

그 중 DFS는 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기
전에 해당 분기를 완벽하게 탐색하는 방법이다.

미로에서 길찾기를 할 때 한 뱡향으로 길을 찾아 가다가, 막다른 길이 나와 더 이상 갈 수 없게
되었을 때 가장 가까운 갈림길에서 다른 방향으로 탐색을 이어나가는 방법과 유사하다.

이렇게 DFS는 정해진 규칙으로 더 이상 탐색할 곳이 없을 때 까지, 깊게 탐색하는 것이다.

Node와 Tree 만들기
2진 트리 구조를 만들기 위해선 Node는 자신이 보관할 데이터를 갖고, 트리 구조를 위해 자신
아래에 위치할 두 개의 Node 가져야한다. 이를 코드로 구현하면 아래와 같다.

  class Node{ 
      int data; 
      Node lt, rt; 
      
      public Node(int val) { 
          data=val; 
          lt=rt=null; 
      } 
  }

이제 루트 Node를 시작으로 해당 노드의 lt와 rt 노드들을 통해 트리를 순회할 수 있다.

트리 순회 방식 3가지

• 전위 순회 : 부모 노드 → 왼쪽 노드 → 오른쪽 노드
• 중위 순회 : 왼쪽 노드 → 부모 노드 → 오른쪽 노드
• 후위 순회 : 왼쪽 노드 → 오른쪽 노드 → 부모 노드

이를 코드로 구현하면 아래와 같다.

▶︎ 전위 순회

	public static void preorderTraversal(Node node) {
        if(node == null) return;
        System.out.print(node.data + " ");
        preorderTraversal(node.lt);
        preorderTraversal(node.rt);
    }

▶︎ 중위 순회

    public static void inorderTraversal(Node node) {
        if(node == null) return;
        inorderTraversal(node.lt);
        System.out.print(node.data + " ");
        inorderTraversal(node.rt);
    }

▶︎ 후위 순회

    public static void postorderTraversal(Node node) {
        if(node == null) return;
        postorderTraversal(node.lt);
        postorderTraversal(node.rt);
        System.out.print(node.data + " ");
    }