트리 알아보기

• 트리는 노드와 엣지로 연결된 그래프의 특수한 형태이다.
  • 그래프의 표현으로도 트리를 표현할 수 있다.

🌸 트리의 특징

• 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.
• 트리의 부분 트리 역시 트리의 모든 특징을 따른다.
• 트리에서 임의의 두 노드를 이어주는 경로는 유일하다.

코딩 테스트에서 트리

1. 그래프로 푸는 트리
   1. 인접 리스트로 표현
   2. DFS, BFS로 푼다.
2. 트리만을 위한 문제
   • 이진트리 & 세그먼트 트리 & LCA
     • 1차원 배열로 트리 표현
     • 부모 노드로 이동 index /2, 자식 노드로 이동 index 2 or index 2 + 1

트리의 핵심 이론

• 트리의 구성 요소

---

출처 - 하루코딩