[알고리즘] 트리

< 트리 >

• 비선형, 계층형
• 최상위 노드 = Root
• 트리는 부트리로 구성
• edge - 노드를 연결하는 선.
• 형제 노드 - 같은 부모의 자식 노드
• 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• 서브 트리 - 부모 노드와 간선을 끊었을 때 생성되는 트리
• 자손 노드 - 서브 트리에 있는 하위 레벨 노드들

<차수>

• 노드의 차수 : 노드에 연결된 자식 노드 수
• 트리의 차수 : 모든 노드들 차수 중 가장 큰 값

<높이>

• 노드의 높이 : 루트에서 노드에 이르는 간선 수. 노드의 레벨과 같음
• 트리의 높이 : 트리에 있는 노드 높이 중에서 가장 큰 값. 최대 레벨

---

< 이진 트리 >

• 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대 2개까지 가질 수 있음
• 레벨 i에서 노드 최대 개수는 2^i개
• 높이가 h인 이진 트리가 가질 수 있는 노드 최소 개수는 (h+1)개, 최대 개수는 (2^h+1 - 1)개

< 포화 이진 트리 (Full Binary Tree) >

• 모든 레벨 노드가 포화상태
• 높이가 h일 때, 최대 노드 개수 가진 이진 트리

< 완전 이진 트리 (Complete Binary Tree) >

• 높이가 h이고 노드 수가 n개일 때 (단, h+1 <= n < 2^(h+1) -1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

< 편향 이진 트리 (Skewed Binary Tree) >

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드 만을 가진 이진 트리

---

< 트리 완전 탐색 >

• BFS(너비 우선 탐색)
• DFS(깊이 우선 탐색)