트리

트리

• 자료구조의 일종
• 사이클이 없는 그래프
• 노드의 개수 V
• 간선의 개수 V-1

트리의 표현

• 그래프의 표현과 같은 방식으로 저장 가능 (인접 리스트)
• 트리의 모든 노드는 부모를 하나 또는 0개(루트) 만 가지기 때문에 부모만 저장하는 방식으로도 저장 가능
• 부모가 0개인 루트는 부모를 -1이나 0으로 처리함

트리의 순회

• 트리도 그래프이므로 DFS와 BFS를 사용할 수 있다.

• 트리에서만 사용할 수 있는 세 방법

• 프리오더 (전위 순회) -> DFS와 순서가 같다.

  • 노드 방문
  • 왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더
  • 오른쪽 자식 노드를 루트로 하는 서브 트리 프리오더
  • A B D E C F G

• 인오더 (준위 순회)

  • 왼쪽 자식 노드를 루트로 하는 서브 트리 인오더
  • 노드 방문
  • 오른쪽 자식 노드를 루트로 하는 서브 트리 인오더
  • D B E A F C G

• 포스트오더 (후위 순회)

  • 왼쪽 자식 노드를 루트로 하는 서브 트리 포스트 오더
  • 오른쪽 자식 노드를 루트로 하는 서브 트리 포스트 오더
  • 노드 방문
  • D E B F G C A

트리의 탐색

• 사이클이 없는 그래프이기 떄문에 임의의 두 정점 사이의 경로는 1개이다.
• DFS와 BFS로 최단거리를 구할 수 있다.

트리의 지름

• 트리에 존재하는 모든 경로 중에서 가장 긴 것이 트리의 지름이다.
• 탐색 2번으로 구할 수 있다.
  • 루트에서 모든 정점까지의 거리를 구하고, 가장 먼 거리인 정점을 A라고 한다.
  • A를 루트라고 하고 모든 정점까지의 거리를 구하고, 이 때 구한 가장 먼 거리가 지름이다.