전위순회, 중위순회, 후위순회란?

1. 개념
2. 예제

 

 

 

---

 

 

1. 개념

 

• 전위 순회
  • 부모 노드를 먼저 방문하는 순회 방식
  • 우선순위: 부모 노드 > 왼쪽 노드 > 오른쪽 노드

위 트리를 전위순회를 한다면 1-2-3 순서로 방문하게 된다.

 

 

• 중위 순회
  • 왼쪽 노드를 먼저 방문 후 부모 노드를 방문하는 순회 방식
  • 우선순위: 왼쪽 노드 > 부모 노드 > 오른쪽 노드

위 트리를 중위순회를 한다면 2-1-3 순서로 방문하게 된다.

 

 

 

• 후위 순회
  • 하위 노드를 먼저 방문 후 부모 노드를 방문하는 순회 방식
  • 우선순위: 왼쪽 노드 > 오른쪽 노드 > 부모 노드

위 트리를 후위순회를 한다면 2-3-1 순서로 방문하게 된다.

 

 

 

이름이 굉장히 헷갈릴 수 있는데 항상 부모 노드를 중심으로 생각하면 기억하기 쉽다.

부모 노드를 언제 방문하는지를 기준으로 네이밍을 했다는 점을 기억하자.

 

전위 순회: 부모 노드 > 왼쪽 노드 > 오른쪽 노드

중위 순회: 왼쪽 노드 > 부모 노드 > 오른쪽 노드

후위 순회: 왼쪽 노드 > 오른쪽 노드 > 부모 노드

 

 

 

2. 예제

예제 트리

 

 

위 예제 트리를 보고 각각 전위를 하면 어떤 순서로 방문하게 되는지 연습해보자.

 

① 시작은 항상 Root 노드이다. '7'을 방문하고 다음 우선순위인 왼쪽 노드인 '3'을 방문한다.

② '3'을 방문했다. 다음 우선 순위인 왼쪽 노드 '1'을 방문한다.

③ '1'은 더 이상 자식 노드가 없으므로 다시 '3'으로 올라간다.

④ '3' 기준으로 오른쪽 노드는 아직 방문하지 않았으므로 '2'를 방문한다.

⑤ '2'는 더 이상 자식노드가 없으므로 다시 '3'으로 올라간다.

⑥ '3'의 자식 노드는 전부 방문했으므로 '7'로 올라간다.

⑦ '7' 기준으로 오른쪽 노드는 아직 방문하지 않았으므로 '6'을 방문한다.

⑧ '6'을 방문했다. 다음 우선순위인 왼쪽 노드 '4'를 방문한다.

⑨ '4'는 더 이상 자식 노드가 없으므로 다시 '6'으로 올라간다.

⑩ '6'을 기준으로 오른쪽 노드는 아직 방문하지 않았으므로 '5'를 방문한다.

⑪ '5'는 더 이상 자식노드가 없으므로 다시 '6'으로 올라간다.

⑫ '6'의 자식 노드는 전부 방문했으므로 '7'로 올라간다.

⑬ 끝

 

결국 방문순서는 7-3-1-2-6-4-5가 된다.

글로 표현하려니 꽤 길어졌는데 연습하고 보면 아주 간단한 과정이다.

이제 중위 순회와 후위 순회를 연습해봐야 하는데...

 

절대 귀찮아서 그런거 아님 (아마)

 

중위 순회, 후위 순회를 할 때는 방문한 노드보다 우선순위인 노드가 있다면

그 노드부터 방문해야 한다는 것을 기억하면서 연습을 해보고 아래 정답과 일치하는지 확인해보자.

 

중위 순회: 1-3-2-7-4-6-5

후위 순회: 1-2-3-4-5-6-7

 

후위 순회의 답을 보고 "어 뭐야? 왜 숫자가 정렬돼서 나오지?'라고 생각했을 것이다.
예제로 쓰인 트리가 힙 구조이기 때문이다.
힙 구조는 후위 순회를 했을 경우 정렬이 되는 성질이 있다. (이거 아님. 아니였음)
힙에 대해서 더 자세히 알고 싶다면 이 포스팅을 참고하자.

 

2021.08.31 수정
힙 구조는 후위 순회를 했을 경우 정렬이 되는 성질이 있다... 라고 적었었는데.
이건 왼쪽 자식노드가 오른쪽 자식노드보다 컸을때 해당하는 이야기다.
결국 개소리였다. 나는 바보...

 

 

 

---

💡 느낀 점

• 사실 힙 구조를 후위 순회하면 정렬된다는 걸 이번에 알았다. 아니 배웠는데 까먹었을지도...
• 그렇다면 힙 정렬할 때 힙 삭제를 거쳐 정렬하는 이유는 무엇일까? 후위 순회로도 정렬할 수 있는데? 다음 포스팅에서 다뤄야겠다.
• (2021.08.31 수정) 잘못 생각했다는 걸 깨달았다.

---