그래프2 - DAG와 위상 정렬
자료구조2 - 유니온 파인드, 힙, BST

1. 트리

그래프의 일종

• 모든 정점끼리 연결되어 있어야 한다.
• 방향을 무시했을 때 사이클이 존재하지 않아야 한다.

정점 N개의 그래프는 항상 N-1개의 간선을 갖는다. -> 트리의 간선 개수는 정점-1개이다.

특징

계층 구조를 이루는 자료를 표현하는데 유용

루트 노드 : 부모노드가 없는 노드
깊이 : 루트 노드와의 거리
높이 : 가장 깊은 정점의 깊이 또는 깊이 +1

부모 노드 : 연결관계의 두 노드 중 상위 노드
자식 노드 : 연결관계의 두 노드 중 하위 노드
리프 노드 : 자식이 없는 노드

차수 : 자식이 없는 노드

문제

1068 트리

1. 특정 노드 이하를 제거한 트리의 자식이 0인 노드의 개수를 구한다.
2. 만약 지워진 노드의 형제가 자신밖에 없으면(부모의 자식의 수가 1이면) 1

11725 트리의 부모 찾기

2. 이진 트리

3. 트리의 지름