이진 트리 순회(Traversal) (1)

이진트리를 조사하기 위해서는 마음대로 찾아도 되지만, 정형화 된 방법들이 있다.

이것을 순회라고 하는데 그중 가장 많이 쓰이는 순회가 전위 순회, 중위 순회, 후위 순회가 있다.

높이가 2 이상인 트리 또한 같은 방법으로 순회를 하면 된다.

이 과정을 하나하나 표현 할 필요 없이, 재귀(Recursive)형태로 순회를 구성하면 높이에 무관한 순회를 할 수 있게 된다. 

중위 순회 이진 트리의 예

중위 순회의 추상적 관점으로의 단계 해석

1단계 왼쪽 서브 트리의 순회를 시작한다.

2단계 루트 노드를 방문한다.

3단계 오른쪽 서브 트리의 순회를 시작한다.

중위 순회의 간단한 코드

void InorderTraverse(BTreeNode *bt)
{
    InorderTraverse(bt->left);
    printf("%d \n", bt->data);
    InorderTraverse(bt->right);
}

왼쪽을 들리고 재귀로 형성되니 왼쪽으로 계속 돌게 될것이다.

그다음 다 돌고나면 자신의 data를 print하고

마지막으로 오른쪽으로 도는데 오른쪽으로 가자마자 왼쪽에 노드가 또 있다면 다시 왼쪽부터 계속돌게 되는 재귀형식이다.

(이 코드는 불완전한 코드(재귀의 탈출 조건을 제대로 하지 않았다.)이지만, 이러한 형식으로 이루어 지다는 것을 알아두자.)