[알고리즘/JAVA] 트리

트리란?

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

 

트리의 조건

1. 부모 : 자식 = 1 : N
2. 하나의 자식은 둘 이상의 부모X
3. 노드의 개수가 N개 → 간선의 개수 N-1개
4. 원소가 하나이거나 비어있어도 트리 O
5. 싸이클 X

 

트리 용어 정리

• 노드(node) - 트리의 원소
• 간선(edge) - 노드를 연결하는 선 , 부모 노드와 자식 노드를 연결
• 루트 노드 (root node) - 트리의 시작 노드
• 리프 노드 (leaf node) - 자식이 없는 노드
• 경로(path) - 간선들로 연결된 노드를 순서대로 나열한 것
• 거리 : 간선의 수
• 형제 노드(sibling node) - 같은 부모 노드의 자식 노드들
• 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• 서브 트리(subtree) - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
• 자손 노드 - 서브 트리에 있는 하위 레벨의 노드들
• 차수(degree) - 노드의 차수 : 노드에 연결된 자식 노드의 수
• 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
• 단말 노드 - 차수가 0인 노드, 즉 자식 노드가 없는 노드
• 노드의 높이 - 말단에서 노드에 이르는 간선의 수(가장 긴 거리)
• 노드의 레벨 - 루트에서 노드에 이르는 간선의 수, 루트의 레벨은 level0
• 트리의 높이 - 트리에 있는 노드의 높이 중에서 가장 큰 값
• 트리의 높이 = 깊이 = 레벨

 

---

트리의 종류

이진 트리

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

 

포화 이진 트리(Full Binary Tree)

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

 

 

완전 이진 트리(Complete Binary Tree)

높이가 h이고 노드 수가 n개일 때 (단, h+1 ≤ n < 2^(h+1) -1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리
1. 마지막 레벨 빼고 모든 레벨이 다 차있어야 함.
2. 마지막 레벨은 왼쪽부터 채워진다.

 

편향 이진 트리(Skewed Binary Tree)

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

 

---

트리를 저장하는 방법

1. 인접 행렬
2. 인접 리스트

트리는 대부분 인접 리스트로 저장하는 것이 유리하다.

	인접 행렬	인접 리스트
A와 B를 잇는 간선 존재 여부 확인 (시간 복잡도)	O(1)	O(min(deg(A), deg(B)))
A와 연결된 모든 정점 확인 (시간 복잡도)	O(|V|)	O(deg(A))
공간 복잡도	O(|V|2)	O(|E|)

 

---

트리 순회

순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것

3가지의 기본적인 순회방법

•  전위 순회 (preorder traversal) : VLR
  부모 노드 방문 후 , 자식 노드를 좌 우 순서로 방문한다
•  중위 순회 (inorder traversal) : LVR
  왼쪽 자식 노드 , 부모 노드 , 오른쪽 자식 노드 순으로 방문한다
•  후위 순회 (postorder traversal) : LRV
  자식 노드를 좌우 순서로 방문한 후 , 부모 노드로 방문한다

예시 문제 : https://www.acmicpc.net/problem/1991

1991번: 트리 순회

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static ArrayList<node>[] arr;
	static class node{
		int left, right;
		node(int left, int right){
			this.left = left;
			this.right = right;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		arr = new ArrayList[N+1];
		for (int i = 1; i < arr.length; i++) 
			arr[i] = new ArrayList<>();
		for (int i = 1; i < arr.length; i++) {
			int rot = sc.next().charAt(0)-64;
			int lef = sc.next().charAt(0)-64;
			int rig = sc.next().charAt(0)-64;
			arr[rot].add(new node(lef, rig));
		}
		in_order(1);
		sb.append('\n');
		pre_order(1);
		sb.append('\n');
		post_order(1);
		System.out.println(sb.toString());
	}
	private static void in_order(int x) {
		sb.append((char)(x+64));
		if(arr[x].get(0).left>0)
			in_order(arr[x].get(0).left);
		if(arr[x].get(0).right>0)
			in_order(arr[x].get(0).right);
	}
	
	private static void pre_order(int x) {
		if(arr[x].get(0).left>0)
			pre_order(arr[x].get(0).left);
		sb.append((char)(x+64));
		if(arr[x].get(0).right>0)
			pre_order(arr[x].get(0).right);
	}
	
	private static void post_order(int x) {
		if(arr[x].get(0).left>0)
			post_order(arr[x].get(0).left);
		if(arr[x].get(0).right>0)
			post_order(arr[x].get(0).right);
		sb.append((char)(x+64));
	}
}