\
트리(Tree)란?
- 노드와 링크로 구성된 자료구조(그래프의 일종)
- 계층적 구조를 나타낼 때 사용한다.
노드(Node): 트리 구조의 자료 값을 담고 있는 단위
에지(Edge): 노드 간의 연결선 (=link, branch)
루트 노드(Root): 부모가 없는 노드, 가장 위의 노드
잎새 노드(Leaf): 자식이 없는 노드 (=단말)
내부 노드(Internal): 잎새 노드를 제외한 모든 노드
부모(Parent): 연결된 두 노드 중 상위의 노드
자식(Child): 연결된 두 노드 중 하위의 노드
형제(Sibling): 같은 부모를 가지는 노드
깊이(Depth): 루트에서 어떤 노드까지의 간선의 수
레벨(Level): 트리의 특정 깊이를 가지는 노드 집합
높이(Height): 트리에서 가장 큰 레벨 값
크기(Size): 자신을 포함한 자식 노드의 개수
차수(Degree): 각 노드가 지닌 가지의 수
트리의 차수: 트리의 최대 차수
트리의 특징
- 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다.
- 노드가 N개인 트리의 간선(Edge)의 수는 N-1개다.
- Cycle이 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, Red-Black트리), 이진 힙(최대 힙, 최소힙) 등이 있다.
이진 트리(Binary Tree)
각 노드가 최대 두 개의 자식을 갖는 트리
자식 노드는 좌우를 구분한다.
왼쪽 자식: 부모 노드의 왼쪽 아래
오른쪽 자식: 부모 노드의 오른쪽 아래
이진 트리 종류
포화 이진 트리 (Perfect Binary Tree)
- 모든 레벨에서 노드 들이 꽉 채워져 있는 트리
완전 이진 트리 (Complete Binary Tree)
- 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리
정 이진 트리 (Full Binary Tree)
- 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
편향 트리 (Skewed Binary Tree) = 사향 트리
- 한쪽으로 기울어진 트리
균형 이진 트리 (Balanced Binary Tree)
- 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리
이진 트리의 순회
너비 우선 검색 (BFS: Breadth-First Search)
낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법
깊이 우선 검색 (DFS: Depth-First Search)
리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 하는 방법, 리프에 도달해서 더 이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다.
전위순회 : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
중위순회 : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
후위순회 : 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문
이진 트리 구현
노드와 이진트리
import java.util.LinkedList;
import java.util.Queue;
// 노드 구성: 데이터, 왼쪽노드, 오른쪽노드, 부모노드
class Node {
char data;
Node left;
Node right;
Node parent;
public Node(char data, Node left, Node right, Node parent) {
this.data = data;
this.left = left;
this.right = right;
this.parent = parent;
}
}
// 이진 트리
class BinaryTree {
Node head;
// 이진 트리 세팅
BinaryTree(char[] arr) {
// null로 세팅
Node[] nodes = new Node[arr.length];
for (int i = 0; i < arr.length; i++) {
nodes[i] = new Node(arr[i], null, null, null);
}
for (int i = 0; i < arr.length; i++) {
int left = 2 * i + 1; // root노드 인덱스는 0이고, 왼쪽노드 인덱스는 1이된다.
int right = 2 * i + 2; // 마찬가지로 오른쪽노드 인덱스는 2가된다.
if (left < arr.length) {
nodes[i].left = nodes[left];
nodes[left].parent = nodes[i];
}
if (right < arr.length) {
nodes[i].right = nodes[right];
nodes[right].parent = nodes[i];
}
}
// root 노드
this.head = nodes[0];
}
// 노드 검색 메서드
public Node searchNode(char data) {
Queue<Node> queue = new LinkedList<>();
queue.add(this.head);
while (!queue.isEmpty()) {
Node cur = queue.poll();
if (cur.data == data) {
return cur;
}
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
return null;
}
// 서브트리 크기 구하는 메서드
public Integer checkSize(char data) {
Node node = this.searchNode(data);
Queue<Node> queue = new LinkedList<>();
queue.add(node);
int size = 1;
while (!queue.isEmpty()) {
Node cur = queue.poll();
if (cur.left != null) {
queue.offer(cur.left);
size++;
}
if (cur.right != null) {
queue.offer(cur.right);
size++;
}
}
return size;
}
}
이진 트리 사용
public class Main {
public static void main(String[] args) {
// 트리에 넣을 배열
char[] arr = new char[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = (char)('A' + i);
}
BinaryTree bt = new BinaryTree(arr);
// root node
System.out.println(bt.head.data); // A
// A's child node
Node A = bt.searchNode('A');
if (A.left != null) {
System.out.println(A.left.data); // B
}
if (A.right != null) {
System.out.println(A.right.data); // C
}
// E's parent node
Node E = bt.searchNode('E');
System.out.println(E.parent.data); // B
// Leaf node
for (int i = 0; i < arr.length; i++) {
Node cur = bt.searchNode((char)('A' + i));
if (cur.left == null && cur.right == null) {
System.out.print(cur.data + " "); // F G H I J
}
}
System.out.println();
// F's Depth
Node F = bt.searchNode('F');
Node cur = F;
int cnt = 0;
while (cur.parent != null) {
cur = cur.parent;
cnt ++;
}
System.out.println(cnt); // 2
// Lv.2 Node
for (int i = 0; i < arr.length; i++) {
Node target = bt.searchNode((char) ('A' + i));
cur = target;
cnt = 0;
while (cur.parent != null) {
cur = cur.parent;
cnt++;
}
if (cnt == 2) {
System.out.print(target.data + " "); // D E F G
}
}
System.out.println();
// Height
int maxCnt = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
Node target = bt.searchNode((char)('A' + i));
cur = target;
cnt = 0;
while (cur.parent != null) {
cur = cur.parent;
cnt++;
}
if (maxCnt < cnt) {
maxCnt = cnt;
}
}
System.out.println(maxCnt); // 3
// C's Size
int size = bt.checkSize('C'); // 3
System.out.println(size);
}
}
'자료구조·알고리즘' 카테고리의 다른 글
구간 합 (0) | 2023.06.23 |
---|---|
배열과 리스트 (0) | 2023.06.23 |
[자료구조] 이진 탐색 트리 (0) | 2022.10.07 |