[자료구조] 이진 트리 순회

 

이진 트리 순회

이진 트리를 순회한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미합니다. 이진 트리에서 순회가 중요한 이유는, 순회 순서에 따라 기대할 수 있는 결과값이 다르기 때문입니다.

 

이진 트리 순회 방법

전위, 중위, 후위 총 3가지의 방법이 있습니다. 이는 루트와 왼쪽 서브트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분됩니다.

만약 루트를 방문하는 작업을 $V$라 하고, 왼쪽 서브트리 방문을 $L$, 오른쪽 서브트리 방문을 $R$이라고 한다면 다음과 같이 3가지 방법을 생각할 수 있습니다.

이진 트리의 순회방법
전위 순회(preorder traversal): VLR
중위 순회(inorder traversal): LVR
후위 순회(postorder traversal): LRV

 

각각의 서브트리들도 같은 방식으로 방문하게 됩니다. 전위 순회라면 서브트리에 들어 있는 노드들도 VLR의 순서대로 순회됩니다.

트리 순회 알고리즘은 순환 기법을 사용합니다. 이 방법으로 하지 않으면 트리를 순회하는 알고리즘을 만들 수 없습니다. 전체 트리나 서브 트리나 구조는 동일하고, 문제의 크기가 작아지므로 순환을 적용할 수 있는 것입니다.

 

전위 순회

방문 순서: 루트 → 왼쪽 → 오른쪽

 

전위 순회. 방문 순서는 숫자로 적혀있다.

 

중위 순회

방문 순서: 왼쪽 → 루트 → 오른쪽

중위 순회. 방문 순서는 숫자로 적혀있다.

 

후위 순회

방문 순서: 왼쪽 → 오른쪽 → 루트

 

후위 순회. 방문 순서는 숫자로 적혀있다.

 

전위, 중위, 후위 순회 구현

// 전위 순회
void preorder(TreeNode *root) {
	if(root != NULL) {
		printf("[%d]", root -> data); // 노드 방문
		preorder(root -> left); // 왼쪽 서브트리 방문
		preorder(root -> right); // 오른쪽 서브트리 방문
	}
}

// 중위 순회
void inorder(TreeNode *root) {
	if(root != NULL) {
		inorder(root -> left); // 왼쪽 서브트리 방문
		printf("[%d]", root -> data); // 노드 방문
		inorder(root -> right); // 오른쪽 서브트리 방문
	}
}

// 후위 순회
void postorder(TreeNode *root) {
	if(root != NULL) {
		postorder(root -> left); // 왼쪽 서브트리 방문
		postorder(root -> right); // 오른쪽 서브트리 방문
		printf("[%d]", root -> data); // 노드 방문
	}
}

 

레벨 순회

각 노드들을 레벨 순으로 검사하는 순회 방법입니다. 이 순회는 큐를 사용합니다.

 

큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식들을 큐에 삽입하는 것을 노드가 없을 때까지 반복합니다.

 

void level_order(TreeNode *ptr) {
    QueueType q;
    init_queue(&q); // 큐 초기화

    if(ptr == NULL) return;

    enqueue(&q, ptr);

    while(!is_empty(&q)) {
        ptr = dequeue(&q);
        printf(" [%d] ", ptr->data);
        if(ptr->left) {
            enqueue(&q, ptr->left);
        }
        if(ptr->right) {
            enqueue(&q, ptr->right);
        }
    }
}