Binary Tree의 순회

Tree의 순회는 트리에서 각각의 노드를 정확히 한 번만 방문하는 과정이다. Linked list나 array와 같은 선형 자료 구조는 논리적으로 한 가지의 순회 방법만이 존재하지만, 트리의 순회에는 많은 방법이 존재한다. 순회는 모든 n-ary tree에 대해 일반화될 수 있으나, 가장 자료가 많고 일반적인 binary tree의 순회에 대해서 알아보도록 하겠다.

순회

tree 내부의 tree를 sub-tree라고 부른다. 순회에는 이러한 sub-tree 개념이 등장한다.

전위(preorder) 순회(root-left-right)

• 현재 node를 방문한다.
• 왼쪽 sub-tree를 전위 순회한다.
• 오른쪽 sub-tree를 전위 순회한다.

전위 우선 순회는 깊이 우선 순회(depth-first traversal)라고도 한다. 전위 표기법에서 자주 사용된다.

중위(inorder) 순회(left-root-right)

• 왼쪽 sub-tree를 중위 순회한다.
• 현재 node를 방문한다.
• 오른쪽 sub-tree를 중위 순회한다.

후위(postorder) 순회(left-right-root)

• 왼쪽 sub-tree를 후위 순회한다.
• 오른쪽 sub-tree를 후위 순회한다.
• 현재 node를 방문한다.

왼쪽 sub-tree 순회-오른쪽 sub-tree 순회라는 순서는 고정이고, root node를 언제 방문하는지에 따라 전위, 중위, 후위로 나뉜다. sub-tree들을 동일한 order로 순회하므로 재귀적인 특성이 강하고, 실제로 코드에 옮길 때도 재귀함수를 사용한다.

sub-tree를 순회하는 구조라 순회의 대상이 계속해서 바뀌기 때문에 조금 헷갈릴 수 있으나, 아래의 사진을 보면 이해에 조금 도움이 될 수도 있다.

레벨 순서(level-order) 순회

이는 sub-tree 개념이 들어가지 않고, 낮은 level부터 왼쪽에서 오른쪽 방향으로 순회한다. 너비 우선 순회(breadth-first traversal)라고도 한다.

위 tree를 전/중/후위, 레벨 순서 순회 각각의 방식으로 순회하면,

• 전위 순회 : F-B-A-D-C-E-G-I-H
• 중위 순회 : A-B-C-D-E-F-G-H-I
• 후위 순회 : A-C-E-D-B-H-I-G-F
• 레벨 순서 순회 : F-B-G-A-D-I-C-E-H