January 17, 2024 16 min to read

자료구조(10) - 트리의 구현 기초와 재귀 함수를 통한 순회

트리의 기본 구현과 순회

🔚 짧게 하는 복습

✅ 1. 이진 트리의 정의와 성질을 안다.

✅ 2. 완전 이진 트리의 정의와 성질을 안다.

✅ 3. 포화 이진 트리의 정의와 성질을 안다.

✅ 4. 이진 검색 트리의 정의와 성질을 안다.

혹시 기억이 안 난다면, 다시 돌아가자

최근 2개의 강의가 너무 이론적인 것만 다루어서 조금 지루했을 것이다.

이번 시간부터는 다시 ADT 위주로 구현 연습을 해보겠다.

트리의 구현 기초

트리 구현의 기본 단위는 노드로, 연결리스트의 노드와 유사하다. (사실 단일 연결리스트도 skewed-tree로 특별한 하나의 트리이기 때문이다.)

다만, 자식이 여러 노드일 수 있다는 점이 다르다.

typedef struct Node* treePointer;

typedef struct Node {
	int data;               // 자료 값
    treePointer child1;       // 첫째 자식 노드를 가리키는 포인터
	treePointer child2;       // 둘째 자식 노드를 가리키는 포인터
    ...
} node;                     // 노드

트리의 특성상 노드의 추가나 제거가 상당히 까다롭다.

그래서 우선은 가장 일반적인 이진 트리(binary tree)에 대해서만 다루어보겠다.

또, 작은 서브 트리를 만들고 그것들은 연결하여 큰 트리로 연결하는 방법으로 임시 구현해보겠다.

위 사진의 트리를 구현해보겠다

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

typedef struct Node* treePointer;

typedef struct Node {
	char data;               // 자료 값
	treePointer left_child;       // 첫째 자식 노드를 가리키는 포인터
	treePointer right_child;       // 둘째 자식 노드를 가리키는 포인터
} node;                     // 노드


// + 노드를 만드는 함수
treePointer make_node(char data) {
	treePointer new_node = (treePointer)malloc(sizeof(node));
	new_node->data = data;
	new_node->left_child = NULL;
	new_node->right_child = NULL;

	return new_node;
}

int make_tree(treePointer root, treePointer left_tree, treePointer right_tree) {
	root->left_child = left_tree;
	root->right_child = right_tree;

	return 0; //연결해서 반환하는 함수
}


int main(void) {
	treePointer A = make_node('A');
	treePointer B = make_node('B');
	treePointer C = make_node('C');
	treePointer D = make_node('D');
	treePointer E = make_node('E');
	treePointer F = make_node('F');
	treePointer G = make_node('G');
	treePointer H = make_node('H');
	treePointer I = make_node('I');
	treePointer J = make_node('J');
	treePointer K = make_node('K');
	treePointer L = make_node('L');

	make_tree(D, H, I);
	make_tree(E, J, K);
	make_tree(F, L, NULL);
	make_tree(B, D, E);
	make_tree(C, F, G);
	make_tree(A, B, C);
}

트리를 구현했는데, 코드를 보면 뭔가 찝찝하다.

너무 반복적인 작업이 많고, 지저분한 느낌이다.

재귀 함수란?

우리는 이 작업을 조금 깔끔하게 하려고, 재귀 함수라는 개념을 사용할 것이다.

재귀 함수란 함수 안에서 자기 자신을 호출하는 함수로, 가장 쉬운 예제로는 이런 것이 있다.

int factorial(int n){
    if(n == 1){
        return 1;
    }

    return n * factorial(n-1);
}

팩토리얼, 즉 1부터 n까지 곱을 구하는 함수이다.

팩토리얼 함수의 특징은 어떤 수의 팩토리얼을 f(n)이라고 하면,

f(1) = 1

f(2) = 2*1 = 2 * f(1)

f(3) = 3 * 2 * 1 = 3 * f(2)

…

f(n) = n * f(n-1)이라는 관계가 나온다.

이를 거꾸로 이용하면, f(1)일 때만 1이라는 탈출 조건을 주고 나머지 경우에는 반복된 함수 호출로 해결할 수 있는 것이다.

factorial(3)을 호출하면 factorial(2)가 호출되고, factorial(2)을 호출하면 factorial(1)이 호출된다.

그럼 그 결괏값이 순서대로 다시 대입되어, factorial(1)에서는 1이 반환, factorial(2)에서는 2* factorial(1)인 2가 반환, 최종적으로는 3* factorial(2)인 3 * 2, 6이 반환되는 것이다.

이렇게 구조적으로 같거나 비슷한 부분 문제가 반복된다면, 재귀 함수가 강력하게 쓰일 수 있다.

트리에서의 재귀 함수

우리가 재귀 함수로 코드를 간결하게 만들 수 있다고 한 이유는, 모든 트리는 1개 이상의 서브 트리로 나눌 수 있기 때문이다.

즉, 트리 전체를 한 번에 다루는 것이 아니라 서브 트리들로 나누고 작은 단위부터 다루는 것이다.

이렇게 구조적으로 반복되는 큰 문제를 작은 문제들로 나누어 다루는 방법을 분할 정복한다.

