이진 트리 순회

이번 포스트에서는 이진트리의 순회에 대해 다루도록 하겠습니다.

이진 트리 순회란?

: 트리에 있는 모든 노드를 한 번씩만 방문하는 것입니다. 또한 한 노드가 방문될 때 어떤 연산이 그 노드에 대해 수행됩니다. 만일 L, V, R이 한 노드에서 각각 왼쪽으로 이동, 노드 방문, 오른쪽으로 이동하는 것을 나타낸다면 LVR, LRV, VLR, VRL, RVL, RLV 등 6개의 순회 방법이 있을 수가 있습니다.

이진 트리 순회의 종류 : 

(1) Inorder (중위 순회, LVR)

: 더 이상 진행할 수 없을 때까지 왼쪽 방향으로 이동하여 내려간 다음, 그 노드를 방문하고 오른쪽 자식 노드로 이동한 뒤 계속합니다. 이때 오른쪽으로 이동할 수 없을 때에는 한 노드 뒤로 되돌아갑니다.

Inorder ex)

소스 코드 :

void inorder(treePointer ptr)
{
	if (ptr) {
    	inorder(ptr->leftChild);
        printf("%d", ptr->data);
        inorder(ptr->rightChild);
    }
}

출력 결과 : A / B * C * D + E

(2) Preorder (전위 순회, VLR)

: 노드를 먼저 하나 씩 방문면서 왼쪽 자식으로  이동합니다. 더 이상 계속할 수 없으면 오른쪽 자식을 방문합니다. 양쪽 다 방문했으면 다시 돌아가서 순회를 더 이상 할 수 없을 때까지 반복합니다.

Preorder ex)

소스 코드 :

void preorder(treePointer ptr)
{
	if (ptr) {
        printf("%d", ptr->data);
        preorder(ptr->leftChild);
        preorder(ptr->rightChild);
    }
}

출력 결과 : + * * / A B C D E

(3) Postorder (후위 순회, LRV)

:  더 이상 진행할 수 없을 때까지 왼쪽 방향으로 이동하여 내려간 다음, 오른쪽 자식 노드로 이동한 뒤 계속합니다. 이때 오른쪽으로 이동할 수 없을 때에는 노드를 방문하고 뒤로 되돌아갑니다.

Postorder ex)

소스 코드 : 

void postorder(treePointer ptr)
{
	if (ptr) {
        postorder(ptr->leftChild);
        postorder(ptr->rightChild);
        printf("%d", ptr->data);
    }
}

출력 결과 : A B / C * D * E +

 

*****추가*****

(4) IterInorder (반복 중위 순회)

소스 코드 : 

void iterInorder(treePointer node)
{
    int top = -1;
    treePointer stack[MAX_STACK_SIZE];
    
    for (;;) {
    	for (; node; node = node->leftChild)
        	push(node);
        node = pop();
        if (!node) 
        	break;
        printf("%d", node->data);
        node = node->rightChild;
    }
}

분석 : 

트리의 노드 수를 n이라고 할때 코드를 살펴보면 트리의 모든 노드들은 스택에 꼭 한 번씩 삽입됩니다. 그러므로 트리의 노드 수가 n이면 시간 복작도는 O(n)입니다.

(5) LevelOder (레벨 순서 순회)

소스 코드 : 

void levelOrder(treePointer ptr)
{
    int front = rear = 0;
    treePointer queue[MAX_QUEUE_SIZE];
    if (!ptr) return;
    addq(ptr);
    for (;;) {
        ptr = deleteq();
        if (ptr) {
            printf("%d", ptr->data);
            if(ptr->leftChild)
            	addq(ptr->leftChild);
            if(ptr->rightChild)
            	addq(ptr->rightChild);
        }
        else break;
   }
}