[자료구조] 트리의 순회 방법 - 전위, 중위, 후위, 레벨

트리의 순회 방법에 대해 알아보기에 앞서 트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다.
https://go2gym365.tistory.com/274

[자료구조] Tree & Binary Tree

---

1. 전위 순회 / PreOrder

• 순회 순서 : [ 루트 노드(부모 노드) > 왼쪽 노드 > 오른쪽 노드] 순서로 방문한다.

위의 그림에서 전위 순회한 결과 : [1 > 2 > 4 > 8 > 5 > 3 > 6 > 7 ] 

 

2. 중위 순회 / InOrder

• 순회 순서 : [ 왼쪽 노드  > 루트 노드(부모 노드) > 오른쪽 노드] 순서로 방문한다.

위의 그림에서 중위 순회한 결과 : [ 8 > 4 > 2 > 5 > 1 > 6 > 3 > 7 ] 

3. 후위 순회 / PostOrder

• 순회 순서 : [ 왼쪽 노드 > 오른쪽 노드 > 루트 노드(부모 노드) ] 순서로 방문한다.

위의 그림에서 후위 순회한 결과 : [  8 > 4 > 5 > 2 > 6 > 7 > 3 > 1 ] 

 

4. 레벨 순회 / Level Order

• 레벨 순회는 앞선 재귀로 구현하는 전위, 중위, 후위 순회와 다르게 Queue를 사용하여 구현한다.
• 순회 순서
  1. 루트 노드를 queue에 넣는다.
  2. 큐의 첫번째 있는 노드를 꺼내서 방문한다.
  3. 현재 노드의 왼쪽 노드를 검사해서 노드가 존재하면 큐에 넣는다.
  4. 현재 노드의 오른쪽 노드를 검사해서 노드가 존재하면 큐에 넣는다.
  5. 2~4의 과정을 큐가 빌 때까지 반복한다.

위의 그림에서 레벨 순회한 결과 : [  1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 ] 

---

이번 포스팅에서 소개한 트리의 4가지 순회 방법이 궁금하면 아래의 포스팅을 참고하면 도움이 될 것이다!

https://go2gym365.tistory.com/275

[자료구조] Linked list를 활용한 이진 트리 구현 :: C++

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