[자료구조] -트리

1. 트리

• Node와 Edge로 이루어진 자료구조
• 트리는 값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)로 이루어져있다.
• 그림 상 데이터 1을 가진 노드가 루트(Root) 노드다
• 모든 노드들은 0개 이상의 자식노드를 갖고 있으며 부모-자식 관계로 불린다.

2. 트리 특징

• 트리에는 사이클이 존재 할 수 없다.
• 모든 노드는 자료형으로 표현이 가능하다.
• 루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.
• 노드의 개수가 N개면, 간선은 N-1 개를 가진다.

3. 트리 순회 방식

• 전위 순회
  각 루트를 순차적으로 먼저 방문하는 방식
• 중위 순회
  왼쪽 하위 트리를 방문 후 루트를 방문하는 방식
• 후위 순회
  왼쪽 하위 트리부터 하위를 모두 방문 후 루트를 방문하는 방식이다
• 레벨 순회
  루트부터 계층 별로 방문하는 방식이다.