Algorithm
[GDG - 스터디] 이진 트리를 입력받아 순회 결과 출력하기
Uykm
2024. 11. 25. 15:05
이진 트리 순회
이진 트리 순회 ?
- 이진 트리 순회는 트리 구조에서 각 노드를 방문하는 방법을 의미한다.
주요 순회 방식
- 전위 순회(Preorder Traversal) : 루트 → 왼쪽 자식 → 오른쪽 자식
- 현재 노드를 먼저 방문한 뒤, 왼쪽 서브트리를 순회하고 오른쪽 서브트리를 순회한다.
- 트리 복사, 표현식 트리를 평가하는 경우에 사용된다.
- 중위 순회(Inorder Traversal) : 왼쪽 자식 → 루트 → 오른쪽 자식
- 왼쪽 서브트리를 먼저 순회한 뒤 현재 노드를 방문하고, 오른쪽 서브트리를 순회한다.
- 정렬된 순서로 출력하는 경우(특히 이진 탐색 트리에서 유용)에 사용된다.
- 후위 순회(Postorder Traversal) : 루트 → 왼쪽 자식 → 오른쪽 자식
- 현재 노드를 먼저 방문한 뒤, 왼쪽 서브트리를 순회하고 오른쪽 서브트리를 순회한다.
- 트리 삭제, 표현식 트리의 연산을 수행하는 경우세 사용된다.
import java.util.*; public class Main { public static void main(String[] args) { BinaryTree tree = new BinaryTree(); // 노드 삽입 tree.insert(50, null); // 루트 노드 tree.insert(30, 50); // 30은 50의 자식 tree.insert(20, 30); // 20은 30의 자식 tree.insert(40, 30); // 40은 30의 자식 tree.insert(70, 50); // 70은 50의 자식 tree.insert(60, 70); // 60은 70의 자식 tree.insert(80, 70); // 80은 70의 자식 // 순회 결과 출력 System.out.print("전위 순회: "); tree.preorder(tree.getRoot()); System.out.println(); System.out.print("중위 순회: "); tree.inorder(tree.getRoot()); System.out.println(); System.out.print("후위 순회: "); tree.postorder(tree.getRoot()); System.out.println(); } } class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } class BinaryTree { private Node root; // 루트 노드 private Map<Integer, Node> nodeMap; // 노드 관리용 Map BinaryTree() { nodeMap = new HashMap<>(); } // 노드 삽입 public void insert(int data, Integer parentData) { Node newNode = new Node(data); // 새로운 노드 생성 nodeMap.put(data, newNode); // Map에 노드 저장 if (parentData == null) { // 루트 노드 설정 root = newNode; return; } Node parentNode = nodeMap.get(parentData); // 부모 노드 참조 if (parentNode.left == null) { parentNode.left = newNode; // 왼쪽 자식 설정 } else { parentNode.right = newNode; // 오른쪽 자식 설정 } } // 루트 노드 반환 public Node getRoot() { return root; } // 전위 순회 public void preorder(Node node) { if (node == null) return; System.out.print(node.data + " "); // 루트 방문 preorder(node.left); // 왼쪽 서브트리 preorder(node.right); // 오른쪽 서브트리 } // 중위 순회 public void inorder(Node node) { if (node == null) return; inorder(node.left); // 왼쪽 서브트리 System.out.print(node.data + " "); // 루트 방문 inorder(node.right); // 오른쪽 서브트리 } // 후위 순회 public void postorder(Node node) { if (node == null) return; postorder(node.left); // 왼쪽 서브트리 postorder(node.right); // 오른쪽 서브트리 System.out.print(node.data + " "); // 루트 방문 } }
문제: 트리 순회 (백준 1991)
문제 링크
알고리즘 [접근 방법]
- 입력받은 이진 트리를 저장하고, 각각의 순회에 대한 결과를 출력해주면 된다. → 두 가지 방식이 있다 !
- 노드를 Map<Character, Node>로 관리하여, 노드 탐색 없이 빠르게 참조 및 삽입하는 방식.
- 루트 노드(head)에서 시작하여, 주어진 데이터를 직접 재귀적으로 탐색하며 삽입하는 방식.
해결 코드 0
- 각 노드는 data, left, right를 가진다.
- 트리를 구성하기 위해 addNode 메서드를 사용한다
- 입력에 따라 각 노드를 생성하거나 기존 노드를 가져온다.
- 순회 결과를 StringBuilder에 저장하며, 전위, 중위, 후위 순회를 각각 구현한다.
- Map을 사용하여 트리를 동적으로 구성했다.
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 노드 개수
BinaryTree tree = new BinaryTree();
// 입력 받아 트리 구성
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
char data = st.nextToken().charAt(0);
char left = st.nextToken().charAt(0);
char right = st.nextToken().charAt(0);
tree.addNode(data, left, right);
}
// 루트 노드
Node root = tree.nodes.get('A');
// 순회 결과 출력
StringBuilder sb = new StringBuilder();
// 전위 순회
tree.preorder(root, sb);
System.out.println(sb.toString());
sb.setLength(0); // StringBuilder 초기화
// 중위 순회
tree.inorder(root, sb);
System.out.println(sb.toString());
sb.setLength(0); // StringBuilder 초기화
// 후위 순회
tree.postorder(root, sb);
System.out.println(sb.toString());
}
static class Node {
char data;
Node left, right;
Node(char data) {
this.data = data;
left = right = null;
}
}
static class BinaryTree {
Map<Character, Node> nodes = new HashMap<>(); // 노드 저장
// 트리 구성
void addNode(char data, char left, char right) {
Node node = nodes.getOrDefault(data, new Node(data));
nodes.put(data, node);
if (left != '.') { // 왼쪽 자식이 있는 경우
Node leftNode = new Node(left);
nodes.put(left, leftNode);
node.left = leftNode;
}
if (right != '.') { // 오른쪽 자식이 있는 경우
Node rightNode = new Node(right);
nodes.put(right, rightNode);
node.right = rightNode;
}
}
// 전위 순회
void preorder(Node node, StringBuilder sb) {
if (node == null) return;
sb.append(node.data); // 루트 방문
preorder(node.left, sb); // 왼쪽 서브트리
preorder(node.right, sb); // 오른쪽 서브트리
}
// 중위 순회
void inorder(Node node, StringBuilder sb) {
if (node == null) return;
inorder(node.left, sb); // 왼쪽 서브트리
sb.append(node.data); // 루트 방문
inorder(node.right, sb); // 오른쪽 서브트리
}
// 후위 순회
void postorder(Node node, StringBuilder sb) {
if (node == null) return;
postorder(node.left, sb); // 왼쪽 서브트리
postorder(node.right, sb); // 오른쪽 서브트리
sb.append(node.data); // 루트 방문
}
}
}
해결 코드 1
- 아래 코드는 노드를 재귀적으로 탐색하며 트리에 삽입하도록 한 코드이다 !
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine()); // 노드 개수
BinaryTree tree = new BinaryTree();
// 입력 받아 트리 구성
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
char data = st.nextToken().charAt(0);
char left = st.nextToken().charAt(0);
char right = st.nextToken().charAt(0);
tree.addNode(tree.root, data, left, right);
}
// 순회 결과 출력
StringBuilder sb = new StringBuilder();
// 전위 순회
tree.preorder(tree.root, sb);
System.out.println(sb.toString());
sb.setLength(0); // StringBuilder 초기화
// 중위 순회
tree.inorder(tree.root, sb);
System.out.println(sb.toString());
sb.setLength(0); // StringBuilder 초기화
// 후위 순회
tree.postorder(tree.root, sb);
System.out.println(sb.toString());
}
static class Node {
char data;
Node left, right;
Node(char data) {
this.data = data;
left = right = null;
}
}
static class BinaryTree {
Node root;
// 트리 구성 (재귀 탐색 방식)
void addNode(Node current, char data, char left, char right) {
if (root == null) { // 루트가 없는 경우 루트 생성
root = new Node(data);
if (left != '.') root.left = new Node(left);
if (right != '.') root.right = new Node(right);
return;
}
// 현재 노드가 삽입할 노드와 동일하면 자식 노드 추가
if (current.data == data) {
if (left != '.') current.left = new Node(left);
if (right != '.') current.right = new Node(right);
return;
}
// 왼쪽 서브트리를 탐색
if (current.left != null) addNode(current.left, data, left, right);
// 오른쪽 서브트리를 탐색
if (current.right != null) addNode(current.right, data, left, right);
}
// 전위 순회
void preorder(Node node, StringBuilder sb) {
if (node == null) return;
sb.append(node.data); // 루트 방문
preorder(node.left, sb); // 왼쪽 서브트리
preorder(node.right, sb); // 오른쪽 서브트리
}
// 중위 순회
void inorder(Node node, StringBuilder sb) {
if (node == null) return;
inorder(node.left, sb); // 왼쪽 서브트리
sb.append(node.data); // 루트 방문
inorder(node.right, sb); // 오른쪽 서브트리
}
// 후위 순회
void postorder(Node node, StringBuilder sb) {
if (node == null) return;
postorder(node.left, sb); // 왼쪽 서브트리
postorder(node.right, sb); // 오른쪽 서브트리
sb.append(node.data); // 루트 방문
}
}
}
정리
- Map은 트리의 동적 구성에서 노드 관리의 효율성과 코드 간결성을 높인다 ! → 특히 중복 노드 참조를 방지하며 빠르게 노드에 접근할 수 있다는 점에서 유용하다 !
https://thin-azimuth-2a9.notion.site/GDG-149f4ee21c0080338337c32099fe124c?pvs=4
GDG 스터디 - 이진 트리를 입력받아 순회 결과 출력하기 | Notion
개념
thin-azimuth-2a9.notion.site