트리(Tree) 개념
트리는 비선형 자료구조로, 계층적 관계를 표현하는데 최적화된 구조이다. 마치 나무가 뿌리에서 시작해 가지를 뻗어나가는 모습과 유사하여 ‘트리’라는 이름이 붙었다. 실생활에서는 회사의 조직도, 운영체제의 파일 시스템 등에서 트리 구조를 쉽게 찾아볼 수 있다
트리의 기본 용어
- 노드(Node): 데이터를 저장하는 기본 단위
- 엣지(Edge): 노드와 노드를 연결하는 선
- 루트 노드(Root Node): 트리의 최상위 노드
- 부모 노드(Parent Node): 특정 노드의 상위 노드
- 자식 노드(Child Node): 특정 노드의 하위 노드
- 터미널 노드(Terminal Node) 또는 리프 노드(Leaf Node): 자식이 없는 노드
- 내부 노드(Internal Node): 자식이 하나 이상 있는 노드
- 서브트리(Sub Tree): 트리 내부의 부분 트리
트리의 레벨과 높이
A (레벨 1)
/ \
B C (레벨 2)
/ \ / \
D E F G (레벨 3)
- 레벨(Level): 루트 노드를 1로 시작하여, 자식으로 내려갈수록 1씩 증가
- 높이(Height): 트리에서 가장 깊은 레벨의 값
위 예시에서 트리의 높이는 3이다
이진 트리(Binary Tree)
이진 트리는 각 노드가 최대 2개인 자식 노드만을 가질 수 있는 트리이다.
이진 트리의 조건
- 각 노드는 0개, 1개 또는 2개의 자식을 가진다
- 2개를 초과하는 자식을 가지면 이진 트리가 아니다
- 한쪽 방향으로만 자식이 연결되어도 이진 트리이다
이진 트리의 종류
포화 이진 트리(Full Binary Tree)
모든 레벨이 완전히 채워진 트리이다. 마지막 레벨의 모든 터미널 노드가 꽉 차서 새로운 노드를 삽입할 수 없는 상태이다
1
/ \
2 3
/ \ / \
4 5 6 7
완전 이진 트리(Complete Binary Tree)
마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드들은 왼쪽부터 순서대로 채워진 트리이다
1
/ \
2 3
/ \ /
4 5 6
완전 이진 트리가 아닌 경우
- 중간 레벨이 완전히 채워지지 않은 경우
- 마지막 레벨이 왼쪽부터 연속적으로 채워지지 않은 경우
이진 트리 구현
BinaryTree 클래스
public class BinaryTree {
private int data;
private BinaryTree leftSubTree;
private BinaryTree rightSubTree;
// 생성자
public BinaryTree(int data) {
this(data, null, null);
}
public BinaryTree(int data, BinaryTree leftTree, BinaryTree rightTree) {
this.data = data;
this.leftSubTree = leftTree;
this.rightSubTree = rightTree;
}
// Getter 메서드
public int getData() {
return this.data;
}
public BinaryTree getLeftSubTree() {
return this.leftSubTree;
}
public BinaryTree getRightSubTree() {
return this.rightSubTree;
}
// Setter 메서드
public void setData(int data) {
this.data = data;
}
public void setLeftSubTree(BinaryTree tree) {
this.leftSubTree = tree;
}
public void setRightSubTree(BinaryTree tree) {
this.rightSubTree = tree;
}
}
설계 특징
이진 트리에서는 각 노드가 곧 트리이기 때문에, 별도의 Node 클래스 없이 BinaryTree 클래스 하나로 노드와 트리를 모두 표현한다
포화 이진 트리 생성 예제
public class BinaryTreeTest {
public static void main(String[] args) {
// 1부터 7까지의 노드 생성
BinaryTree tree1 = new BinaryTree(1);
BinaryTree tree2 = new BinaryTree(2);
BinaryTree tree3 = new BinaryTree(3);
BinaryTree tree4 = new BinaryTree(4);
BinaryTree tree5 = new BinaryTree(5);
BinaryTree tree6 = new BinaryTree(6);
BinaryTree tree7 = new BinaryTree(7);
// 트리 구조 연결
tree1.setLeftSubTree(tree2);
tree1.setRightSubTree(tree3);
tree2.setLeftSubTree(tree4);
tree2.setRightSubTree(tree5);
tree3.setLeftSubTree(tree6);
tree3.setRightSubTree(tree7);
// 테스트 출력
System.out.println("루트 노드의 오른쪽 자식: " +
tree1.getRightSubTree().getData());
// 루트 노드의 오른쪽 자식: 3
System.out.println("루트 노드의 오른쪽 자식의 왼쪽 자식: " +
tree1.getRightSubTree().getLeftSubTree().getData());
// 루트 노드의 오른쪽 자식의 왼쪽 자식: 6
}
}
트리 순회(Tree Traversal)
트리의 모든 노드를 체계적으로 방문하는 방법이다. 재귀를 활용하여 구현하며, 세 가지 방식이 있다
전위 순회(Pre-order Traversal)
방문 순서: 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
전위 순회 동작 과정
1
/ \
2 3
/ \ / \
4 5 6 7
단계별 방문:
1. 루트(1) 방문 → 출력: 1
2. 왼쪽 서브트리(2) 방문
2-1. 루트(2) 방문 → 출력: 2
2-2. 왼쪽(4) 방문 → 출력: 4
2-3. 오른쪽(5) 방문 → 출력: 5
3. 오른쪽 서브트리(3) 방문
3-1. 루트(3) 방문 → 출력: 3
3-2. 왼쪽(6) 방문 → 출력: 6
3-3. 오른쪽(7) 방문 → 출력: 7
결과: 1 → 2 → 4 → 5 → 3 → 6 → 7
전위 순회 구현
public void preOrderTraversal(BinaryTree tree) {
if (tree == null) return;
System.out.println(tree.getData()); // 루트 방문
preOrderTraversal(tree.getLeftSubTree()); // 왼쪽 순회
preOrderTraversal(tree.getRightSubTree()); // 오른쪽 순회
}
중위 순회(In-order Traversal)
방문 순서: 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
중위 순회 동작 과정
1
/ \
2 3
/ \ / \
4 5 6 7
단계별 방문:
1. 왼쪽 서브트리(2)로 이동
1-1. 왼쪽(4)으로 이동 → 출력: 4
1-2. 루트(2) 방문 → 출력: 2
1-3. 오른쪽(5) 방문 → 출력: 5
2. 루트(1) 방문 → 출력: 1
3. 오른쪽 서브트리(3)로 이동
3-1. 왼쪽(6) 방문 → 출력: 6
3-2. 루트(3) 방문 → 출력: 3
3-3. 오른쪽(7) 방문 → 출력: 7
결과: 4 → 2 → 5 → 1 → 6 → 3 → 7
중위 순회 구현
public void inOrderTraversal(BinaryTree tree) {
if (tree == null) return;
inOrderTraversal(tree.getLeftSubTree()); // 왼쪽 순회
System.out.println(tree.getData()); // 루트 방문
inOrderTraversal(tree.getRightSubTree()); // 오른쪽 순회
}
후위 순회(Post-order Traversal)
방문 순서: 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
후위 순회 동작 과정
1
/ \
2 3
/ \ / \
4 5 6 7
단계별 방문:
1. 왼쪽 서브트리(2)로 이동
1-1. 왼쪽(4) 방문 → 출력: 4
1-2. 오른쪽(5) 방문 → 출력: 5
1-3. 루트(2) 방문 → 출력: 2
2. 오른쪽 서브트리(3)로 이동
2-1. 왼쪽(6) 방문 → 출력: 6
2-2. 오른쪽(7) 방문 → 출력: 7
2-3. 루트(3) 방문 → 출력: 3
3. 루트(1) 방문 → 출력: 1
결과: 4 → 5 → 2 → 6 → 7 → 3 → 1
후위 순회 구현
public void postOrderTraversal(BinaryTree tree) {
if (tree == null) return;
postOrderTraversal(tree.getLeftSubTree()); // 왼쪽 순회
postOrderTraversal(tree.getRightSubTree()); // 오른쪽 순회
System.out.println(tree.getData()); // 루트 방문
}
재귀 동작 분석
중위 순회를 예로 들어 재귀 호출 스택을 단계별로 살펴보겠다
트리 구조:
1
/ \
2 3
/ \ / \
4 5 6 7
중위 순회 재귀 호출 스택:
호출 스택 출력
══════════════════════════════════════════
inOrder(1)
├─ inOrder(2)
│ ├─ inOrder(4)
│ │ ├─ inOrder(null)
│ │ ├─ print(4) → 4
│ │ └─ inOrder(null)
│ ├─ print(2) → 2
│ └─ inOrder(5)
│ ├─ inOrder(null)
│ ├─ print(5) → 5
│ └─ inOrder(null)
├─ print(1) → 1
└─ inOrder(3)
├─ inOrder(6)
│ ├─ inOrder(null)
│ ├─ print(6) → 6
│ └─ inOrder(null)
├─ print(3) → 3
└─ inOrder(7)
├─ inOrder(null)
├─ print(7) → 7
└─ inOrder(null)
완전한 BinaryTree 클래스 (순회 메서드 포함)
public class BinaryTree {
private int data;
private BinaryTree leftSubTree;
private BinaryTree rightSubTree;
public BinaryTree(int data) {
this(data, null, null);
}
public BinaryTree(int data, BinaryTree leftTree, BinaryTree rightTree) {
this.data = data;
this.leftSubTree = leftTree;
this.rightSubTree = rightTree;
}
public int getData() {
return this.data;
}
public BinaryTree getLeftSubTree() {
return this.leftSubTree;
}
public BinaryTree getRightSubTree() {
return this.rightSubTree;
}
public void setData(int data) {
this.data = data;
}
public void setLeftSubTree(BinaryTree tree) {
this.leftSubTree = tree;
}
public void setRightSubTree(BinaryTree tree) {
this.rightSubTree = tree;
}
// 전위 순회
public void preOrderTraversal(BinaryTree tree) {
if (tree == null) return;
System.out.println(tree.getData());
preOrderTraversal(tree.getLeftSubTree());
preOrderTraversal(tree.getRightSubTree());
}
// 중위 순회
public void inOrderTraversal(BinaryTree tree) {
if (tree == null) return;
inOrderTraversal(tree.getLeftSubTree());
System.out.println(tree.getData());
inOrderTraversal(tree.getRightSubTree());
}
// 후위 순회
public void postOrderTraversal(BinaryTree tree) {
if (tree == null) return;
postOrderTraversal(tree.getLeftSubTree());
postOrderTraversal(tree.getRightSubTree());
System.out.println(tree.getData());
}
}
실행 테스트
public class BinaryTreeTest {
public static void main(String[] args) {
// 포화 이진 트리 생성
BinaryTree tree1 = new BinaryTree(1);
BinaryTree tree2 = new BinaryTree(2);
BinaryTree tree3 = new BinaryTree(3);
BinaryTree tree4 = new BinaryTree(4);
BinaryTree tree5 = new BinaryTree(5);
BinaryTree tree6 = new BinaryTree(6);
BinaryTree tree7 = new BinaryTree(7);
tree1.setLeftSubTree(tree2);
tree1.setRightSubTree(tree3);
tree2.setLeftSubTree(tree4);
tree2.setRightSubTree(tree5);
tree3.setLeftSubTree(tree6);
tree3.setRightSubTree(tree7);
// 순회 테스트
System.out.println("=== 전위 순회 ===");
tree1.preOrderTraversal(tree1);
// 출력: 1 2 4 5 3 6 7
System.out.println("\n=== 중위 순회 ===");
tree1.inOrderTraversal(tree1);
// 출력: 4 2 5 1 6 3 7
System.out.println("\n=== 후위 순회 ===");
tree1.postOrderTraversal(tree1);
// 출력: 4 5 2 6 7 3 1
}
}
트리 자료구조의 활용
- 이진 탐색 트리(BST): 효율적인 검색을 위한 정렬된 트리
- 힙(Heap): 우선순위 큐 구현에 사용되는 완전 이진 트리
- AVL 트리: 자가 균형 이진 탐색 트리
- 레드-블랙 트리: 균형 잡힌 탐색 성능 보장
스택과 큐가 연결 리스트에 규칙을 추가하여 탄생한 것처럼, 이진 트리 역시 다양한 규칙과 조건을 추가하여 더 강력한 자료구조로 발전한다
핵심 정리
- 트리는 계측적 구조를 표현하는 비선형 자료구조이다
- 이진 트리는 각 노드가 최대 2개의 자식만 가지는 트리이다
- 트리 순회는 재귀를 활용하여 효율적으로 구현할 수 있다
- 순회 방식에 따라 방문 순서가 달라지며, 각각 다른 용도로 활용된다
- 이진 트리는 다양한 고급 자료구조의 기반이 된다
인프런 강의 중 감자님의 강의 ‘그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)’ 강의 참고