[알고리즘/java] 이진트리순회(DFS)

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

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

 

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

이면지에 허접한 손그림..^^

전위순회 : 1 2 4 5 3 6 7

중위순회 : 4 2 5 1 6 3 7

후위순회 : 4 5 2 6 7 3 1

 

class Node {
	int data;
	Node lt, rt;

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

public class Main {

	private static Node root;

	public static void DFS(Node root) {
		if (root == null)
			return;
		else {
			DFS(root.lt);
			DFS(root.rt);
		}

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		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);

	}

}

위의 트리구조를 Node class를 이용하여 만든다.

 

트리 구조를 노드를 이용해 표현

 

DFS메소드 내에서 출력 라인을 어디에 두느냐에 따라 전위순회, 중위순회, 후위순회가 된다.

public static void DFS(Node root) {
		if (root == null)
			return;
		else {
			System.out.print(root.data + " ");
			DFS(root.lt);
			DFS(root.rt);
		}

	}

>> 전위순회

public static void DFS(Node root) {
		if (root == null)
			return;
		else {
			DFS(root.lt);
			System.out.print(root.data + " ");
			DFS(root.rt);
		}

	}

>> 중위순회

public static void DFS(Node root) {
		if (root == null)
			return;
		else {
			DFS(root.lt);
			DFS(root.rt);
			System.out.print(root.data + " ");
		}

	}

>> 후위순회

 

재귀과정을 좀 더 쉽게 이해하려면, 저번 게시글

2021.12.10 - [인프런 강의/자바 알고리즘 문제풀이: 코딩테스트 대비] - [알고리즘/java] 인프런 자바 알고리즘 강의 : 재귀함수

처럼 스택프레임을 직접 그려가며 따라가봐야 한다.