[JS][자료구조] 트리(Tree)

트리에 대해 알아보자,,!

⚡정의

그래프의 일종으로 두 노드 사이의 하나의 간선만 연결되어 있는, 최소 연결과 계층 형태의 비선형 자료구조

 

📚트리 구조 및 용어

 

• 노드 : 하나 이상의 값을 갖는 객체 단위
• 간선 : 두 노드를 연결하는 선
• 루트 노드 : 부모가 없는 최상위 노드
• 단말 노드 : 자식이 없는 노드
• 부모 노드 : 특정 Sub-Tree 내에서의 상위 노드
• 자식 노드 : 특정 Sub-Tree 내에서의 하위 노드

 

📚트리 특징

• 노드 크기(size) : 자신을 포함한 모든 자손의 노드 개수 
• 노드 깊이(depth) : 루트에서 특정 노드에 도달하기 위한 간선의 개수
• 노드 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
• 노드 차수(degree) : 노드가 지닌 가지의 수
• 트리 차수(tree degree) : 트리의 최대 차수
• 트리 높이(height) : 루트 노드에서 가장 깊숙이 있는 노드의 길이

 

📚트리의 종류

이진 트리, 이진 탐색 트리, AVL 트리, 힙(Heap)

 

📚트리의 순회

정의

트리 구조에서 각각의 노드를 정확히 한 번씩 체계적인 방법으로 방문 하는 과정

 

순회 종류

NODE를 기준으로 앞, 중간, 뒤 생각하기!

• 전위 순회 (Pre -order) : N - L - R
• 중위 순회 (In-order) : L - N - R
• 후외 순회 (Post-order) : L - R - N
• 층별 순회(Level-order) : 낮은 Level 부터 순차적으로 순회

 

필요 용어

• N (Node) : 해당 노드를 방문
• L (Left) : 왼쪽 서브 트리로 이동
• R (Right) : 오른쪽 서브 트리로 이동

예시 트리

 

전위 순회(Pre-order)

전위 순회 방법 : N - L - R

1. 노드를 방문한다.
2. 왼쪽 서브트리를 전위 순회한다.
3. 오른쪽 서브트리를 전위 순회한다

방문 순서

F → B → A → D→ C → E →G → I → H

 

중위 순회(Post-order)

중위 순회 방법 : L - N - R

1. 왼쪽 서브트리를 중위 순회 함
2. 노드를 방문
3. 오른쪽 서브트리를 중위 순회함

방문 순서

A → B → C → D → E → F → G → H → I

 

후위 순회(Post-order)

후위 순회 방법 : L - R - N

1. 왼쪽 서브트리를 중위 순회 함
2. 오른쪽 서브트리를 중위 순회함
3. 노드를 방문

방문 순서

A → C → E → D → B → H → I → G → F

 

층별 순회(Level-order)

층별 순회 방법 : 낮은 Level 부터 순차적으로 순회

1. root 노드를 방문
2. Level 증가
3. 왼쪽에서 오른쪽 순으로 방문

💡한 LEVEL을 다 탐색하고 다음 LEVEL ~~~

방문 순서

F → B → G →A → D → I →C → E → H