[ C언어 ] 자료구조_트리순회

저번에는 트리 자료구조의 구조를 알아보았습니다.

이번에는 이진트리를 순회하는 종류와 방법을 알아보겠습니다.

 

이전에 알아본 선형 자료구조들은 순회방법이 한 가지였습니다. 하지만 트리는 비선형 자료구조이기 때문에 순회방법이 여러 가지가 있습니다.

 

1. 순회방법

대표적인 순회방법은 3가지입니다.

1. 전위순회(VLR)

2. 중위순회(LVR)

3. 후위순회(LRV)

이 3가지 순회방법은 루트노드를 중심으로 왼쪽 서브트리 오른쪽 서브트리 중 어느 곳을 먼저 방문할 것인지를 의미합니다.

 

 

위 트리에서 3가지 방식으로 순회를 해보겠습니다.

1. 전위순회: A -> B -> D -> E -> C -> F -> G

2. 중위순회: D -> B -> E -> A -> F -> C -> G

3. 후위순회: D -> E -> B -> F -> G -> C -> A

 

그러면 이런 순회는 어떻게 할 수 있을까요?

 

이진트리 구조는 순환적인 구조를 가지고 있습니다.

즉 이 구조는 순환함수 재귀함수를 사용하면 쉽게 구현할 수 있습니다.

 

2. 순회 구현

먼저 노드를 구현할 구조체를 만들어 줍니다.

typedef char element;

typedef struct Tree {
	element data;
	struct Tree* left;
	struct Tree* right;

}Tree;

 

다음으로 순회할 함수를 만들어 줍니다.

void preorder(Tree* tree)
{
	if (tree != NULL) {
		printf("[%c] ", tree->data);
		preorder(tree->left);
		preorder(tree->right);
	}
}

void inorder(Tree* tree)
{
	if (tree != NULL) {
		inorder(tree->left);
		printf("[%c] ", tree->data);
		inorder(tree->right);
	}
}

void postorder(Tree* tree)
{
	if (tree != NULL) {
		postorder(tree->left);
		postorder(tree->right);
		printf("[%c] ", tree->data);
	}
}

코드를 보면 조건문으로 트리가 NULL 이 아니라면 본인을 다시 호출하는 구조로 되어있습니다.

이때 다른 점은 함수 내부기준으로 루트노드에 값을 언제 확인하는지 순서가 다르다는 것입니다.

 

3. 순회방법 정리

그러면 위 순회방법들은 어떤 경우에 사용하는 게 좋을까요?

만약 순서 상관없이 모든 노드를 순회하기만 하면 된다 라면 어떤 방식을 사용해도 상관없지만

하위 디렉터리 개수나 크기등을 측정해야 한다면 후위순회를 사용해야 하겠죠

 

이상으로 이진트리 순회방법을 알아보았습니다. 감사합니다.