[Section2][자료구조/알고리즘] 자료구조 - Tree traversal

트리 순회(Tree traversal) 란?

트리를 순회하는 방법을 말한다.

 

 

 

트리 순회 종류

전위(먼저), 중위(중간에), 후위(나중에) 의 개념을 root를 기준으로 생각하면 된다.

• 전위 순회 (Preorder)
  전위 순회의 노드를 방문(처리 or 출력) 순서
  1. Root
  2. Left
  3. Right

전위순회. 출처 : https://www.crocus.co.kr/348

 

• 중위 순회 (Inorder)
  중위 순회의 노드를 방문(처리 or 출력) 순서

중위 순회. 출처 : https://www.crocus.co.kr/348

 

• 후위 순회 (Postorder)
  후위 순회의 노드를 방문(처리 or 출력) 순서
  1. Left
  2. Right
  3. Root

 

 

회고

개념적으로는 금방 이해되는 내용이지만, 트리의 구조가 확장 되었을때는 처리 순서를 한번에 인지하기가 쉽지가 않았다.

그래서 일단 저 위 그림에 나와있는 가장 단순한 구조(깊이가 1인 트리)의 트리에서 개념을 곱씹으며 한 깊이씩 생각해보니 나름 개념이 잡힌것 같다.

 

우선 중요한점은 
Right, Left의 개념은 현재 노드에서의 의미이다.

어떤 순회 방식이든,
Right, Left든 이동을 하고 나면 Right 혹은 Left 였던 노드가 Root가 되는것이다.

그 기준에서 또 Right, Left로 이동을 하는것이다.

마치 내일이란것이 개념적으로만 존재하고, 실제 내일을 살수 없는것처럼 (사람은 물리적으로 오늘만 살 수 있다)

 

그리고!

전위는 방문즉시 처리(출력)를 하지만,
중위와 후위는 더이상 방문할곳이 없을때 출력(처리)한다. (일단 깊이 들어가는것이다)

 이 부분이 조금 납득이 안갔는데, 어쨋든 root로 진입을 하는데 

중위와 후위에서 left부터 한다는것이 무슨 의미일까? 

생각을 해보았다.

중위와 후위가 left부터 순회 한다는것은

당연히 데이터를 접근할때 root 노드부터 방문을 하겠지만

실질적인 처리를 하지 않겠다는 것이다.

 

 

만약 트리에 있는 노드의 데이터를 출력하는 처리일때

아래와 같이 깊이가 1인 트리에서 시작하자면

중위 순회. 출처 : https://www.crocus.co.kr/348

당연히 root인 c부터 방문을 할것이다.

그러나 방문만 할뿐 실질적인 처리인 출력은 하지 않고 left로 가겠다는것이다.

그래서 노드의 방문 순서는

C -> L -> C -> R 이지만

 

출력은

L -> C -> R 이 되는것이다.

 

 

참조 : 

https://www.youtube.com/watch?v=_hxFgg7TLZQ 

https://youtu.be/QN1rZYX6QaA

 https://www.crocus.co.kr/348

이진 트리 순회(Traversal) (1)