[자료구조] 이진트리 순회(DFS : Depth - First Search)

 

깊이 우선 탐색 (DFS)

• 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
  • 미로를 탐색할 때 한 방향으로 갈 수 있을때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
  • 즉, 넓게(wide) 탐색하기 전에 깊게 탐색하는 것이다.
  • 사용하는 경우 : 모든 노드를 방문하고자 하는 경우에 이 방법을 택한다.
  • 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
  • 깊이 우선 탐색(DFS)의 검색 속도가 너비 우선 탐색에 비해서 느리다.

 

 

 

 

이진트리 순회

 

• 전위 순회  출력 : 1 2 4 5 3 6 7
  • 루트 - 왼쪽 자식 - 오른쪽 자식
• 중위 순회 : 4 2 5 1 6 3 7
  • 왼쪽 자식 - 루트 - 오른쪽 자식
• 후위순회 : 4 5 2 6 7 3 1
  • 왼쪽 자식 - 오른쪽 자식 - 루트 

 

💡 이진 트리 만들기

public  class Solution {
    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);
    }
    
    static class Node {
    	int data;
    	Node lt, rt;
    	
    	Node(int data) {
    		this.data = data;
    		lt = rt = null;
    	}
    }
}

 

 

🔍 전위 순회 (PreOrder) Root - L - R

public  class Solution {
    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);
    	DFS(root);
    }
    
    static class Node {
    	int data;
    	Node lt, rt;
    	
    	Node(int data) {
    		this.data = data;
    		lt = rt = null;
    	}
    }
    
    static void DFS(Node root) {
    	if(root == null) return;
    	
    	System.out.print(root.data + " ");
    	DFS(root.lt);
    	DFS(root.rt);
    }
}

1 2 4 5 3 6 7

 

 

🔍 중위 순회 (InOrder) L - Root- R

public  class Solution {
    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);
    	DFS(root);
    }
    
    static class Node {
    	int data;
    	Node lt, rt;
    	
    	Node(int data) {
    		this.data = data;
    		lt = rt = null;
    	}
    }
    
    static void DFS(Node root) {
    	if(root == null) return;
    	
    	DFS(root.lt);
    	System.out.print(root.data + " ");
    	DFS(root.rt);
    }
}

4 2 5 1 6 3 7

 

 

🔍 후위 순회 (PostOrder) L - R - Root

public  class Solution {
    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);
    	DFS(root);
    }
    
    static class Node {
    	int data;
    	Node lt, rt;
    	
    	Node(int data) {
    		this.data = data;
    		lt = rt = null;
    	}
    }
    
    static void DFS(Node root) {
    	if(root == null) return;
    	
    	DFS(root.lt);
    	DFS(root.rt);
    	System.out.print(root.data + " ");
    }
}

4 5 2 6 7 3 1

 

 

 

 

---

👀 참고 자료

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog