JAVA의 Tree

자료구조 - 트리, 이진트리

트리는 부모-자식 관계의 노드들로 이루어지며 계층적인 구조를 나타내는 자료구조입니다.
운영체제의 파일시스템, HTML, XML 등을 다룰 때 사용하는 DOM, 데이터베이스 등 다양하게 활용되고 있습니다.
트리구조에서 중요한 것은 부모는 여러 자식을 가질 수 있지만 자식은 하나의 부모를 갖는다는 것입니다.
이진트리는 각 노드가 최대 2개의 자식을 가지는 트리를 말합니다.

위의 그림은 포화이진트리 구조입니다. 모든 노드가 2개의 자식을 갖기 때문입니다.
트리의 최상단 노드를 뿌리, 즉 루트(Root)라고 합니다. 
루트로부터 어떤 노드까지의 거리를 그 노드의 깊이(Depth)라 하고 
깊이가 같은 노드끼리의 집합을 레벨(Level)이라 합니다. 
같은 부모를 가진 노드들을 형제(Sibling) 노드라 합니다.

---

트리의 표현

트리를 표현하는 방법에는 배열 표현법과 링크 표현법이 있습니다. 
배열 표현법은 각 노드에 인덱스를 부여하여 배열에 저장하는 방법입니다.
링크 표현법은 다음 노드를 가리키는 포인터 변수를 이용하여 부모노드가 자식노드를 가리키는 방법입니다.

위의 그림은 이진트리를 배열 표현법으로 나타낸 것입니다.
트리의 순서가 배열의 인덱스가 되어 1번부터 차례로 값이 들어가게 됩니다.
배열 표기법은 트리 노드의 삽입 또는 삭제에 따라 배열의 크기를 동적으로 변경할 수 없다는 단점이 있습니다.
그리고 링크 표현법에 비해 트리의 구조를 한눈에 알아보기가 힘듭니다.

위의 그림은 이진트리를 링크 표현법으로 나타낸 것입니다.
각 노드는 왼쪽 자식을 가리키는 포인터, 오른쪽 자식을 가리키는 포인터, 데이터 영역을 가지게 됩니다.
만일 자식이 없다면 NULL로 표현됩니다.
링크 표현법은 트리 노드의 삽입 또는 삭제에 따라 크기를 동적으로 변경할 수 있지만
배열 표현법보다 코드가 복잡하다는 단점이 있습니다.

---

JAVA의 트리 구현

JAVA에서 제공하는 라이브러리를 사용하기 전에
부모-자식관계를 갖는 일반적인 트리를 구현해보겠습니다.

public class TreeNode<T> implements Iterable<TreeNode<T>>{
    private T data;
    private TreeNode<T> parent;
    private List<TreeNode<T>> children;
 
    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<TreeNode<T>>();
    }
 
    public TreeNode<T> addChild(T child) {
        TreeNode<T> childNode = new TreeNode<T>(child);
        childNode.parent = this;
        this.children.add(childNode);
        return childNode;
    }
 
    @Override
    public Iterator<TreeNode<T>> iterator() {
        // TODO Auto-generated method stub
        return null;
    }
}

우선 Iterable 인터페이스를 상속하여 TreeNode 타입을 갖도록 만들었습니다.
각 노드는 값이 저장되는 data 필드를 가지며 하나의 부모와 여러개의 자식 리스트를 가집니다.
자식 리스트는 링크드리스트(LinkedList)를 이용하여 구현하였습니다.

트리노드를 삽입하게 되면 우선 트리노드를 생성하고 
또 다른 자식을 가질 수 있도록 부모영역에 자신을 연결시켜줍니다.
마지막으로 자식 리스트에 추가해줍니다.

public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        TreeNode<String> root = new TreeNode<String>("root");
        {
            TreeNode<String> node1 = root.addChild("node1");
            TreeNode<String> node2 = root.addChild("node2");
            TreeNode<String> node3 = root.addChild("node3");
            {
                TreeNode<String> node4 = node1.addChild("node4");
                TreeNode<String> node5 = node1.addChild("node5");
                {
                    TreeNode<String> node6 = node3.addChild("node6");
                }
            }
        }
    }
}

이제 TreeNode 클래스를 메인에 적용시켜 보겠습니다.
제일 먼저 root 노드를 삽입하고 node1에 스트링 타입의 "node1", "node2", "node3" 데이터를 삽입합니다.
마찬가지로 "node4", "node5", "node6" 데이터를 삽입하였습니다.

삽입 결과는 위의 그림과 같습니다.
다음 포스팅을 통해 이진트리를 구현해보겠습니다.