Java로 구현하는 이진 트리 중위 순회(Inorder Traversal) 방법

이 글에서는 Java를 사용하여 이진 트리의 중위 순회(Inorder Traversal)를 수행하는 방법을 알아봅니다. 중위 순회는 각 노드를 왼쪽 하위 트리와 오른쪽 하위 트리 사이에서 처리하는 순회 방식입니다. 쉽게 말해 왼쪽 하위 트리 → 노드 → 오른쪽 하위 트리 순서로 방문합니다.

중위 순회는 이진 탐색 트리(BST)에서 노드를 오름차순으로 정렬된 순서로 출력할 수 있다는 장점이 있어, 실무에서도 널리 활용됩니다.

아래는 실행 결과 예시입니다.

입력

프로그램 실행

출력 결과

tree_object의 중위 순회 결과:
5->12->6->1->9->

알고리즘

Step 1 - 시작
Step 2 - 데이터 명세가 정의된 클래스를 사전에 선언한다.
Step 3 - 해당 클래스의 새 인스턴스를 생성한다.
Step 4 - 인스턴스를 적절한 값으로 초기화한다.
Step 5 - 중위 순회를 수행하는 메서드를 호출한다.
Step 6 - 결과를 출력한다.
Step 7 - 종료

예제 1: 재귀(Recursive) 방식

첫 번째 예제는 재귀 호출을 활용한 중위 순회 구현입니다. 코드가 간결하고 직관적이어서 가장 널리 사용되는 방식입니다.

class Node {
    int item;
    Node left_node, right_node;
    public Node(int key) {
        item = key;
        left_node = right_node = null;
    }
}
public class Tree {
    Node root;
    Tree() {
        root = null;
    }
    void inOrder(Node node) {
        if (node == null)
            return;
        inOrder(node.left_node);
        System.out.print(node.item + "->");
        inOrder(node.right_node);
    }
    public static void main(String[] args) {
        Tree tree_object = new Tree();
        System.out.println("A tree_object object is defined: ");
        tree_object.root = new Node(1);
        tree_object.root.left_node = new Node(12);
        tree_object.root.right_node = new Node(9);
        tree_object.root.left_node.left_node = new Node(5);
        tree_object.root.left_node.right_node = new Node(6);
        System.out.println("The In-Order traversal of the tree_object is: ");
        tree_object.inOrder(tree_object.root);
    }
}

출력 결과

A tree_object object is defined:
The In-Order traversal of the tree_object is:
5->12->6->1->9->

예제 2: 비재귀(반복문 + 스택) 방식

두 번째 예제는 재귀 호출 없이 Stack 자료구조를 이용해 반복문으로 중위 순회를 구현한 것입니다. 트리의 깊이가 매우 깊은 경우 재귀 방식은 스택 오버플로우가 발생할 수 있으므로, 이러한 반복 방식이 유용합니다.

import java.util.Stack;
class Node {
    int data;
    Node left_node, right_node;
    public Node(int item) {
        data = item;
        left_node = right_node = null;
    }
}
class tree {
    Node root;
    void inorder() {
        if (root == null)
            return;
        Stack<Node> temp_stack = new Stack<Node>();
        Node current_node = root;
        while (current_node != null || temp_stack.size() > 0) {
            while (current_node != null) {
                temp_stack.push(current_node);
                current_node = current_node.left_node;
            }
            current_node = temp_stack.pop();
            System.out.print(current_node.data + " ");
            current_node = current_node.right_node;
        }
    }
    public static void main(String args[]) {
        tree tree = new tree();
        System.out.println("A tree_object object is defined: ");
        tree.root = new Node(1);
        tree.root.left_node = new Node(2);
        tree.root.right_node = new Node(3);
        tree.root.left_node.left_node = new Node(4);
        tree.root.left_node.right_node = new Node(5);
        System.out.println("The In-Order traversal of the tree_object is: ");
        tree.inorder();
    }
}

출력 결과

A tree_object object is defined:
The In-Order traversal of the tree_object is:
4 2 5 1 3

정리

중위 순회는 왼쪽 → 루트 → 오른쪽 순서로 노드를 방문하며, 재귀 방식과 스택을 활용한 반복 방식 두 가지로 구현할 수 있습니다. 재귀 방식은 코드가 단순하고 이해하기 쉬운 반면, 반복 방식은 깊은 트리에서도 안정적으로 동작한다는 점이 차이입니다. 상황에 맞게 적절한 방식을 선택하여 사용하시기 바랍니다.