이진트리의 순회 (Binary Tree Traversal)

이진검색트리같은 이진트리(Binary tree) 구조의 자료구조에서 검색, 출력 등의 이유로 전체 노드들을 방문(visit)하는 것을 순회(traversal)이라고 합니다.

아시다 싶이 이진트리의 구조는 최상위에 루트(root)가 존재하고 좌측에는 왼쪽 서브트리가 , 오른쪽에는 오른쪽 서브트리의 모양을 갖습니다.

대표적인 이진트리 순회 방법에 3가지의 방법이 있습니다. 루트의 방문 순서에 따라 구분이 됩니다.

1. 전위 순회 (Preorder Traversal)

Root -> Left Tree -> Right Tree   ( 루트를 제일 처음에 방문 )

2. 중위 순회 (Inorder Traversal)

Left Tree -> Root -> Right Tree   ( 루트를 중간에 방문 )

3. 후위 순회 (Postorder Traversal)

Left Tree -> Right Tree -> Root   ( 루트를 제일 마지막에 방문 )

가장 흔히 볼 수 있는 이진검색트리(Binary Search Tree) 에서의 검색목적의 전위순회 슈도코드를 살펴보겠습니다.

전위, 중위, 후위의 변환은 코드의 순서 변경 차이 밖에 없습니다.

treeSearch(t, x)

{

/* t : 트리의 루트 노드 , x : 검색하고자 하는 키 */

if(t=NIL or key[t] = x) then return t;      // root 탐색

if(x < key[t])

then return treeSearch(left[t], x);    // 왼쪽 서브트리 탐색

else return treeSearch(right[t], x);   // 오른쪽 서브트리 탐색

}