[Tree] 트리란?

😘트리 : Node와 Edge로 이루어진 자료구조

트리는 값을 가진 노드와 이 노드들을 연결해주는 간선으로 이루어져있다.

그림 상 데이터 1을 가진 노드가 루트(Root)노드다.

모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부른다.

😁 트리의 특징

1. 트리에는 사이클이 존재할 수 없다. (만약 사이클이 생기면 그것은 그래프다)

2. 모든 노드는 자료형으로 표현이 가능하다.

3. 루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.

4. 노드의 개수가 N개면, 간선은 N-1개를 가진다.

😍 트리 순회 방식

트리를 순회하는 방식은 총 4가지가 있다. 위의 그림을 예시로 진행해보자.

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

 

[참고 자료]

https://gyoogle.dev/blog/computer-science/data-structure/Tree.html