[Java] 트리(Tree) 자료구조 개념 정리

트리란?

계층적 구조를 표현하는 비선형 자료구조

예시
1. 회사 조직도
2. 가족 관계도 등

---

트리 용어 정리

1. 노드(Node) : 트리의 각 원소
2. 엣지(Edge) : 노드를 연결하는 선, 간선
3. 루트(Root) : 최상위 노드
4. 부모(Parent) : 바로 위에 연결된 노드
5. 자식(Child) : 바로 아래에 연결된 노드
6. 형제(Sibling) : 같은 부모를 가진 노드
7. 리프(Leaf) : 자식이 없는 노드
8. 내부 노드(Internal Node) : 자식이 있는 노드
9. 깊이(Depth) : 루트에서 해당 노드까지의 엣지 수
   • ex) A의 깊이 = 0, B의 깊이 = 1, D의 깊이 = 2
10. 레벨(Level) : 깊이와 동일하게 쓰이거나 깊이 + 1로 쓰임
11. 높이(Height) : 트리 전체의 깊이 최댓값
12. 서브트리(Subtree) : 특정 노드를 루트로 하는 트리

---

트리 직접 구현해보기

아래 트리 구조를 코드로 구현하고 출력해보자.

        1
      / | \
     2  3  4
    / \    |
   5  6    7

코드

import java.util.ArrayList;
import java.util.List;

public class TreeConceptPractice {

    static class Tree {
        int data;
        List<Tree> children;

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

        void addChild(Tree child) { this.children.add(child); }
    }

    static void printTree(Tree node, String prefix) {
        if (node == null) return;
        System.out.println(prefix + node.data);
        for (Tree child : node.children) {
            printTree(child, prefix + "    ");
        }
    }

    static void main(String[] args) {
        Tree root = new Tree(1);
        Tree n2 = new Tree(2);
        Tree n3 = new Tree(3);
        Tree n4 = new Tree(4);
        Tree n5 = new Tree(5);
        Tree n6 = new Tree(6);
        Tree n7 = new Tree(7);

        root.addChild(n2);
        root.addChild(n3);
        root.addChild(n4);
        n2.addChild(n5);
        n2.addChild(n6);
        n4.addChild(n7);

        printTree(root, "");
    }
}

출력

1
    2
        5
        6
    3
    4
        7

동작 원리

printTree(root, "")가 호출되면 "" + 1이 출력된다.
이후 반복문으로 루트(1)의 자식들을 순서대로 순회하는데, 각 자식마다 재귀함수가 실행된다.

1의 자식은 2, 3, 4 순서로 처리되며, 2가 넘어가면 2의 자식인 5, 6이 먼저 출력된다.
2가 끝나면 3, 그다음 4와 4의 자식인 7 순서로 출력된다.