이진트리 전위순회(preorder traversal) 이해하기

https://mymajoriscs.tistory.com/1

자료구조 트리(Tree) 이해하기

 

이전글에서 트리의 개념과 종류를 소개하면서, 이진트리(Binary)의 기본개념에 대해서 설명했었다.

이진트리를 순회하는 방법으로는 전위순회, 중위순회, 후위순회, 레벨순회가 있다.

그중에서도 이번글에서는 전위순회(preorder)에 대해서 다뤄보고자 한다.

 

 

순회경로를 이해하는 방법은 다양하지만 대표적으로 2가지 방법이 있다.

전위순회(Preorder Traversal)의 본질은 아래와 같은 순서로 방문한다는 것이지만, 이를 설명하는 방식은 다양하다.

"현재 노드 → 왼쪽 → 오른쪽" 순으로 순회

 

1) Recursive 형태의 접근법

 

 위 트리의 경우 A가 ROOT노드이므로 A부터 시작해서,

 

A방문 → B방문(왼쪽)→D방문(왼쪽)→H방문(왼쪽)→H,D,B는 이미 방문

→E방문(오른쪽)→I방문(왼쪽)→I,E는 이미 방문

→J방문(오른쪽)→J,E,B,A이미 방문

→C방문(오른쪽)→F방문(왼쪽)→F,C이미 방문

→G방문(오른쪽)→K방문(오른쪽)→K,G,C,A 이미 방문

→모두방문하였으므로 종료

• 순회경로 : A-B-D-H-E-I-J-C-F-G-K

 

 

2) SubTree 분할식 접근

 아래 절차와 같이 Subtree관점에서 현재노드 방문→왼쪽 Subtree → 오른쪽 Subtree 순서로 이해해서 분할해서 처리하다보면 위와 같이 A-B-D-H-E-I-J-C-F-G-K 경로를 얻게 된다.

이진트리 순회의 응용 

- 아래와 같은 수식트리를 순회하는 방식에 따라 표기법이 나뉜다. 이를 각각 전위 표기법(prefix notation), 중위 표기법(infix notation), 후위 표기법(postfix notation)이라고 한다.

- 전위표기법 결과 : -*AB/CD

- 표기법(notation)을 활용해서 계산기로 만들기 위해서는 Stack을 활용하여야 한다.

 

 

 

전위순회(Preorder Traversal)에 대해서 이론적인 순서를 설명했는데, 다음글에서 코드관점에서 전위순회를 구현해보려고 한다.