[JAVA] 깊이 우선 탐색(DFS) 전위/중위/후위 순회

그래프 탐색 알고리즘
탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 그래프 탐색 알고리즘은 DFS와 BFS가 있다.

구현 방법

DFS : 스택, 재귀함수
BFS : 큐

스택 자료구조

: 먼저 들어온 데이터가 나중에 나가는 형식으로(First In Last Out으로 FILO, 선입후출)의 자료구조이다.

큐 자료구조

: 먼저 들어온 데이터가 먼저 나가는 형식(First In First Out으로 FIFO, 선입선출)의 자료구조이다.

재귀함수

: 재귀함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다.

DFS
전위 순회 : 부모 -> 왼쪽 자식 -> 오른쪽 자식
: F B A D C E G I H
중위 순회 : 왼쪽 자식 -> 부모 -> 오른쪽 자식
: A B C D E F H I G
후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 부모
: A C E D B F H I G

자바를 이용한 전위/중위/후위 순회하기

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){
    	
    }
    
    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의 전위/ 중위/ 후위 순회

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{
            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.inflearn.com/

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

-> 이진트리순회(DFS : Depth-First Search)