[알고리즘] [10] 트리

1. 트리(Tree)

• 비선형 자료구조
• 원소들 간 관계가 일대다인 계층형 자료구조
• 노드 (Node)는 트리의 원소이며, 최상위 노드를 루트 (root)라고 한다.
• 노드에 연결된 나머지 노드들은 각각 하나의 트리로 묶이며(재귀적 정의) 이를 부트리 (subtree)라 한다.

트리 용어

• 형제 노드 (sibling node) : 같은 부모를 가지는 자식 노드들
• 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로의 모든 노드들
• 서브 트리 (subtree) : 부모 노드와의 간선을 끊었을 때 생기는 새로운 트리
• 자손 노드 : 서브 트리에 있는 하위 노드들
• 차수 (degree)
  >> 노드의 차수 : 노드에 연결된 자식 노드 수
  >> 트리의 차수 : 트리에 있는 노드 차수 중 가장 큰 값
  >> 단말 노드 (리프 노드) : 차수가 0인 노드
• 높이
  >> 노드의 높이 (레벨) : 루트에서 노드에 이르는 간선의 수
  >> 트리의 높이 : 트리에 있는 노드 레벨 중 가장 큰 값

2. 이진 트리

• 차수가 2인 트리
• 각 노드가 자식 노드를 최대 2개까지 가진다.
  >> left child node & right child node

포화 이진 트리 (Perfect Binary Tree)

• 모든 노드가 포화 상태인 이진 트리
• 모든 리프 노드의 레벨이 동일한 트리

완전 이진 트리 (Complete Binary Tree)

• 빈 자리가 없이 완벽하게 채워진 이진 트리

편향 이진 트리 (Skewed Binary Tree)

• 최소 개수의 노드를 가지며 한쪽 방향의 자식 노드만을 가지는 이진 트리

---

3. 배열을 이용한 이진 트리 구현

• 노드 번호가 i 인 노드의 Parent : i / 2
• 노드 번호가 i 인 노드의 Left Child : 2 * i
• 노드 번호가 i 인 노드의 Right Child : 2 * i + 1
• 레벨 n의 노드 번호 시작 : 2^n

import java.util.ArrayDeque;
import java.util.Queue;

// 완전이진트리 배열 구현
// 정해진 크기의 트리
public class CompleteBinaryTree<T> {
	private Object[] nodes;
	private final int SIZE;
	private int lastIdx; // 마지막으로 저장된 노드의 인덱스
	
	public CompleteBinaryTree(int size) {
		super();
		SIZE = size;
		nodes = new Object[size + 1];
		
	}
	public boolean isEmpty() {
		return lastIdx == 0;
	}
	
	public boolean isFull() {
		return lastIdx == SIZE;
	}
	
	public void add(T e) {
		if (isFull()) {
			System.out.println("포화상태");
			return;
		}
		nodes[++lastIdx] = e;
	}
	public void bfs() {
		if (isEmpty()) return;
		
		Queue<Integer> queue = new ArrayDeque<>();
		queue.offer(1); // 방문할 노드를 관리할 값 넣기(노드 번호 인덱스)
		
		while (!queue.isEmpty()) {
			int current = queue.poll();
			System.out.println(nodes[current]);
			
			// Left Child
			if (current * 2 <= lastIdx) queue.add(current * 2);
			
			// Right Child
			if (current * 2 + 1 <= lastIdx) queue.add(current * 2 + 1);
			
		}
	}
}

4. 비선형 자료구조 완전 탐색

• 트리, 그래프와 같은 비선형 구조는 선형 구조와 달리 선후 연결 관계를 알 수 없다.
• BFS, DFS와 같은 방식이 있다.

BFS (Breadth First Search) : 너비 우선 탐색

• 루트 노드의 자식 노드를 모두 방문한 후, 방문했던 자식 노드를 기준으로 다시 해당 노드의 자식 노드를 차례로 방문하는 방식
• 선입선출 형태의 큐를 사용해야 한다.