트레버스(Traverse)
목차
트레버스(Traverse) 기본 개념
트레버스는 "순회"라는 의미로, 트리나 그래프 같은 자료 구조의 각 노드를 방문하는 방법을 말합니다. 트리에서 트레버스를 할 때는 다음과 같은 방식으로 트리 구조를 순회할 수 있습니다.
- 전위 순회 (Pre-order Traversal)
순서: 루트 → 왼쪽 → 오른쪽
주로 트리를 만들 때 사용됩니다.
- 중위 순회 (In-order Traversal)
순서: 왼쪽 → 루트 → 오른쪽
이 방식은 이진 검색 트리에서 유용하게 사용됩니다.
- 후위 순회 (Post-order Traversal)
순서: 왼쪽 → 오른쪽 → 루트
주로 트리의 삭제나 후처리 작업에 사용됩니다.
- 레벨 순회 (Level-order Traversal)
순서: 각 레벨을 차례대로 방문
큐를 사용하여 구현합니다.
트리 구조 예시
트리 구조는 일반적으로 부모 노드와 자식 노드로 연결된 자료구조입니다. 예를 들어, 아래와 같은 이진 트리를 생각해 봅시다:
1
/ \
2 3
/ \ / \
4 5 6 7
이진 트리에서 다양한 트레버스 방법을 적용할 수 있습니다.
1. 전위 순회 (Pre-order Traversal)
설명:
루트를 먼저 방문하고, 그다음 왼쪽 서브트리와 오른쪽 서브트리를 순차적으로 방문합니다.
순회 순서: 1 → 2 → 4 → 5 → 3 → 6 → 7
자바 코드 예시:
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
void preOrder(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " "); // 방문
preOrder(node.left); // 왼쪽 서브트리
preOrder(node.right); // 오른쪽 서브트리
}
}
public class Main {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.print("전위 순회: ");
tree.preOrder(tree.root);
}
}
출력:
전위 순회: 1 2 4 5 3 6 7
2. 중위 순회 (In-order Traversal)
설명:
왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문합니다. 이 방식은 이진 검색 트리에서 오름차순으로 값을 출력할 때 유용합니다.
순회 순서: 4 → 2 → 5 → 1 → 6 → 3 → 7
자바 코드 예시:
class BinaryTree {
Node root;
void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left); // 왼쪽 서브트리
System.out.print(node.data + " "); // 방문
inOrder(node.right); // 오른쪽 서브트리
}
}
public class Main {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.print("중위 순회: ");
tree.inOrder(tree.root);
}
}
출력:
중위 순회: 4 2 5 1 6 3 7
3. 후위 순회 (Post-order Traversal)
설명:
왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문합니다. 트리의 후처리 작업에 유용하게 사용됩니다.
순회 순서: 4 → 5 → 2 → 6 → 7 → 3 → 1
자바 코드 예시:
class BinaryTree {
Node root;
void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left); // 왼쪽 서브트리
postOrder(node.right); // 오른쪽 서브트리
System.out.print(node.data + " "); // 방문
}
}
public class Main {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.print("후위 순회: ");
tree.postOrder(tree.root);
}
}
출력:
후위 순회: 4 5 2 6 7 3 1
4. 레벨 순회 (Level-order Traversal)
레벨 순회는 트리의 각 레벨을 차례대로 방문하는 방법입니다. 이를 구현하려면 큐를 사용합니다. 큐에 각 레벨의 노드를 넣고, 큐에서 꺼내면서 순차적으로 트리를 탐색합니다.
자바 코드 예시:
import java.util.*;
class BinaryTree {
Node root;
void levelOrder(Node node) {
if (node == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(node);
while (!queue.isEmpty()) {
Node current = queue.poll();
System.out.print(current.data + " ");
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
}
}
public class Main {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.print("레벨 순회: ");
tree.levelOrder(tree.root);
}
}
출력:
레벨 순회: 1 2 3 4 5 6 7
결론
트레버스 알고리즘은 트리 및 그래프 데이터 구조를 순차적으로 탐색할 수 있게 해주는 중요한 기법입니다. 위에서 설명한 전위, 중위, 후위, 레벨 순회는 트리 순회에서 가장 많이 사용되는 방법입니다. 이러한 순회 방법을 통해 데이터를 효율적으로 처리하고, 트리의 구조를 잘 활용할 수 있습니다.
