[DataStructure] 트리

트리

---

1. 트리

---

1. 트리

정점(Node)과 간선(Edge)로 이루어져있고, 계층적인 관계를 표현하기 위해서 사용되는 자료구조입니다.

이진 트리, 이진 탐색 트리, 이진 힙, AVL 트리, 힙 트리, B-트리, B+트리 등 다양한 종류가 있습니다.

트리의 삽입과 삭제는 트리의 종류에 따라 다르게 나타나기 때문에 트리에서 노드를 방문하는 순서에 대해 다뤄보겠습니다.

 

- 전위 순회

1. 현재 노드 방문

2. 왼쪽 서브트리 방문

3. 오른쪽 서브트리 방문

 

- 중위 순회

1. 왼쪽 서브트리 방문

2. 현재 노드 방문

3. 오른쪽 서브트리 방문

 

- 후위 순회

1. 왼쪽 서브트리 방문

2. 오른쪽 서브트리 방문

3. 현재 노드 방문

 

노드를 언제 방문하느냐에 따라서 순회의 방식이 달라집니다.

맨 처음 노드를 방문하면 전위, 나중에 노드를 방문하면 후위, 중간에 노드를 방문하면 중위 순회가 됩니다.

일반적인 트리 구조에서 왼쪽부터 방문하는 것이 원칙이기 때문에 왼쪽부터 방문하게 됩니다.

---

참고 사이트

[자료구조] Tree - 개요 (기본 개념과 구현)

 

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3