Java에서 트리(Tree) 자료구조 마스터하기

트리(Tree)란?

• 트리는 계층적 구조를 가진 비선형 자료구조로, 노드(Node)들이 부모-자식 관계로 연결된 구조입니다.
• Java에서 트리 구조는 주로 사용자 정의 클래스를 통해 구현되며, TreeSet과 TreeMap 같은 컬렉션 프레임워크를 통해서도 활용됩니다.

Java에서 트리 구현의 기본

• 사용자 정의 트리 노드 클래스를 만들어 기본적인 트리 구조를 구현해봅시다.

 

사용자 정의 트리 노드 클래스

• 트리의 기본 구성 요소인 노드를 정의하는 클래스입니다.

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

 

 

트리 생성 및 요소 추가

• 간단한 트리를 생성하고 요소를 추가합니다.

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

 

트리의 순회

• 트리의 데이터를 탐색하는 데에는 여러 순회 방법이 있습니다: 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder).

전위 순회(Preorder Traversal)

• 노드 방문 -> 왼쪽 서브트리 순회 -> 오른쪽 서브트리 순회.

void preorderTraversal(TreeNode node) {
    if (node != null) {
        System.out.print(node.data + " "); // 노드 방문
        preorderTraversal(node.left);      // 왼쪽 서브트리 순회
        preorderTraversal(node.right);     // 오른쪽 서브트리 순회
    }
}

 

 

중위 순회(Inorder Traversal)

• 왼쪽 서브트리 순회 -> 노드 방문 -> 오른쪽 서브트리 순회.

void inorderTraversal(TreeNode node) {
    if (node != null) {
        inorderTraversal(node.left);       // 왼쪽 서브트리 순회
        System.out.print(node.data + " "); // 노드 방문
        inorderTraversal(node.right);      // 오른쪽 서브트리 순회
    }
}

 

 

후위 순회(Postorder Traversal)

• 왼쪽 서브트리 순회 -> 오른쪽 서브트리 순회 -> 노드 방문.

void postorderTraversal(TreeNode node) {
    if (node != null) {
        postorderTraversal(node.left);     // 왼쪽 서브트리 순회
        postorderTraversal(node.right);    // 오른쪽 서브트리 순회
        System.out.print(node.data + " "); // 노드 방문
    }
}

 

 

Java에서 제공하는 트리 기반 컬렉션

• TreeSet: 정렬된 순서로 요소를 저장하는 세트.
• TreeMap: 키-값 쌍을 이진 탐색 트리 구조로 저장하는 맵.

트리의 활용

• 트리 구조는 데이터베이스 시스템, 파일 시스템, 정렬 및 탐색 알고리즘 등에서 널리 사용됩니다.

결론

• Java에서 트리 자료구조는 데이터를 계층적으로 관리하는 데 매우 효과적입니다.
• 사용자 정의 트리 구현과 표준 라이브러리의 트리 기반 컬렉션 사용은 Java 프로그래밍의 중요한 측면입니다.
• 전위, 중위, 후위 순회는 트리 구조의 데이터를 탐색하고 처리하는 데 사용되는 기본적인 방법입니다.