[java] 자바의 트리 순회(Tree Traversal) 알고리즘 이해하기

14 Dec 2023

java

1. 소개

트리 순회(Tree Traversal)는 트리 구조에서 노드를 방문하고 처리하는 방법을 말합니다. 이 포스트에서는 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder) 알고리즘을 자바로 구현하는 방법을 다룰 것입니다.

트리 순회를 위해서는 트리의 노드 구조 및 순회 알고리즘 이해가 필요합니다.

2. 전위 순회(Preorder Traversal)

전위 순회는 루트 노드를 가장 먼저 방문한 후에 왼쪽 서브트리를 순회하고, 그 다음에 오른쪽 서브트리를 순회하는 방식입니다.

다음은 전위 순회 알고리즘의 자바 구현 예시입니다.

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    void preorderTraversal(Node node) {
        if (node != null) {
            System.out.println(node.data + " ");
            preorderTraversal(node.left);
            preorderTraversal(node.right);
        }
    }

    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);

        System.out.println("Preorder traversal of binary tree is ");
        tree.preorderTraversal(tree.root);
    }
}

3. 중위 순회(Inorder Traversal)

중위 순회는 왼쪽 서브트리를 순회한 후에 루트 노드를 방문하고, 그 다음에 오른쪽 서브트리를 순회하는 방식입니다.

다음은 중위 순회 알고리즘의 자바 구현 예시입니다.

class BinaryTree {
    // ... 이전 예시와 동일한 내용

    void inorderTraversal(Node node) {
        if (node != null) {
            inorderTraversal(node.left);
            System.out.println(node.data + " ");
            inorderTraversal(node.right);
        }
    }

    public static void main(String[] args) {
        // ... 이전 예시와 동일한 내용

        System.out.println("\nInorder traversal of binary tree is ");
        tree.inorderTraversal(tree.root);
    }
}

4. 후위 순회(Postorder Traversal)

후위 순회는 왼쪽 서브트리를 순회한 후에 오른쪽 서브트리를 순회하고, 마지막으로 루트 노드를 방문하는 방식입니다.

다음은 후위 순회 알고리즘의 자바 구현 예시입니다.

class BinaryTree {
    // ... 이전 예시와 동일한 내용

    void postorderTraversal(Node node) {
        if (node != null) {
            postorderTraversal(node.left);
            postorderTraversal(node.right);
            System.out.println(node.data + " ");
        }
    }

    public static void main(String[] args) {
        // ... 이전 예시와 동일한 내용

        System.out.println("\nPostorder traversal of binary tree is ");
        tree.postorderTraversal(tree.root);
    }
}

결론

이번 포스트에서는 전위 순회, 중위 순회, 후위 순회 알고리즘을 자바로 구현하는 방법을 살펴보았습니다. 트리 순회는 많은 자료 구조 및 알고리즘에서 활용되므로, 이러한 순회 방법을 이해하고 활용하는 것은 매우 중요합니다.

References

GeeksforGeeks: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

목차

1. 소개

2. 전위 순회(Preorder Traversal)

3. 중위 순회(Inorder Traversal)

4. 후위 순회(Postorder Traversal)

결론

References