[GDG - 스터디] 이진 트리를 입력받아 순회 결과 출력하기

이진 트리 순회

이진 트리 순회 ?

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

주요 순회 방식

• 전위 순회(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

1. 각 노드는 data, left, right를 가진다.
2. 트리를 구성하기 위해 addNode 메서드를 사용한다
3. 입력에 따라 각 노드를 생성하거나 기존 노드를 가져온다.
4. 순회 결과를 StringBuilder에 저장하며, 전위, 중위, 후위 순회를 각각 구현한다.
5. 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