우리가 처음 만든 코드는 서브 트리부터 만들어서 루트로 연결하는 방법을 사용했지만, 지금부터 이용할 코드는 재귀 함수를 통해 루트에서부터 리프 노드로 내려가는 방법을 구현할 것이다.

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

typedef struct Node* treePointer;

typedef struct Node {
	char data;               // 자료 값
	treePointer left_child;       // 첫째 자식 노드를 가리키는 포인터
	treePointer right_child;       // 둘째 자식 노드를 가리키는 포인터
} node;                     // 노드


// + 노드를 만드는 함수
treePointer make_node(char data) {
	treePointer new_node = (treePointer)malloc(sizeof(node));
	new_node->data = data;
	new_node->left_child = NULL;
	new_node->right_child = NULL;

	return new_node;
}

void make_tree(treePointer root, char data, char adj[][2]) {
	int index = data - 'A'; //아스키 코드를 통해 배열의 row 인덱스를 구함
	char left_data = adj[index][0];
	char right_data = adj[index][1];

	if (root == NULL) {
		return; // 탈출 조건
	}

	if (left_data != '#') { // 첫째 자식 노드가 있다면
		root->left_child = make_node(left_data);
		// 할당해서 붙임

		make_tree(root->left_child, left_data, adj);
		// left_child를 루트로 하는 서브 트리에서 다시 함수 호출
	}
	if (right_data != '#') { //둘째 자식 노드가 있다면
		root->right_child = make_node(right_data);
		// 할당해서 붙임

		make_tree(root->right_child, right_data, adj);
		// right_child를 루트로 하는 서브 트리에서 다시 함수 호출
	}

	return ;
}


int main(void) {
	char adj[12][2] = {
	{'B', 'C'}, {'D', 'E'}, {'F','G'}, {'H', 'I'},
	{'J', 'K'}, {'L', '#'}, {'#', '#'}, {'#', '#'},
	{'#', '#'}, {'#', '#'}, {'#', '#'}, {'#', '#'}
	}; // 트리의 자식 정보를 순서대로 저장한다.(없으면 '#')

	treePointer root = make_node('A');

	make_tree(root, 'A', adj);
}

이 코드는 루트 노드인 A에서 시작해서, 생기는 작은 문제를 순서대로 해결해간다.

그러다가 리프 노드를 만나면 탈출하고, 다시 호출된 함수로 복귀한다.

최종적으로 처음 호출한 함수가 종료되면, 트리가 성공적으로 완성된다.

처음 코드처럼 작은 문제부터 해결해서 최종적인 문제를 해결하는 방법을 바텀 업(bottom-up)

두 번째처럼 최종적인 문제를 해결하는 과정에 만나는 작은 문제를 순서대로 해결하는 방법을 탑 다운(top-down)이라고 한다.

트리에서는 보통 탑다운을 이용한 함수를 많이 사용한다.

재귀 함수를 통한 순회

트리에서의 순회는 3가지 방법으로 나뉜다.

3가지 방법 모두 루트에서 시작해서 왼쪽 리프 노드부터 오른쪽 리프 노드로 순회하는 것은 같다.

하지만 출력을 언제 하냐에 따라 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 나뉜다.

이를 각각 VLR, LVR, LRV 순회라고도 한다.

그 이유는 코드의 순서가 V(value 출력), L(left child를 루트로 하는 서브 트리 호출), L(right child를 루트로 하는 서브 트리 호출) 3가지의 조합으로 나타나기 때문이다.

아래 코드를 직접 보자.

void preorder(treePointer root) {// 전위 순회(preorder, VLR)
	if (root == NULL) {
		return;
	}
	printf("%c ", root->data); //V
	preorder(root->left_child); // L
	preorder(root->right_child); // R
}

void inorder(treePointer root) {// 중위 순회(inorder, LVR)
	if (root == NULL) {
		return;
	}
	inorder(root->left_child); // L
	printf("%c ", root->data); //V
	inorder(root->right_child); // R
}

void postorder(treePointer root) {// 후위 순회(postorder, LRV)
	if (root == NULL) {
		return;
	}
	postorder(root->left_child); // L
	postorder(root->right_child); // R
	printf("%c ", root->data); //V
}

오늘 한 코드 모두 정리

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

typedef struct Node* treePointer;

typedef struct Node {
	char data;               // 자료 값
	treePointer left_child;       // 첫째 자식 노드를 가리키는 포인터
	treePointer right_child;       // 둘째 자식 노드를 가리키는 포인터
} node;                     // 노드


// + 노드를 만드는 함수
treePointer make_node(const char data) {
	treePointer new_node = (treePointer)malloc(sizeof(node));
	new_node->data = data;
	new_node->left_child = NULL;
	new_node->right_child = NULL;

	return new_node;
}

void make_tree(treePointer root, const char data, char adj[][2]) {
	int index = data - 'A'; //아스키 코드를 통해 배열의 row 인덱스를 구함
	char left_data = adj[index][0];
	char right_data = adj[index][1];

	if (root == NULL) {
		return; // 탈출 조건
	}

	if (left_data != '#') {
		root->left_child = make_node(left_data);
		make_tree(root->left_child, left_data, adj);
	}
	if (right_data != '#') {
		root->right_child = make_node(right_data);
		make_tree(root->right_child, right_data, adj);
	}

	return ;
}

