트리
계층적 관계를 표현하는 비선형적 자료구조
- 노드와 간선으로 이루어진 자료구조 (모두가 연결)
- 루트 노드가 존재
- 부모-자식으로 표현되는 계층 구조 가짐
- 방향성이 존재하는 방향 그래프이며 사이클 불가능
- 정점(노드)개수 |V| = 간선개수 |E| +1
트리 용어
- 루트 노드 : 트리 가장 윗부분 ex) 1
- 리프 노드 : 트리 가장 아랫부분 ex) 8, 5, 6, 7
- 부모 노드 : 어떤 노드에서 가지로 연결된 위쪽 노드
- 자식 노드 : 어떤 노드에서 가지로 연결된 아래쪽 노드
ex) 2부모 - 4,5 자식 / 3부모 - 6,7 자식 - 형제 노드 : 부모가 같은 노드
ex) 4,5 형제 / 6,7 형제 - 레벨 : 루트에서 얼마나 떨어져 있는 지를 나타낸 값
- 깊이(높이) : 루트에서 가장 멀리 떨어진 리프까지의 거리
ex) 0 Depth - 1 / 1 Depth - 2,3 / 2 Depth - 4,5,6,7 / 3 Depth - 8 - 차수 : 정점에 연결되어 있는 간선의 수, 노드가 갖는 자식 수
- 서브 트리 : 다른 노드를 루트로 그 자손으로 이루어진 트리
- 경로(path) : 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열
이진 트리
각 노드가 왼쪽 자식과 오른쪽 자식 둘을 갖는 트리
- 자식 노드 최소 2개
트리 구현 방법
1) 인접 배열 구현 : 2차원 배열(이진트리) - int[N][2]
말단 노드[-1]
- 2차원 배열로 구현시 메모리 효율↓, 탐색량↑
2) 인접 리스트 구현 : 리스트는 가변적이기 때문에 탐색이 효율적
부모, 자식 구분할 수 없을 때 양방향 노드
이진트리 순회 - DFS
- 깊이 우선 탐색(세로형 탐색)
- 리프노드까지 아래로 내려가면서 탐색
- 리프에 도달해 더 이상 탐색할 곳이 없으면 부모로 돌아가고 다시 탐색 진행
A
↙↘
B C
1) 전위순회(Preorder) : 출발하기 직전 부모 노드 방문
노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
2) 중위순회(inorder) : 가는 도중 부모 노드 방문
왼쪽 자식 -> 노드 방문 -> 오른쪽 자식 (자식 노드 먼저 출력)
3) 후위순회(postorder) : 돌아온 후 부모 노드 방문
왼쪽 자식 -> 오른쪽 자식 -> (돌아와 노드 방문)
이진트리 순회 - BFS
- 너비 우선 탐색(가로형 탐색)
- 낮은 레벨(높이) 부터 시작해 왼쪽에서 오른쪽 방향으로 가다가
한 레벨에서 탐색이 끝나면 다음 레벨로 넘어가는 것
DFS 구현
while - iterative
재귀 - recursive
완전 이진 트리
루트에서 아래쪽 레벨로 내려가는 노드가 빠짐없이 채워져 있고,
또 같은 레벨에서 왼쪽에서 오른쪽으로 노드가 빠짐없이 채워져 있는 이진트리(마지막 제외)
- 마지막 레벨을 제외한 레벨은 노드를 빠짐없이 가득 채운다.
- 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 빠짐없이 가득 채우되 끝까지 채울 필요 없다
마지막 레벨이 아니면 노드를 가득 채움
1) 루트 없는 트리, 루트를 1로 가정
2) ArrayList<>[] 탐색 - 재귀(DFS),스택(DFS),큐(BFS)
3) ArrayList 인접 리스트 N개
4) 부모 자식을 모르기 때문에 양방향으로 값 넣어주기
5) isVisited = true/false
Just Do IT ------- 🏃♀️