트리 - 이진트리 순회

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다.

 

이전글: 트리-이진트리 정의/성질/분류/표현법

 

순회 traversal 

이진트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것

• 전위 순회(preorder traversal)
• 중위 순회(inorder traversal)
• 후위 순회(postorder traversal)

---

전위 순회 preorder traversal

루트 노드 → 왼쪽 서브트리 → 오른쪽 서브트리

 

이때 서브트리도 하나의 트리이므로, 그 트리 안에서 위의 과정을 또 거치면 된다.

쉽게 생각하면 왼쪽으로 계속 가다가 막히면 오른쪽으로 가는 방법이다.

예를 들어, 아래의 트리를 전위 순회 해보자.

A 방문
==> A의 왼쪽 서브트리 B 방문
==> B의 왼쪽 서브트리 D 방문
==> B의 오른쪽 서브트리 E 방문
==> A의 오른쪽 서브트리 C 방문
==> C의 왼쪽 서브트리 F 방문
==> 종료.

결론적으로는, A -> B -> D -> E -> C -> F 순으로 전위순회한다.

---

중위 순회 inorder traversal

루트 노드의 왼쪽 서브트리 → 루트 노드 → 루트 노드의 오른쪽 서브트리

 

이때 서브트리도 하나의 트리이므로, 그 트리 안에서 위의 과정을 또 거치면 된다.

쉽게 생각하면 가장 왼쪽부터 보고, 없으면 루트, 그 다음에 오른쪽을 보는 방식이다.

예를 들어, 아래의 트리를 중위 순회 해보자.

A의 왼쪽 서브트리 B로 이동
==> B의 왼쪽 서브트리 D로 이동
==> D 방문
==> D의 루트 B 방문
==> B의 오른쪽 서브트리 E 방문
==> B의 루트 A 방문
==> A의 오른쪽 서브트리 C로 이동
==> C의 왼쪽 서브트리 F로 이동
==> F 방문
==> F의 루트 C 방문
==> 종료.

결론적으로, D -> B -> E -> A -> F -> C 순으로 중위 순회한다.

---

후위 순회 postorder traversal

왼쪽 서브트리 → 오른쪽 서브트리 → 루트 노드

 

이때 서브트리도 하나의 트리이므로, 그 트리 안에서 위의 과정을 또 거치면 된다.

쉽게 생각하면 가장 왼쪽부터 보고, 그 다음에 오른쪽을, 마지막으로 루트를 보는 방식이다.

예를 들어, 아래의 트리를 후위 순회 해보자.

A의 왼쪽 서브트리 B로 이동
==> B의 왼쪽 서브트리 D로 이동
==> D 방문
==> B의 오른쪽 서브트리 E로 이동
==> E 방문
==> B 방문
==> A의 오른쪽 서브트리 C로 이동
==> C의 왼쪽 서브트리 F로 이동
==> F 방문
==> C의 오른쪽 서브트리가 공집합이므로 패스
==> C 방문
==> A 방문
==> 종료

결론적으로, D -> E -> B -> F -> C -> A 순으로 후위 순회한다.

---

위에서 살펴본 전위, 중위, 후위 순회는 정렬, 탐색 등
다양하게 이용되기 때문에 꼭 알고 넘어가야 하는 내용이다.

모든 순회의 핵심은 루트 노드의 서브트리 또한 이진트리이므로,
전위,중위,후위 순회 모두 서브트리에 대해 동일한 과정을 수행하면 된다는 것이다.
서브트리의 서브트리에도 마찬가지이다.

---

c언어로 구현하고 결과 확인해보기

계속 예시로 사용했던 아래의 그래프에 대해 전위/중위/후위 순회를 시행해보자.

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
	char data;
	struct TreeNode* left, * right;
} TreeNode;

TreeNode n0 = { 'D', NULL, NULL};
TreeNode n1 = { 'E', NULL, NULL };
TreeNode n2 = { 'B', &n0, &n1};
TreeNode n3 = { 'F', NULL, NULL};
TreeNode n4 = { 'C', &n3, NULL };
TreeNode n5 = { 'A', &n2, &n4};
TreeNode* root = &n5;

// 전위 순회
void preorder(TreeNode* root)
{
	// 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
	if (root != NULL) {
		printf("%c -> ", root->data);
		preorder(root->left);
		preorder(root->right);
	}
}
// 중위 순회
void inorder(TreeNode* root) 
{
	// 왼쪽 서브트리 -> 루트 노드 -> 오른쪽 서브트리
	if (root != NULL) {
		inorder(root->left);
		printf("%c -> ", root->data);
		inorder(root->right);
	}
}
// 후위 순회
void postorder(TreeNode* root)
{
	// 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 노드
	if (root != NULL) {
		postorder(root->left);
		postorder(root->right);
		printf("%c -> ", root->data);
	}
}
int main()
{
	printf("전위 순회\n");
	preorder(root);
	printf("\n");
	printf("중위 순회\n");
	inorder(root);
	printf("\n");
	printf("후위 순회\n");
	postorder(root);
	printf("\n");
	return 0;
}

결과

 

추가적으로 순회에는 이 외에도 반복문을 이용한 순회, 레벨 순회가 있다.

이에 대한 설명은 다음 글에서 진행된다.