int make_tree(treePointer root, treePointer left_tree, treePointer right_tree) {
	root->left_child = left_tree;
	root->right_child = right_tree;

	return 0; //연결해서 반환하는 함수
}


treePointer make_tree2(){
	treePointer A = make_node('A');
	treePointer B = make_node('B');
	treePointer C = make_node('C');
	treePointer D = make_node('D');
	treePointer E = make_node('E');
	treePointer F = make_node('F');
	treePointer G = make_node('G');
	treePointer H = make_node('H');
	treePointer I = make_node('I');
	treePointer J = make_node('J');
	treePointer K = make_node('K');
	treePointer L = make_node('L');

	make_tree(D, H, I);
	make_tree(E, J, K);
	make_tree(F, L, NULL);
	make_tree(B, D, E);
	make_tree(C, F, G);
	make_tree(A, B, C);

	return A;
}


void preorder(treePointer root) {// 전위 순회(preorder, VLR)
	if (root == NULL) {
		return;
	}
	printf("%c ", root->data); //V
	preorder(root->left_child); // L
	preorder(root->right_child); // R
}

void inorder(treePointer root) {// 중위 순회(inorder, LVR)
	if (root == NULL) {
		return;
	}
	inorder(root->left_child); // L
	printf("%c ", root->data); //V
	inorder(root->right_child); // R
}

void postorder(treePointer root) {// 후위 순회(postorder, LRV)
	if (root == NULL) {
		return;
	}
	postorder(root->left_child); // L
	postorder(root->right_child); // R
	printf("%c ", root->data); //V
}



int main(void) {
	char adj[12][2] = {
	{'B', 'C'}, {'D', 'E'}, {'F','G'}, {'H', 'I'},
	{'J', 'K'}, {'L', '#'}, {'#', '#'}, {'#', '#'},
	{'#', '#'}, {'#', '#'}, {'#', '#'}, {'#', '#'}
	};

	treePointer root = make_node('A'); // 탑 다운으로 트리 구현
	treePointer root2 = make_tree2(); // 바텀 업으로 트리 구현

	make_tree(root, 'A', adj);

	printf("preorder : \n");
	preorder(root);
	printf("\n");
	preorder(root2);
	printf("\n");

	printf("inorder : \n");
	inorder(root);
	printf("\n");
	inorder(root2);
	printf("\n");

	printf("postorder : \n");
	postorder(root);
	printf("\n");
	postorder(root2);
	printf("\n");
}

결과창

preorder
A B D H I E J K C F L G
A B D H I E J K C F L G
inorder :
H D I B J E K A L F C G
H D I B J E K A L F C G
postorder :
H I D J K E B L F G C A
H I D J K E B L F G C A

바텀 업으로 만들었던, 탑 다운으로 만들었던 같은 결과를 가지는 것을 알 수 있다.

📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

✅ 1. 트리의 노드를 구조체로 만드는 방법을 안다.

✅ 2. 재귀 함수와 부분 문제를 이해한다.

✅ 3. 트리 생성을 재귀 함수를 통해 할 수 있다.

✅ 4. 트리 순회를 재귀 함수를 통해 할 수 있고, 각 순회를 알 수 있다.

⚠️ 트리의 depth가 너무 깊은 경우 스택 오버플로우가 발생할 수 있다. (읽어볼 거리 참고)

💣 과제,

전위 순회, 중위 순회, 후위 순회 중 최소 몇 개를 알면 트리를 유추할 수 있을지 생각해보자 (난이도 上)
CBT를 구현할 때, 위 코드처럼 자식 노드를 저장하는 표가 필요할지 생각해보자 (난이도 下) (저번 강의 참고)
tree의 레벨 당, 왼쪽에서 오른쪽 노드를 출력하려면 어떻게 해야 할지 생각해보자(난이도 上) (읽어볼 거리 참고)

🔜 더 공부해보기,

Minflix v3.1.2

자료구조(10) - 트리의 구현 기초와 재귀 함수를 통한 순회

🔚 짧게 하는 복습

트리의 구현 기초

재귀 함수란?

트리에서의 재귀 함수

재귀 함수를 통한 순회

오늘 한 코드 모두 정리

결과창

📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

자료구조(11) - 완전 이진 트리의 이진 탐색 트리의 구현

Minsu Choi

Comments

자료구조(10) - 트리의 구현 기초와 재귀 함수를 통한 순회

🔚 짧게 하는 복습

트리의 구현 기초

재귀 함수란?

트리에서의 재귀 함수

재귀 함수를 통한 순회

오늘 한 코드 모두 정리

결과창

📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

자료구조(11) - 완전 이진 트리의 이진 탐색 트리의 구현

Don't go yet!

객체지향프로그래밍(30) - 강의를 마무리 하며

객체지향프로그래밍(29) - 이론적 배경(2) - 객체지향의 SOLID 원칙

Share

Minsu Choi

Comments