자료구조 - 트리 순회 방식

자주 헷갈리는 트리 순회 방식을 정리해놓으려 한다

 

그림 출처 위키백과

결론부터 얘기하면 각 단계에서 root 노드의 탐색 순서에 따라 순회 방식의 이름이 결정된다고 

생각하면 외우기 편하다

 

최초 root node인 F 노드부터 시작하는 것은 동일하다

 

각 순회 방식별 탐색 노드 순서는 아래와 같다

• 전위 순회(pre-order) : root -> left -> right
  
  F -> B -> A -> D -> C -> E -> G -> I -> H
• 중위 순회(in-order) : left -> root -> right
  
  A -> B -> C -> D -> E -> F -> G -> H -> I
  
  
• 후위 순회(post-order) : left -> right -> root
  
  A -> C -> E -> D -> B -> H -> I -> G -> F

기억해야 할 포인트는 내가 탐색해야 할 순서의 leaf 노드를 찾아서 깊게 들어가야 한다는 것이다