노드와 에지로 연결된 그래프의 특수한 형태
그래프의 포현으로도 트리를 표현할 수 있음
트리의 특징
- 순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노트가 존재
- 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖음
- 트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따름
- 트리에서 임의의 두 노드를 이어주는 경로는 유일함

핵심 이론

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
에지	노드와 노드의 연결 관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
서브 트리	전체 트리에 속한 작은 트리

코딩테스트에서 tree

그래프로 푸는 tree
- Node Edge → 인접 리스트로 표현 → DFS, BFS
tree 만을 위한 문제
- 이진트리 & 세그먼트 트리(index tree) & LCA(최소 공통 조상)
  - 1차원 배열로 tree 표현
    - 부모 노드로 이동 → index/2

[067] 트리의 부모 찾기

https://www.acmicpc.net/problem/11725
2 → 4 / 3 → 6 / 4 → 1 / 5 → 3 / 6 → 1 / 7 → 4
양방향 에지로 간주하고 저장
인접 리스트 자료구조 사용 → tree는 그래프도 되기 때문
1번 노드부터 DFS로 탐색하면서 부모 노드를 찾아 주면 문제를 쉽게 해결할 수 있음

자식 노드로 가기 직전에 현재 노드가 다음번에 탐색할 노드의 부모 노드