[Data Structure] 트리

트리란

노드와 노드들을 이어주는 엣지로 이루어진 자료구조이다. 

그래프의 일종이다. 

 

트리의 특징

하나의 루트 노드를 가지며 부모 노드는 0개 이상의 자식 노드를 갖는다.

트리에는 사이클이 존재할 수 없다. 만약 사이클이 존재한다면 이는 트리가 아니라 그래프이다.

루트에서 어떤 노드로 가는 경우는 오직 하나이다.

 

트리 순회 방식

전위 순회

각 루트를 순차적으로 먼저 방문하는 방식이다. 

루트 → 왼쪽 자식 →  오른쪽 자식

1 2 4 8 9 5 10 11 3 6 13 7 14

 

중위 순회

왼쪽 하위 트리를 방문 후 루트를 방문하는 방식이다.

왼쪽 자식 → 루트 → 오른쪽 자식

8 9 4 10 11 5 2 13 6 14 7 3 1

 

후위 순회

왼쪽 하위 트리와 오른쪽 하위 트리를 방문 후 루트를 방문하는 방식이다.

왼쪽 자식 → 오른쪽 자식 → 루트

8 9 4 10 11 5 2 13 6 14 7 3 1

 

레벨 순회

루트부터 계층 별로 방문하는 방식이다.

1 2 3 4 5 6 7 8 9 10 11 13 14