[Python 자료구조] 순회 (Traversal)

⭐ 순회 (Traversal)

1. 깊이 우선 순회

중위 순회 (In-order Traversal)

• left subtree → 자기 자신 → right subtree

전위 순회 (Pre-order Traversal)

• 자기 자신 → left subtree → right subtree

후위 순회 (Post-order Traversal)

• left subtree → right subtree → 자기 자신

2. 넓이 우선 순회

• 수준이 낮은 노드 우선 방문!
• 같은 수준이면, 부모 노드의 방문 순서에 따라 방문, 왼쪽자식이 오른쪽 자식보다 먼저 방문
• 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기억해야함 → 큐를 활용

3. 알고리즘 구현

1. traversal = 빈 리스트, q = 빈 큐를 만들고
   
   
2. 루트 노드를 q에 넣는다
   
   
3. q에 노드가 있을때
   - q에서 노드를 꺼낸다
   - 그 노드의 자식을 확인해서 왼쪽, 오른쪽 순으로 q에 넣는다
   
   
4. 빈 q가 되면 순회 끝!