[자료구조] 트리(Tree)

트리

• 트리는 값을 가진 노드와 이 노드들을 연결해주는 간선(Edge)으로 이루어져있음
• 그림 상 데이터 1을 가진 노드가 루트(Root) 노드
• 모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부름
  
  

트리의 특징

• 트리에는 사이클이 존재할 수 없음 (만약 사이클이 만들어진다면, 그것은 트리가 아니고 그래프)
• 모든 노드는 자료형으로 표현이 가능
• 루트에서 한 노드로 가는 경로는 유일한 경로 뿐
• 노드의 개수가 N개면, 간선은 N-1개를 가짐
  
  

트리 순회 방식

1. 전위 순회(pre-order)

• 각 루트(Root)를 순차적으로 먼저 방문하는 방식
• (Root → 왼쪽 자식 → 오른쪽 자식)1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14

 

2. 중위 순회(in-order)

• 왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식
• (왼쪽 자식 → Root → 오른쪽 자식)8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 → 14 → 7

 

3. 후위 순회(post-order)

• 왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문하는 방식
• (왼쪽 자식 → 오른쪽 자식 → Root)8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1

 

4. 레벨 순회(level-order)

• 루트(Root)부터 계층 별로 방문하는 방식1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14

    public class Tree<T> {
        private Node<T> root;

        public Tree(T rootData) {
            root = new Node<T>();
            root.data = rootData;
            root.children = new ArrayList<Node<T>>();
        }

        public static class Node<T> {
            private T data;
            private Node<T> parent;
            private List<Node<T>> children;
        }
    }