모든 사진 자료에 관한 출처는 아래 알튜비튜 - 튜터링에 있음을 밝힙니다.
https://github.com/Altu-Bitu/Notice

🎄트리

• 비선형 자료구조
• 그래프의 부분 집합으로 사이클이 없고, V개의 정점에 대해 V-1개의 간선이 있음.
• 부모-자식의 계층 구조
• 트리 탐색의 시간 복잡도는 O(h) (h=트리의 높이)
• 그래프와 마찬가지로 DFS,BFS를 이용하여 탐색

---

트리 vs 그래프

	트리	그래프
간선의 수	V-1개	V-1개이상
특정 정점 사이 경로의 수	1개	1개 이상
방향 유무	O	O or X
사이클 유무	X	O or X
계층 관계	O	X

---

트리 용어

Tree

• Root : 부모 정점이 없는 최 상위 정점
• SubTree : 트리의 부분집합
• Leaf node : 자식 정점이 없는 정점
• Level : 트리의 각계층
• Height : level중 가장 큰 값

---

트리의 종류

• Binary Tree (이진 트리) : 자식 정점의 수가 2개 이하
• General Tree(일반 트리) : 자식 정점의 수에 제한 없음

---

트리 구현(이진 트리)

1.구조체 + 포인터

: 실시간으로 트리를 만들어야할때 적합.

2. 맵1

: 이미 트리 관계가 정의되어 있을때 적합

• 자식노드가 없을(NULL)경우 -1로 표시

3. 맵2

: 정점번호가 연속하지 않을때 적합. ex) 1,3,6,7,9

4. 2차원 벡터

: 정점 번호가 연속할때 적합

---

이진 트리의 특징

• 시간복잡도가 트리의 높이에 비례한다!

---

이진 트리의 종류

• Full Binary : leaf 노드들을 제외한 모든 노드들이 0개 혹은 2개의 children 을 가지고 있을 때.

• Complete Binary : 마지막 level 을 제외한 나머지 level 에 node 들이 가득 차있고, 마지막 level 에서 node 는 가장 왼쪽 부터 채워지는 형태

---

이진 트리 순회

• 레벨 순회
  

• 전위 순회
  : v -> l -> r -> 3 6 5 4 7 1
  

• 중위 순회
  : l -> v -> r -> 5 6 4 3 1 7
  

• 후위 순회
  : l -> r ->v -> 5 4 6 1 7 3
  

---

다양한 트리 연산

• 트리의 정점 수 구하기

int nodeCnt(int node){ 
int cnt=0;
for (int child : tree[node])
cnt+=nodeCnt(child); // 현재(node)의 자식노드의 노드 수를 모두 더함.
return cnt+1; //자식 노드의 노드 갯수 + 자신

• 리프 노드의 수 구하기
  

int leafCnt(int node){ 
if (tree[node].empty()) //자식노드가 없다면 (leaf)
return 1;

int cnt =0;
for (int chlid : tree[node])
cnt+=leafCnt(child);
return cnt;

• 트리의 높이 구하기

int treeHeight(int node){
int height = 0;
for (int child : tree[node]){
height = max(height, treeHeight(child)); //자식노드의 높이중 가장 큰 것.

return height+1; // 현재 노드까지의 높이는 자식노드의 높이+1
}