이진 트리의 순회

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

- 스택, 큐, 덱 등은 데이터를 선형으로 저장하므로 자료에 순차적으로 순회하는 방법이 한 가지뿐

- 트리는 여러 가지 순서로 자료에 접근 가능

큐와 이진 트리의 순회 방법 비교

---

이진 트리 순회 방법

• 루트 방문: V
• 왼쪽 서브 트리 방문: L
• 오른쪽 서브 트리 방문: R

1. 전위 순회(preorder traversal): VLR

- 루트 → 왼쪽 서브 트리 → 오른쪽 서브 트리 순으로 방문

※ 왼쪽 서브 트리와 오른쪽 서브 트리도 하나의 이진 트리이므로, 전체 트리와 똑같은 방식으로 서브 트리를 방문

∴ 왼쪽 서브 트리의 루트 방문 → 왼쪽 서브 트리의 왼쪽 서브 트리 방문 → 왼쪽 서브 트리의 오른쪽 서브 트리 방문 → ...

∴ 모든 서브 트리에 대하여 같은 알고리즘 반복

- 노드 x가 NULL이면 더 이상 순환 호출을 하지 않음

- x의 데이터 출력

- x의 왼쪽 서브 트리를 순환 호출하여 방문

- x의 오른쪽 서브 트리를 순환 호출하여 방문

 

2. 중위 순회(inorder traversal): LVR

- 왼쪽 서브 트리 → 루트 → 오른쪽 서브 트리 순으로 방문

- 이하 위와 동일

- 노드 x가 NULL이면 더 이상 순환 호출을 하지 않음

- x의 왼쪽 서브 트리를 순환 호출하여 방문

- x의 데이터 출력

- x의 오른쪽 서브 트리를 순환 호출하여 방문

 

3. 후위 순회(postorder traversal): LRV

- 왼쪽 서브 트리 → 오른쪽 서브 트리 → 루트 순으로 방문

- 이하 위와 동일

- 노드 x가 NULL이면 더 이상 순환 호출을 하지 않음

- x의 왼쪽 서브 트리를 순환 호출하여 방문

- x의 오른쪽 서브 트리를 순환 호출하여 방문

- x의 데이터 출력

---

전/중/후위 순회 구현

- 순회 함수의 매개변수는 루트를 가리키는 포인터

- 왼쪽 또는 오른쪽 서브 트리를 방문하는 것은 전체 트리를 방문하는 것과 동일하므로, 매개변수만 변경하여 전체 트리의 방문 함수를 다시 한 번 호출(이때 매개변수는 서브 트리의 루트 노드 포인터)

---

전체 프로그램

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

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

//중위
void inorder(TreeNode* root) {
	if (root != NULL) {
		inorder(root->left);
		printf("[%d] ", root->data);	//출력으로 방문 표현
		inorder(root->right);
		
	}
}

//전위
void preorder(TreeNode* root) {
	if (root != NULL) {
		printf("[%d] ", root->data);
		preorder(root->left);
		preorder(root->right);
	}
}

//후위
void postorder(TreeNode* root) {
	if (root != NULL) {
		postorder(root->left);
		postorder(root->right);
		printf("[%d] ", root->data);
	}
}

TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 4, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode* root = &n6;

int main(void) {
	printf("중위=");
	inorder(root);
	printf("\n");

	printf("전위=");
	preorder(root);
	printf("\n");

	printf("후위=");
	postorder(root);
	printf("\n");

	return 0;
}

>>