[C언어와 함께 자료구조를] 이진트리 순회 (Binary Tree Traverse)

트리(Tree)구조는 배열과 리스트 처럼 분명한 순회 순서(Traversal Order)를 갖지 않고 여러개의 순회 순서를 정의 할 수 있습니다. 트리(Tree)의 모든 노드들을 한 번씩 중복없이 순회하는 방법 4가지에 대해 이야기 해보려 합니다.

트리 순회하는 방법은 먼저 루트(Root)를 먼저 타는 방법 (전위 순회 : Preorder traverse), 루트를 중간에 타는 방법 (중위 순회 : Inorder Traverse), 루트를 나중에 타는 방법 (후위 순회 : Postorder Traverse), 마지막으로 층별로 타는 방법 (층별 순회 : Level order Traverse)등이 있습니다. 트리를 순회하는 방법 (앞 3가지)을 C언어로 구현하려면 재귀호출(Recursive Call)을 이용해야 합니다. 재귀호출에 대해서는 알고리즘 파트에서 언급하도록 하겠습니다.

다음과 같은 트리가 있다고 했을 때, 각각 방법으로 어떻게 순회하는지 알아보겠습니다. 

이진트리

트리 순회 구현은 깊이(Depth)에 비례한 호출 스택(Stack)공간 (앞의 3가지 순회), 또는 큐(Queue)가 필요합니다. 왜냐면 이전 포스팅에서 다른 트리 구조체를 다음과 같이 정의 했기 때문에 자식의 입장에서는 부모에 대한 정보를 알 수 없기 때문에 추가 자료구조를 같이 사용합니다.

 

typedef struct _node 
{ 
    char key; 
    struct _node *left; /* 왼쪽 자식 노드 */ 
    struct _node *right; /* 오른쪽 자식 노드 */ 
} node;

node *head, tail;

 

1. 전위 순회 (Preorder Traverse)

void preorder(node *t)
{
    if (t != tail) {
    	visit(t);			/* ① 루트를 먼저 방문한다. */
        preorder(t->left);		/* ② 왼쪽 서브트리(Subtree)를 방문한다. */
        preorder(t->right);		/* ③ 오른쪽 서브트리(Subtree)를 방문한다. */
    }
}

위 이진트리에서 전위순회를 손으로 따라 해보면 A-B-D-G-H-E-C-F-I 순으로 출력됨을 알 수 있습니다.

 

2. 중위 순회 (Inorder Traverse)

void inorder(node *t)
{
    if (t != tail) {
        inorder(t->left);		/* ① 왼쪽 서브트리(Subtree)를 방문한다. */
        visit(t);			/* ② 루트를 먼저 방문한다. */
        inorder(t->right);		/* ③ 오른쪽 서브트리(Subtree)를 방문한다. */
    }
}

 

위 이진트리에서 중위순회를 손으로 따라 해보면 G-D-H-B-E-A-C-I-F 순으로 출력됨을 알 수 있습니다.

 

3. 후위 순회 (Postorder Traverse)

void postorder(node *t)
{
    if (t != tail) {
        postorder(t->left);		/* ① 왼쪽 서브트리(Subtree)를 방문한다. */
        postorder(t->right);		/* ② 오른쪽 서브트리(Subtree)를 방문한다. */
        visit(t);			/* ③ 루트를 먼저 방문한다. */
    }
}

위 이진트리에서 후위순회를 손으로 따라 해보면 G-H-D-E-B-I-F-C-A 순으로 출력됨을 알 수 있습니다.

 

4. 층별 순회 (Level order Traverse) 

void levelorder(node *t)
{
    put (t);			/* 1. 큐에 루트노드(Root Node)를 put한다. */
    while (!is_queue_empty()) {	/* 2. 큐가 비어있지 않으면 */
        t = get();		/* 2-1. 큐에서 get하여 t에 대입, t를 방문 */
        visit (t)
        if (t->left != tail)	/* 2-2. t의 왼쪽 자식이 있으면 큐에 put */
        	put(t->left);
        if (t->right != tail)	/* 2-3. t의 오른쪽 자식이 있으면 큐에 put */
        	put(t->right);
    }
}

층별 순회에서는 큐(Queue)를 사용했

위 이진트리에서 층별순회를 손으로 따라 해보면 A-B-C-D-E-F-G-H-I 순으로 출력됨을 알 수 있습니다.

 

지금까지 트리순회(Tree Traverse)에 대한 4가지 방법에 대해 간단하게 다뤄봤는데요, 뭔가 미흡한 것 같죠. 당연한 이유가 트리 자료구조는 다른 자료구조/알고리즘에서 지속적으로 다루며 새로 배우는 경우가 많기 때문입니다.