이진 트리 순회

이진 트리 순회 ?

• 이진 트리 순회는 트리 구조에서 각 노드를 방문하는 방법을 의미한다.

주요 순회 방식

• 전위 순회(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)에서 시작하여, 주어진 데이터를 직접 재귀적으로 탐색하며 삽입하는 방식.