Java : DFS 이진 트리 순회

• 이진 트리는 분할 정복 탐색 알고리즘으로 빠른 속도로 탐색이 가능하다.
• 탐색 방법에 따라 전위, 중위, 후위로 나뉜다.

전위

• 노드를 기준으로 부모 -> 자식 왼쪽 -> 자식 오른쪽으로 검사한다.
• 자식이 여럿 있을 경우 끝까지 파고 간다.
• 순서 : 1 2 4 5 3 6 7

중위

• 자식 왼쪽 -> 부모 -> 자식 오른쪽
• 왼쪽 끝까지 간 후 부모를 지나 오른쪽으로 간다.
• 순서 : 4 2 5 1 6 3 7

후위

• 자식 왼쪽 -> 자식 오른쪽 -> 부모
• 자식을 먼저 탐색 후 부모에게 간다.
• 순서 : 4 5 2 6 7 3 1

구현

//노드 클래스
public class Node {
	private final int data;
	Node lt, rt;

	public Node(int val) {
		this.data = val;
		this.lt = this.rt = null;
	}

	public int getData() {
		return data;
	}
}

public class BinaryTreeTraversal {

	public static void main(String[] args) {
		Node tree = new Node(1);
		tree.lt = new Node(2);
		tree.rt = new Node(3);
		tree.lt.lt = new Node(4);
		tree.lt.rt = new Node(5);
		tree.rt.lt = new Node(6);
		tree.rt.rt = new Node(7);
		dfs(tree);
	}

	static void dfs(Node root) {
		if (root != null) {
        		// 전위 | 결과 : 1 2 4 5 3 6 7 
            		System.out.print(root.getData() + " ");
			dfs(root.lt);
   		        //이곳에서 출력 시 중위 | 결과 : 4 2 5 1 6 3 7 
			dfs(root.rt);
        		//이곳에서 출력 시 후위 | 결과 : 4 5 2 6 7 3 1 
		}
	}
}