[Data Structure] 이진 트리 순회

목차

• 이진 트리 순회방법
  • ① 전위순회 (preorder traversal) : VLR
  • ② 중위순회 (inorder traversal) : LVR
  • ③ 후위순회 (postorder traversal) : LRV
• ※ Example

이진 트리 순회방법

- 루트 방문 : V

- 왼쪽 서브트리 방문 : L

- 오른쪽 서브트리 방문 : R

• 루트를 언제 방문하느냐에 따라 전위(1), 중위(2), 후위(3)로 구분

 

① 전위순회 (preorder traversal) : VLR

1. 루트 노드 방문 (V)
2. 왼쪽 서브트리 방문 (L)
3. 오른쪽 서브트리 방문 (R)

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

 

② 중위순회 (inorder traversal) : LVR

1. 왼쪽 서브트리 방문 (L)
2. 루트 노드 방문 (V)
3. 오른쪽 서브트리 방문 (R)

void inorder(treenode* root) { // LVR 순
	if (root != NULL) {
		inorder(root->left);
		printf("[%d] ", root->data);
		inorder(root->right);
	}
}

 

③ 후위순회 (postorder traversal) : LRV

1. 왼쪽 서브트리 방문 (L)
2. 오른쪽 서브트리 방문 (R)
3. 루트 노드 방문 (V) 

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

VLR / LVR / LRV

 

※ Example

#include <stdio.h>
#include <stdlib.h>
// 이진트리 순회 (전위, 중위, 후위)
 
typedef int element;
typedef struct treenode {
	element data;
	struct treenode* left;
	struct treenode* right;
}treenode;
 
treenode n1 = { 8, NULL, NULL };
treenode n2 = { 39, NULL, NULL };
treenode n3 = { 85, NULL, NULL };
treenode n4 = { 2, NULL, NULL };
treenode n5 = { 15, &n1, &n2 };
treenode n6 = { 21, &n3, &n4 };
treenode n7 = { 30, &n5, &n6 };
treenode* root = &n7; // 트리의 루트 노드(n7)를 가리키는 root 포인터
 
//           30
//    15          21
// 8     39    85    2
 
// 전위순회 : 30 15 8 39 21 85 2
// 중위순회 : 8 15 39 30 85 21 2
// 후위순회 : 8 39 15 85 2 21 30
 
void preorder(treenode* root) { // VLR 순
	if (root != NULL) {
		printf("[%d] ", root->data);
		preorder(root->left);
		preorder(root->right);
	}
}
 
void inorder(treenode* root) { // LVR 순
	if (root != NULL) {
		inorder(root->left);
		printf("[%d] ", root->data);
		inorder(root->right);
	}
}
 
void postorder(treenode* root) { // LRV 순
	if (root != NULL) {
		postorder(root->left);
		postorder(root->right);
		printf("[%d] ", root->data);
	}
}
 
int main(void) {
	printf("전위 순회 >> ");
	preorder(root);
	printf("\n");
 
	printf("중위 순회 >> ");
	inorder(root);
	printf("\n");
 
	printf("후위 순회 >> ");
	postorder(root);
	printf("\n");
}