Colin's Blog
[java] 트리 구현 방법

트리는 계층적인 구조를 나타내는 비선형 자료구조로, 많은 문제에서 유용하게 활용됩니다. Java로 트리를 구현하는 방법에는 여러 가지가 있지만, 이번 글에서는 가장 대표적인 두 가지 방법을 소개하겠습니다.

1. 링크드 리스트를 이용한 트리 구현

링크드 리스트를 이용하여 트리를 구현하는 방법은 간단하면서도 직관적입니다. 링크드 리스트의 각 노드는 자신의 자식 노드들을 참조하는 포인터를 갖고 있습니다.

class Node {
    int data;
    Node parent;
    List<Node> children;

    public Node(int data) {
        this.data = data;
        this.children = new ArrayList<>();
    }
}

위의 코드에서 Node 클래스는 트리의 노드를 나타내며, parent 변수는 부모 노드를 가리키는 포인터입니다. children 변수는 해당 노드의 자식 노드들을 저장하는 리스트입니다.

이제 각 노드를 연결하여 트리를 만들 수 있습니다.

Node root = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);

root.children.add(node2);
root.children.add(node3);

Node node4 = new Node(4);
Node node5 = new Node(5);

node2.children.add(node4);
node2.children.add(node5);

위의 코드는 다음과 같은 트리를 생성합니다.

      1
     / \
    2   3
   / \
  4   5

2. 배열을 이용한 트리 구현

배열을 이용하여 트리를 구현하는 방법은 메모리를 절약할 수 있으며, 인덱스를 이용하여 노드 간의 관계를 나타낼 수 있습니다.

class Tree {
    int[] tree;

    public Tree(int size) {
        this.tree = new int[size];
    }

    public void setRoot(int data) {
        tree[0] = data;
    }

    public void setLeftChild(int parentIndex, int data) {
        int childIndex = parentIndex * 2 + 1;
        tree[childIndex] = data;
    }

    public void setRightChild(int parentIndex, int data) {
        int childIndex = parentIndex * 2 + 2;
        tree[childIndex] = data;
    }
}

위의 코드에서 Tree 클래스는 배열을 이용한 트리를 나타냅니다. tree 배열은 트리의 노드를 저장하며, 각 노드의 인덱스는 다음과 같이 계산됩니다.

setRoot, setLeftChild, setRightChild 메서드를 사용하여 트리의 구조를 설정할 수 있습니다.

Tree tree = new Tree(7);
tree.setRoot(1);
tree.setLeftChild(0, 2);
tree.setRightChild(0, 3);
tree.setLeftChild(1, 4);
tree.setRightChild(1, 5);

위의 코드는 위에서 소개한 링크드 리스트를 이용한 트리와 같은 트리를 생성합니다.

결론

Java에서 트리를 구현하는 방법에는 여러 가지가 있지만, 링크드 리스트와 배열을 이용한 방법은 대표적인 방법입니다. 어떤 방법을 선택하더라도 트리의 자료구조와 알고리즘을 잘 이해하고 활용할 수 있다면 다양한 문제를 해결할 수 있을 것입니다.

참고 문헌:

© 2018 Colin. All rights reserved.