[자료구조] 노드로 이루어진 트리 구현하기 (By Java)

오늘은 자료구조의 트리를 알고리즘 대회나 문제에서 풀기 쉽게 한 번에 구현하는 방법에 대해서 알아볼 것이다.

트리 자료구조

트리 자료구조는 지난 트리 자료 구조(1)-기본 트리 용어 및 개념 파트에서 설명했으므로 생략하고 바로 구현을 해보도록 하겠다.

트리 자료구조의 핵심

트리 자료구조에서의 핵심은 바로 노드이다.

여기서 노드란 트리 자료구조에 데이터를 저장하고 있는 하나 하나의 원소인 셈이다.

노드는 크게 Data Field와 Link Field로 나뉘어져 있다.

저기 위에서 보면 각각의 숫자에 해당하는 부분이 Data Field이며 연결되어 있는 간선은 Link Field이다.

그렇다면 위에서 말 했듯이 노드는 Data Field와 Link Field가 합쳐진 구조이므로 이를 그림으로 그린다면 아래와 같은 그림의 형상을 하고 있을 것이다.

그럼 위에 존재하는 트리를 노드로 도식화 하여 보여준다면 다음과 같은 형태가 나타나게 된다.

링크 필드에서는 다음 노드를 가리킬 수 있는 주소가 담겨 있는 형태이다.

자바로 구현하기

이제 자바로 구현해보자.

구현 단계는 2단계로

1. 노드 구현하기
2. 노드 연결관계 추가하기

class MyNode {
    int data;
    MyNode left;
    MyNode right;
}

class Tree {
    public MyNode root;

    public void setRoot(MyNode node) {
        this.root = root;
    }

    public MyNode getRoot() {
        return root;
    }

    public MyNode addNode(MyNode left, int data, MyNode right){
        MyNode node = new MyNode();
        node.data = data;
        node.left = left;
        node.right = right;

        return node;
    }
}