이진탐색트리의 순회

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

위 문제의 그림을 가지고 설명하였습니다.

 

 

전위 순회

---

전위 순회는 Root - 왼쪽 서브 트리 - 오른쪽 서브 트리 순으로 방문합니다

이진 탐색 트리는 왼쪽 서브 트리의 값들은 Root 보다 작고 오른쪽 서브트리의 값들은 Root보다 크므로

전위 순회한 결과를 통해 트리의 구조를 나타낼 수 있습니다.

 

50 30 24 5 28 45 98 52 60 같은 전위 순회 결과의 경우

50 | 30 24 5 28 45 | 98 52 60으로 나누어서 Root, 왼쪽 서브 트리, 오른쪽 서브 트리의 값들로 나타낼 수 있습니다.

다시 30 24 5 28 45의 경우 30 | 24 5 28 | 45로 나눌 수 있습니다.

 

 

중위 순회

---

왼쪽 -> Root -> 오른쪽 순으로 순회합니다

이렇게 순회하면 오름차순의 값들을 가질 수 있습니다.

오른쪽 -> Root -> 왼쪽 순으로 순회하면 내림차순의 값들을 가질 수 있습니다.

 

 

후위 순회

---

왼쪽 -> 오른쪽 -> Root 순으로 순회합니다.

트리의 삭제에서 부모 노드를 삭제하면서 자식 노드까지 삭제하는 경우 후위 순회를 사용할 수 있습니다.

 

 

References

---

https://yoongrammer.tistory.com/70