과제
- int 값을 가지고 있는 이진 트리를 나타내는 Node 라는 클래스를 정의하세요.
- int value, Node left, right를 가지고 있어야 합니다.
- BinrayTree라는 클래스를 정의하고 주어진 노드를 기준으로 출력하는 bfs(Node node)와 dfs(Node node) 메소드를 구현하세요.
- DFS는 왼쪽, 루트, 오른쪽 순으로 순회하세요. => 중위 순회
학습
0. 트리
-
백준 알고리즘 문제 15881번 트리와 쿼리 에 나와있는 설명을 덧붙인다
-
트리구조란?회로(사이클)가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.- 그래프에 사이클이 하나도 없다는 것이 중요하다. 알고리즘 문제에서는 그래프에 사이클이 하나도 없다면 트리라고 정의한다.
-
트리에서 간선의 개수는
정점(노드)의 수 - 1- 서로 다른 두 노드를 잇는 길(간선)이 하나 밖에 없어서
루트 노드, 부모와 자식 관계
루트노드(root node): 최상위 노드- 트리에는 루트가 있을 수도 있고 없을 수도 있다
- 루트를 고정하면 부모와 자식의 관계를 정의할 수 있다
- (그림출처 위 알고리즘 문제) 예를 들어 아래와 같은 그래프
에서 노드 5를 루트로 고정하면 다음과 같이 된다 
용어
- 노드 A가 노드 B를 가리킬 때 A를 B의
부모노드(parent node)라고 하고 B를 A의자식노드(child node)라고 한다. 잎 노드(leaf node): 자식노드가 없는노드내부노드 (internal node): 잎 노드가 아닌 노드
트리 특성
- 1) 임의의 두 점 U,V에 대해 U에서 V로 가는 최단 경로는 유일하다
- 2) 아무 정점이나 잡고 부모와의 연결을 끊었을 때 정점 아래 (정점과 그 자식들, 그 자식들의 자식들로) 이루어진 부분그래프는 트리가 된다 (서브트리)
1. 이진트리
- 이진트리란 ? 각 노드가 최대 2개의 자식 노드를 가진 구조
1-1. 완전 이진 트리 Complete Binary Tree
- 출처 : 위키
- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다.
- 또 다른 정의 : 가장 오른 쪽 잎노드가 제거된 포화 이진 트리
- 그림출처
- 왼쪽의 full tree은 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있지도 않고 혹시 아래 그림처럼 채워져 있다고 해도
맨 왼쪽 하얀 노드가 없기 때문에 완전 이진 트리가 아니다 - full tree는 자식이 아예 없거나 2개만 있어야 한다. (자식이 1개 있는 노드가 있어서는 안된다)
- 자료구조 heap은 완전 이진트리를 사용
2. 탐색 알고리즘 BFS, DFS
- BFS(Breadth-first Search) 너비우선탐색
- 루트 노드에서 시작해서 현재 depth에 있는 노드를 다 탐색한 후 다음 depth로 탐색을 시작한다.
- DFS(Depth-first Search) 깊이우선탐색
- 루트노드에서 시작해서 각 자손의 제일 아래에 있는 자식노들 까지 다 탐색한후 다음 형제 노드로 가는 방법
- 루트노드 방문을 언제 하느냐에 따라서 Pre-order(전위), In-order(중위), Post-order(후위)가 있다.
- Pre-order(전위)
[루트][왼쪽자식][오른쪽자식]: 루트 -> 왼쪽 자식 노드를 루트로 하는 서브트리를 재귀로 Pre-order -> 오른쪽 자식 노드를 루트로 하는 서브트리를 재귀로 Pre-order - In-order(중위)
[왼쪽자식][루트][오른쪽자식]: 왼쪽 자식 노드 루트로 하는 서브트리를 재귀로 In-order -> 루트 -> 오른쪽 자식 노드 루트로 하는 서브트리를 재귀로 In-order - Post-order(후위)
[왼쪽자식][오른쪽자식][루트]: 왼쪽 자식 노드 루트로 하는 서브트리를 재귀로 Post-order -> 오른쪽 자식 노드 루트로 하는 서브트리를 재귀로 Post-order -> 루트 
출처 : 위키- 관련 알고리즘 문제 백준 1991번 : 트리 순회
- Pre-order(전위)
3. 코드
출처
spring, java학습