트레버스(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

---

결론

트레버스 알고리즘은 트리 및 그래프 데이터 구조를 순차적으로 탐색할 수 있게 해주는 중요한 기법입니다. 위에서 설명한 전위, 중위, 후위, 레벨 순회는 트리 순회에서 가장 많이 사용되는 방법입니다. 이러한 순회 방법을 통해 데이터를 효율적으로 처리하고, 트리의 구조를 잘 활용할 수 있습니다.