트리 순회

➡️ 트리 순회

순회: 자료 구조에 저장된 모든 데이터를 도는 것

트리 순회에는 주로 재귀 함수를 사용함

순회 기본 동작 3가지

1. 재귀적으로 왼쪽 부분 트리 순회
2. 재귀적으로 오른쪽 부분 트리 순회
3. 현재 노드 데이터를 출력

---

☁ Preorder 순회 (전위 순회)

pre: ~ 전에 => 부분 트리 순회 "전"에 현재 노드 출력

현재 노드 데이터 출력 -> 재귀적으로 왼쪽 부분 트리 순회 -> 재귀적으로 오른쪽 부분 트리 순회

출력: F, B, A, D, C, E, G, I, H

---

☁ Postorder 순회 (후위 순회)

post: ~ 후에 => 부분 트리 순회 "후"에 현재 노드 출력

재귀적으로 왼쪽 부분 트리 순회 -> 재귀적으로 오른쪽 부분 트리 순회 -> 현재 노드 데이터 출력

출력: A, C, E, D, B, H, I, G, F

---

☁ Inorder 순회 (중위 순회)

in: ~ 안(사이)에 => 부분 트리 순회 "사이"에 현재 노드 출력

재귀적으로 왼쪽 부분 트리 순회 -> 현재 노드 데이터 출력 -> 재귀적으로 오른쪽 부분 트리 순회

출력: A, B, C, D, E, F, G, H, I

---

✅ 트리 순회가 갖는 의미

트리를 순회하면 노드들 사이에 선형적 순서를 만들 수 있음!!

ex) Inorder 순회 시: A, B, C, D, E, F, G, H, I

트리의 노드들을 어떤 방식으로 저장하는지, 이 노드들을 어떻게 순회하는지에 따라 트리에도 선형적 관계를 사용할 수 있음!!