섹션 7 Recursive, Tree, Graph - 5. 이진트리 순회(깊이우선탐색)

📌 문제 설명

이진트리(Binary Tree)가 주어졌을 때,
깊이우선탐색(DFS)을 이용해 전위순회, 중위순회, 후위순회를 연습한다.

아래와 같은 이진트리를 예시로 한다.

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

---

📝 입력 & 출력

입력

• 트리는 문제에 주어진 대로 직접 생성한다.
  (루트 노드부터 자식 노드를 차례로 연결)

출력

• 전위순회(Preorder) 결과 출력
• 중위순회(Inorder) 결과 출력
• 후위순회(Postorder) 결과 출력

---

🔹 예제 입력 & 출력

예제 출력

전위순회 출력: 1 2 4 5 3 6 7  
중위순회 출력: 4 2 5 1 6 3 7  
후위순회 출력: 4 5 2 6 7 3 1

---

💡 해결 방법

이진트리 순회(Traversal)는 크게 세 가지 방식이 있다.

• 전위순회 (Preorder Traversal)
  • "부모 → 왼쪽 자식 → 오른쪽 자식" 순서로 방문
• 중위순회 (Inorder Traversal)
  • "왼쪽 자식 → 부모 → 오른쪽 자식" 순서로 방문
• 후위순회 (Postorder Traversal)
  • "왼쪽 자식 → 오른쪽 자식 → 부모" 순서로 방문

각 순회 방법은 재귀(DFS) 를 통해 간단하게 구현할 수 있다.
각 노드를 방문하는 시점(순서)만 달라질 뿐,
기본 구조는 "왼쪽 서브트리 → 오른쪽 서브트리"로 이동하는 방식은 동일하다.

---

💻 코드 구현 (Java)

1️⃣ 전체 코드

package partRecursiveTreeGraph;

class Node {
	int data;
	Node lt, rt;
	public Node(int val) {
		data = val;
		lt = rt = null;
	}
}

public class Problem5 {
	Node root;

	public void DFS(Node root) {
		if (root == null) return;
		else {
			// System.out.print(root.data + " "); // 전위순회
			DFS(root.lt);
			// System.out.print(root.data + " "); // 중위순회
			DFS(root.rt);
			System.out.print(root.data + " "); // 후위순회
		}
	}

	public static void main(String[] args) {
		Problem5 tree = new Problem5();
		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); // 현재는 후위순회 출력
	}
}

---

📖 코드 설명

트리 구성

• Node 클래스를 통해 트리 노드를 정의한다.
• 각 노드는 data 값과 lt, rt (left, right) 두 개의 자식 노드를 가진다.
• Problem5 클래스의 main() 메서드에서 트리를 수동으로 구성한다.

DFS 함수

• 현재 노드가 null이면 재귀를 종료한다.
• 순회의 종류에 따라 System.out.print(root.data)를 출력하는 위치를 다르게 배치한다.

순회 종류출력 위치

• 전위순회 : DFS(root.lt) 호출 전에 출력
• 중위순회 : DFS(root.lt) 호출 후, DFS(root.rt) 호출 전에 출력
• 후위순회 : DFS(root.rt) 호출 후 출력

---

⏳ 시간 복잡도 분석

• 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(N)이다.
• 여기서 N은 트리의 노드 개수이다.

---

🧠 핵심 정리

• 전위순회: 부모 → 왼쪽 → 오른쪽
• 중위순회: 왼쪽 → 부모 → 오른쪽
• 후위순회: 왼쪽 → 오른쪽 → 부모
• 각각의 차이는 print 위치만 다르고, 기본적인 재귀 구조는 동일하다.
• 세 순회 모두 시간 복잡도는 O(N)으로 동일하다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

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