[Java] 자료구조 - 트리(Tree) 만들기

1. 트리란

 

그래프는 정점과 간선으로 이루어져 있습니다.

정점들이 간선으로 연결되어 있는 그래프를 연결 그래프라고 합니다.

만약 한 정점에서 출발해 다시 자기 자신으로 돌아올 수 있는 경로가 있다면 사이클이 존재한다고 합니다.

트리는 사이클이 없는 연결 그래프입니다.

 

위 그림과 같이 트리는 자료를 계층적으로 표현하고자 할 때 사용됩니다. 각 노드는 상위 노드와 연결되어 있고, 부모-자식 관계를 가지며 같은 레벨에 있는 노드들은 형제라고 부릅니다. 자식이 최대 2명인 트리를 이진 트리라고 하며, 이진 트리가 가장 기본적인 트리의 형태라고 할 수 있습니다.

 

2. Java로 이진 트리 구현하기

 

트리에서 하나의 노드는 하나의 데이터 공간과, 왼쪽 자식에 대한 링크, 오른쪽 자식에 대한 링크를 가집니다.

TreeNode 클래스는 노드의 구조를 설계해줍니다.

class TreeNode {
    private int data;
    private TreeNode leftChild;
    private TreeNode rightChild;

    public TreeNode(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    public void setData(int data) {
        this.data = data;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }
}

 

이제 트리를 만들어봅니다.

먼저 최상위 노드인 root를 만들어 1을 저장한 뒤, 왼쪽 자식과 오른쪽 자식으로 새로운 트리노드 객체를 생성하여 저장합니다.

앞으로는 root를 시작점으로 해서 트리를 탐색할 수 있습니다.

root의 자식들에게 자식 노드를 추가해주면, 위 그림과 같은 트리가 완성됩니다.

TreeNode root = new TreeNode(1);
root.setLeftChild(new TreeNode(2));
root.setRightChild(new TreeNode(3));

root.getLeftChild().setLeftChild(new TreeNode(4));
root.getLeftChild().setRightChild(new TreeNode(5));
root.getRightChild().setLeftChild(new TreeNode(6));