[알고리즘/java] 인프런 자바 알고리즘 강의 : 이진트리순회(DFS)

[알고리즘/java] 인프런 자바 알고리즘 강의 : 이진트리순회(DFS)

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

- https://inf.run/Azjw

이진트리 순회(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] 인프런 자바 알고리즘 강의 : 재귀함수

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

from http://bumbleb22.tistory.com/7 by ccl(A) rewrite - 2021-12-11 18:27:08