DFS

이진 트리 순회( 깊이 우선 탐색 )

1. 전위순회 : 부모를 제일 먼저 방문 ( 부모 - 왼쪽자식 -오른쪽 자식 ) / 1 - 2 - 4 - 5 - 3 - 6 - 7
2. 중위순회 : 부모를 중간에 방문 ( 부모 - 왼쪽자식 -오른쪽 자식 ) / 4 - 2 - 5 - 1 - 6 - 3 - 7
3. 후위순회 : 부모를 가장 나중에 방문 ( 왼쪽자식 -오른쪽 자식 - 부모 ) / 4 - 5 - 2 - 6 - 7 - 3 - 1

 

// 이진 트리의 노드 
class Node{
	int data; 
	Node lt, rt; // Node 객체 주소 저장 
	public Node(int val){
		data=val; 
		lt=rt=null; 
	}
}

public class Main {	
	Node root; 
	public void DFS(Node root) {
		if(root==null) return; // 말단 Node로 온 경우
		else {
			// 전위순회
			System.out.print(root.data + " ");
			DFS(root.lt);
			DFS(root.rt); 
		}
		/*
		 * 중위순회
			else {
				DFS(root.lt);
				System.out.print(root.data + " ");
				DFS(root.rt); 
			}
			후위순회
			else {
				DFS(root.lt);
				DFS(root.rt); 
				System.out.print(root.data + " ");
			}
		*/
	}
	// 이진 트리 생성, DFS 수행
	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/course/lecture?courseSlug=%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84&unitId=72767&tab=curriculum