💡 이진트리 순회(DFS : 깊이우선탐색, Depth-First Search)

이진트리 순회(깊이우선탐색) 아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

 

 

[[ 코딩 인터뷰 : 00순회 출력을 숫자로 써서 표현해보세요. ]]

 

전위순회 출력 : 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객체의 주소를 저장하는 변수이므로 클래스형(Node형)으로 만듦
    Node lt, rt; 
    public Node(int val) { 
        data=val; 
        // 객체 생성시 null값
        lt=rt=null; 
    } 
} 
  
public class Main{ 
    // 참조형, Node클래스의 객체 주소를 저장하는 인스턴스 변수
    Node root; 
    public void DFS(Node root){ // root : 1번 data를 가지고 있는 노드
        if(root==null)  // 말단 노드로 온 것이므로 종료함
            return; 
        else{ // 두 번 뻗어야 하므로 함수 호출도 두 번
            // System.out.print(root.data+" "); 전위순회
            DFS(root.lt);
            // System.out.print(root.data+" "); 중위순회
            DFS(root.rt);
            // System.out.print(root.data+" "); 후위순회
        }
    } 
  
    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); 
    } 
}

 

 

+ 추가로 보면 좋은 영상

https://www.youtube.com/watch?v=9ZZbA2iPjtM