이진트리 순회

01 May 2023 in Algorithm on Java, Coding, Test

문제

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

전위순회 출력 : 1 2 4 5 3 6 7

중위순회 출력 : 4 2 5 1 6 3 7

후위순회 출력 : 4 5 2 6 7 3 1

해결방법

• 순회 관련 문제(깊이 우선 탐색)
  • 전위 순회 - 루트 노드를 먼저 탐색
  • 중위 순회 - 루트 노드를 중간에 탐색
  • 후위 순회 - 루트 노드를 맨 마지막에 탐색

코드

import java.util.*;

// 노드 클래스를 따로 생성하여 데이터를 갖고 있는다.
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.Main tree=new Main.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); 
    } 
}