[Algorithm] 트리(Tree)에 대해서 정리하기

트리(Tree)란?

트리는 계층적인 데이터 구조를 표현하는 자료구조이다. 비선형 자료구조로, 루트(Root)에서 시작하여 여러 개의 자식 노드(Child Node)를 가질 수 있다.

트리의 특징

• 사이클이 없는 연결 그래프 (Acyclic Graph)
• 노드(Node)와 간선(Edge)으로 구성
• 루트 노드(Root Node): 트리의 최상단 노드
• 자식 노드(Child Node): 부모 노드(Parent Node)에 연결된 하위 노드들
• 리프 노드(Leaf Node): 자식이 없는 노드
• 깊이(Depth): 루트에서 특정 노드까지의 경로 길이
• 높이(Height): 루트에서 가장 깊은 노드까지의 거리

 

이진 트리(Binary Tree)란?

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리이다.

이진 트리의 종류

1. 포화 이진 트리 (Full Binary Tree): 모든 노드가 자식 노드를 0개 또는 2개 가짐.
2. 완전 이진 트리 (Complete Binary Tree): 왼쪽에서 오른쪽으로 순서대로 채워진 트리.
3. 편향 이진 트리 (Skewed Binary Tree): 한쪽 방향으로만 치우친 트리.

 

완전 이진 트리

완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다.

주요 개념

• 배열을 사용하여 완전 이진 트리를 구현
• BFS(너비 우선 탐색)
• DFS(깊이 우선 탐색 - 전위, 중위, 후위 순회)

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

public class CompleteBinaryTree<T> {  // 객체가 생성될 때 T의 타입이 결정

	private Object[] nodes;  // 정점 저장 배열
	private final int SIZE;  // 최대 저장할 수 있는 정점의 수
	private int lastIndex;  // 정점 저장 배열에서 마지막 정점 저장된 인덱스 번호

	public CompleteBinaryTree(int size) {
		SIZE = size;
		nodes = new Object[size + 1];  // 0번 인덱스 사용안함 (정점 번호는 1부터 출발)
	}

	// 비어있는지?
	public boolean isEmpty() {
		return lastIndex == 0;
	}

	// 가득 찼는지?
	public boolean isFull() {
		return lastIndex == SIZE;
	}

	// 정점 추가
	public void add(T e) {
		if (isFull()) {
			System.out.println("포화 상태 입니다.");
			return;
		}

		nodes[++lastIndex] = e;
	}

 

트리 구현 방식

• nodes[] 배열을 사용하여 완전 이진 트리 저장
• lastIndex를 사용하여 마지막 노드를 추적
• add(T e)를 통해 노드를 추가할 때 왼쪽에서 오른쪽 순서대로 삽입

 

BFS (너비 우선 탐색, Level Order Traversal)

BFS는 큐(Queue) 를 사용하여 트리를 레벨 단위로 탐색한다.

public void bfs() {
	Queue<Integer> queue = new ArrayDeque<>();
	queue.offer(1);  // 루트 노드부터 탐색 시작

	while (!queue.isEmpty()) {
		int current = queue.poll();  // 큐에서 꺼내기
		System.out.print(nodes[current] + " ");  // 방문한 정점 처리

		// 왼쪽 자식 추가
		if (current * 2 <= lastIndex) {
			queue.offer(current * 2);
		}

		// 오른쪽 자식 추가
		if (current * 2 + 1 <= lastIndex) {
			queue.offer(current * 2 + 1);
		}
	}
	System.out.println();
}

 

실행 과정

          A
        /   \
      B       C
    /   \   /   \
   D     E F     G
  / \
 H   I

A B C D E F G H I

 

 

BFS0 (깊이 출력 포함)

public void bfs0() {
	Queue<Integer> queue = new ArrayDeque<>();
	queue.offer(1);
	int level = 0;

	while (!queue.isEmpty()) {
		System.out.print("깊이: " + level + " ");
		int size = queue.size();

		while (--size >= 0) {
			int current = queue.poll();
			System.out.print(nodes[current] + " ");

			if (current * 2 <= lastIndex) {
				queue.offer(current * 2);
			}
			if (current * 2 + 1 <= lastIndex) {
				queue.offer(current * 2 + 1);
			}
		}
		System.out.println();
		level++;
	}
}

 

출력 예시

깊이: 0 A 
깊이: 1 B C 
깊이: 2 D E F G 
깊이: 3 H I

 

DFS (깊이 우선 탐색)

DFS는 재귀(Recursion) 를 이용해 탐색

1. 전위 순회 (PreOrder Traversal)

순서: 루트(V) → 왼쪽(L) → 오른쪽(R)

public void dfsByPreOrder(int current) {
	System.out.print(nodes[current] + " ");  // V

	if (current * 2 <= lastIndex) {  // L
		dfsByPreOrder(current * 2);
	}

	if (current * 2 + 1 <= lastIndex) {  // R
		dfsByPreOrder(current * 2 + 1);
	}
}

출력: A B D H I E C F G

 

2. 중위 순회 (InOrder Traversal)

순서: 왼쪽(L) → 루트(V) → 오른쪽(R)

public void dfsByInOrder(int current) {
	if (current * 2 <= lastIndex) {  // L
		dfsByInOrder(current * 2);
	}

	System.out.print(nodes[current] + " ");  // V

	if (current * 2 + 1 <= lastIndex) {  // R
		dfsByInOrder(current * 2 + 1);
	}
}

출력: H D I B E A F C G

 

3. 후위 순회 (PostOrder Traversal)

순서: 왼쪽(L) → 오른쪽(R) → 루트(V)

public void dfsByPostOrder(int current) {
	if (current * 2 <= lastIndex) {  // L
		dfsByPostOrder(current * 2);
	}

	if (current * 2 + 1 <= lastIndex) {  // R
		dfsByPostOrder(current * 2 + 1);
	}

	System.out.print(nodes[current] + " ");  // V
}

출력: H I D E B F G C A

 

트리(Tree)와 그래프(Graph)의 차이점

트리는 사이클이 없는 연결 그래프 (Acyclic Graph)
트리는 계층적 구조(Hierarchical Structure)를 가지며, 부모-자식 관계로 이루어집니다.

트리의 주요 특징

• 사이클(Cycle)이 없음 → 트리는 사이클(Loop)이 없는 연결 그래프이다.
• 항상 하나의 루트(Root) 노드 존재 → 계층 구조를 가짐.
• 모든 노드는 하나의 부모(Parent)만 가짐 → (루트 제외)
• N개의 노드를 가지는 트리는 항상 (N-1)개의 간선을 가짐
• DFS, BFS를 사용하여 탐색 가능

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 일반적인 연결 구조
트리와 달리, 그래프는 계층 구조를 가지지 않으며, 복잡한 연결 관계를 표현할 수 있습니다.

그래프의 주요 특징

• 사이클(Cycle)이 존재할 수 있음 → 트리와의 가장 큰 차이점.
• 모든 노드가 반드시 연결될 필요 없음 → 분리된 그래프(Disconnected Graph) 가능.
• 방향 그래프(Directed Graph, 유향 그래프)와 무방향 그래프(Undirected Graph)로 구분
• DFS, BFS를 사용하여 탐색 가능

Chat GPT가 비교해준 표

 

백준알고리즘 트리 문제

https://superohinsung.tistory.com/161

[백준 알고리즘] 1068번 트리(Java) 문제 풀이