---

⚡ Tree

---

📌 트리

🔷 개념

• 비선형 구조
• 원소들 간에 1:N 관계를 가지는 자료구조
• 원소들 간에 계층관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조

🔷 정의

• 한 개 이상의 노드로 이루어진 유한 집합

  • 노드 중 최상위 노드를 루트(root)라 한다.
  • 나머지 노드들은 n(>=0)개의 분리 집합 T1, ..., TN으로 분리될 수 있다.

• 이들 T1, ..., TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 한다.

  🌟 용어 정리
  노드(node): 트리의 원소
  간선(edge): 노드를 연결하는 선, 부모 노드와 자식 노드를 연결
  루트 노드(root node): 트리의 시작 노드
  형제 노드(sibling node): 같은 부모 노드의 자식 노드들
  조상 노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
  서브 트리(subtree): 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
  자손 노드: 서브 트리에 있는 하위 레벨의 노드들

🔷 차수(degree)

• 노드의 차수: 노드에 연결된 자식 노드의 수
• 트리의 차수: 트리에 있는 노드의 차수 중에서 가장 큰 값
• 단말 노드(리프 노드): 차수가 0인 노드 (자식 노드가 없는 노드)

🔷 높이

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

---

📌 이진 트리

🔷 정의

• 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대한 2개(왼쪽 자식 노드, 오른쪽 자식 노드)까지만 가질 수 있는 트리

🔷 특성

• 레벨 i 에서의 노드의 최대 개수는 2^i 개
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^h+1-1)개가 된다.

🔷 종류

1. 포화 이진 트리(Perfect Binary Tree)

• 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리
• 높이가 h일 때, 최대의 노드 개수인 (2^h+1 - 1)의 노드를 가진 이진 트리

  높이 3일 때 2^3+1 - 1 = 15 개의 노드

• 루트를 1번으로 하여 2^h+1 - 1까지 정해진 위치에 대한 노드 번호를 가짐

2. 완전 이진 트리(Complete Binary Tree)

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

3. 편향 이진 트리(Skewed Binary Tree)

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

🔷 표현

1. 배열

• 루트의 번호를 1로 한다.
• 이진 트리에 각 노드 번호를 왼쪽부터 오른쪽으로 번호 부여
• 레벨 n에 있는 노드에 대하여 2^n부터 2n+1 - 1 까지 번호를 차례대로 부여
• 노드 번호를 배열의 인덱스로 사용하여 노드 번호의 성질 이용이 가능하다!

🌟 노드 번호의 성질
1) 노드 번호가 i인 노드의 부모 노드 번호: i/2(나머지 내림)
2) 노드 번호가 i인 노드의 왼쪽 자식 노드 번호: 2*i
3) 노드 번호가 i인 노드의 오른쪽 자식 노드 번호: 2*i + 1
4) 레벨 n의 노드 번호 시작 번호: 2^n

• 단점
  1) 편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비가 발생한다.
  2) 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우, 배열의 크기 변경이 어려워 비효율적이다.

2. 연결리스트

• 배열을 이용한 이진 트리의 표현의 단점 보완
• 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현

🔷 순회

• 트리의 각 노드를 중복되지 않게 전부 방문하는 것
• 비 선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없기 때문에 특별한 방법이 필요하다.

1. 전위 순회(preorder traversal): VLR

• 부모 노드 방문 후, 자식 노드를 좌, 우 순서로 방문한다.

  1) 현재 노드 n을 방문 - V
  2) 현재 노드 n의 왼쪽 서브 트리로 이동 - L
  3) 현재 노드 n의 오른쪽 서브트리로 이동 - R

2. 중위 순회(inorder traversal): LVR

• 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순으로 방문한다.

3. 후위 순회(postorder traversal): LRV

• 자식 노드를 좌우 순서로 방문한 후, 부모 노드로 방문한다.

  💡 L-R 의 순서는 절대 바뀌지 않는다. 따라서 V의 위치에 따라 방법이 바뀐다.

🖥 자 배열로 구현 드가자

public class dailyClass {
	static char [] arr = new char[] {' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', ' ', ' ', 'H', 'I'};
	static int N = arr.length;
	public static void main(String[] args) {
		preorder(1);
		System.out.println();
		inorder(1);
		System.out.println();
		postorder(1);
	}
	
	// 전위 순회
	// i: 현재 방문 중인 노드 번호
	public static void preorder(int i) {
		// 유효한 노드 check
		if(i < N) {
			if(arr[i] != ' ')
				System.out.print(arr[i] + " "); // V
			
			preorder(i*2); // L
			preorder(i*2+1); // R
		}
	}
	
	// 중위 순회
	// i: 현재 방문 중인 노드 번호
	public static void inorder(int i) {
		// 유효한 노드 check
		if(i < N) {
			inorder(i*2); // L
			if(arr[i] != ' ')
				System.out.print(arr[i] + " "); // V
			inorder(i*2+1); // R
		}
	}
	
	// 후위 순회
	// i: 현재 방문 중인 노드 번호
	public static void postorder(int i) {
		// 유효한 노드 check
		if(i < N) {
			postorder(i*2); // L
			postorder(i*2+1); // R
			if(arr[i] != ' ')
				System.out.print(arr[i] + " "); // V
		}
	}
}