<이진트리 기본 알고리즘> #후위순회 #트리의 높이 #(단말)노드 개수 구하는 알고리즘

# 후위 순회를 이용한 디렉토리 용량 계산 프로그램의 알고리즘 calc_direc_size

/* 트리의 높이, 노드개수 구하는 알고리즘 등은 아래로 내려가시다 보면 만날 수 있습니다. */

/* 또한 해당 게시물은 우클릭 및 드래그가 금지되어 있기에 맨 아래 종합 소스코드 첨부합니다. */

---

 이진 트리의 순회는 디렉토리의 용량을 계산하는 데도 사용될 수 있다. 단, 이진트리라는 제약조건으로 하나의 디렉토리 안에 다른 디렉토리가 2개 이하로만 존재해야 한다. // 삼진트리였다면, 3개 이하로만 존재해야 한다.

 이진 트리 순회의 응용에 해당하는 프로그램 중 하나인 디렉토리 용량을 계산하는 프로그램을 소개한다. 디렉토리는 우리가 흔히 '폴더'라고 부르는 것과 동의어다.

 디렉토리 용량 계산 프로그램을 작성하기 전, 어떤 알고리즘을 사용할 것인가를 먼저 생각해보자. 생각할 때는 구체적인 상황 하나를 상정하고 예시를 들면 쉽다. 상황을 하나 들어보면 이렇다.

 우리 컴퓨터에 '자료구조'라는 폴더가 있다고 가정해보자. 자료구조 폴더 안에는 스택, 큐, 트리 라는 폴더 3개가 있다. 하지만 각 폴더 안에 어떤 파일들이 있는지는 알 수 없다고 가정한다. 알 수 있는 정보는 각 폴더에 대한 용량이다. 각 폴더의 용량은 100KB, 200KB, 300KB 이렇게 주어졌다.

 위와 같은 가정하에 자료구조 폴더의 크기를 구하라는 요청을 받았다. 어떤 과정을 통해 자료구조 폴더의 크기를 구할 수 있을까? 조금만 생각해보면 쉽게 알 수 있다. 하위 폴더의 크기가 주어졌으니 그 크기들을 더해서 현재 폴더의 크기를 구하면 된다.

 이 아이디어가 중요하다. 하위 폴더의 크기를 더해 현재 폴더의 크기를 구한다는 아이디어 말이다. 하위에 존재하는 폴더의 정보를 얻어낸 후, 현재 폴더로 오는 구조이기 때문에 후위순회를 사용해야한다는 걸 알 수 있다.

 /* 후위 순회란, 트리를 탐색할 때 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문하는 순회를 일컫는 말이다. 후위순회의 알고리즘은 다음과 같다. */

/*************************************************
 ** 후위순회 알고리즘 (L R V)
*************************************************/

void postorder(TreeNode *root) {
	if (root) {
		postorder(root->left); // 왼쪽 서브 트리 순회
		postorder(root->right); // 오른쪽 서브 트리 순회
		printf("%d", root->data); // 노드 방문
	}
}

/*************************************************
 ** End Line
*************************************************/

 후위 순회를 사용하되 순환 호출되는 함수가 용량을 반환하도록 만들어야 한다. 이런 사안들을 반영한 것이 아래 디렉토리 용량계산 프로그램이다. 트리는 동적으로 생성하는 편이 좋지만, 알고리즘을 공부하기 위해 간단하게 정적으로 트리를 생성했다.

/*************************************************
 ** 디렉토리 용량 계산 프로그램
*************************************************/

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

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

//			n1
//		n3		n2
//	n4		n5

int calc_direc_size(TreeNode *root) { // 트리에 있는 data값을 합산한다.
	if (!root) // 빈 노드 였을 경우
		return 0;
	else {
		int left = calc_direc_size(root->left); // 왼쪽 서브트리를 순회한다.
		int right = calc_direc_size(root->right); // 오른쪽 서브트리를 순회한다.
		return left + right + root->data; // 순회한 노드에 해당하는 데이터를 더해 리턴한다.
	}
	return 0;
}

void main() {
	TreeNode n4 = { 500, NULL, NULL };
	TreeNode n5 = { 200, NULL, NULL };
	TreeNode n3 = { 100, &n4, &n5 };
	TreeNode n2 = { 50, NULL, NULL };
	TreeNode n1 = { 0, &n2, &n3 };

	printf("디렉토리의 크기 = %d\n", calc_direc_size(&n1));
}
/*************************************************
 ** End Line
*************************************************/

# 트리의 높이 구하기

---

 트리의 높이를 구할 때 핵심 개념은, 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이를 비교하여 큰 쪽을 택한다는 것이다. 그렇다면 우리에게 필요한 건 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이다. 높이는 어떻게 구할 수 있을까?

/* 위에 있는 디렉토리 용량 계산 프로그램에 있는 TreeNode와 main 함수를 그대로 이용해서 봅시다. */

/*************************************************
 ** 트리의 높이를 구하는 알고리즘
*************************************************/
typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
} TreeNode;

//			n1
//		n3		n2
//	n4		n5

int get_height(TreeNode *root) { // 트리의 높이를 구한다.
	if (!root)
		return 0;
	else {
		int left_h = get_height(root->left); // 왼쪽 서브트리의 높이를 순환호출을 통해 얻는다.
		int right_h = get_height(root->right); // 같은 방법으로 오른쪽 서브트리의 높이를 얻는다.
		return 1 + (left_h > right_h ? left_h : right_h); // 둘 중 큰 값에 1을 더해 반환한다.
	}
}

void main() {
	TreeNode n4 = { 500, NULL, NULL };
	TreeNode n5 = { 200, NULL, NULL };
	TreeNode n3 = { 100, &n4, &n5 };
	TreeNode n2 = { 50, NULL, NULL };
	TreeNode n1 = { 0, &n2, &n3 };

	printf("디렉토리의 크기 = %d\n", calc_direc_size(&n1));
}

/*************************************************
 ** End Line
*************************************************/

 순환 알고리즘을 작성하거나 읽을 때는 탈출조건을 보는 게 아니라 순환호출 되는 부분을 먼저 살펴봐야 한다. 호출되는 부분은 int left_h = get_height(root->left), int right_h = get_height(root->right) 이 두 부분이다. 

 이 알고리즘을 만드는 사람 입장에서 생각해보자. 왼쪽 서브트리의 높이(left_h)와 오른쪽 서브트리의 높이(right_h)를 구하기 위해 일단 순환함수로 각 서브트리의 끝(밑바닥)까지 방문할 수 있도록 구성했다. 방문 순서는 get_height(root->left) 호출이 먼저 이루어졌으므로, 왼쪽 서브트리의 끝까지 갈 것이고, 탈출조건을 맞아 완전히 왼쪽 서브트리를 나오면, 오른쪽 서브트리로 진입할 것이다. // 탈출조건과 탈출문이 없다면, 순환은 끊임없이 계속 이루어지므로 무한루프에 빠지게 된다.

 순환하는 부분을 살펴봤으니 이제 탈출 조건을 만든다고 생각해보자. 데브맷의 경우, 순환의 끝에 이르렀을 때가 언제인지를 먼저 생각해봤다. 순환이 끝날 때는 바로, 단말노드를 만났을 때다. 단말노드란 자식이 없는 노드를 뜻한다. 그렇다면 단말노드인 걸 어떻게 알 수 있을까? 

/* 참고로 데브맷은 블로그 주인장의 필명이다. */

 자식이 없는 것이 단말노드이므로, 우리는 두 가지 정도의 조건문을 생각할 수 있다.

• if(root->left == NULL && root->right == NULL) // 왼쪽 서브트리와 오른쪽 서브트리가 없을 때
• if(root == NULL) or if(!root) // root노드가 NULL 일 때, 즉 자기 자신이 NULL이 될 때 

 root == NULL 이라는 말은 자식 노드가 있나 살펴보러 내려가긴 했는데 아무 것도 없었다는 뜻이다. 데브맷은 이 조건문을 택했다. 내 자식이 있는지 탐색을 해봤는데 없으니 일단 0을 리턴한다. 리턴을 하고 돌아왔으면 그 다음 순서는 어떻게 될까? 위의 get_height 알고리즘에서 마지막 부분을 살펴보자.

 맨 처음에 1을 하나 더하는 것이 눈에 띈다. 왜 1을 더해주는 걸까? 라는 의문이 든다면, 그 이전에 어떤 작업을 시행했는지를 살펴보면 된다. 순환을 계속하면서 트리 끝까지 내려가 있는 상태에서, 한 단계 더 내려가서 root == NULL 이 되는 상황이 연출됐다. 자식이 없으므로 left_h 와 right_h 는 둘 다 0이 될 것이다.

 내 자식들은 존재하지 않지만, 나는 존재한다는 것이 입증이 됐다. 따라서 나는 높이를 구할 때 하나의 수치로 환산될 수 있는 것이다. 그래서 1을 더하는 것이다. 1을 더한 후에는, 왼쪽 서브트리와 오른쪽 서브트리의 높이 값 중 더 큰 놈을 택하면 된다. 이 부분은 삼항연산자로 이루어져 있다.

 순환의 개념이 들어가 다소 난해할 수 있지만, 순환 알고리즘을 이해할 땐 개념적으로 접근하면 좀 편하다. 이게 먼저 실행되고 그 다음엔 저게 실행되고 어디로 리턴되고 등의 실행순서를 따지면 매우 헷갈린다. 하지만, 얘는 왼쪽 서브트리 높이 구하는 일을 담당해주고 너는 오른쪽 서브트리 높이 구하는 일을 담당해주고 그 결과를 비교해서 큰 놈을 가져다 값으로 쓴다 라는 식의 개념적 접근을 하면 한결 수월하다.

# 노드 갯수 구하기

---

 위에서 설명한 순환의 작동방식을 이해 했다면, 노드 개수를 구하는 알고리즘은 식은 죽 먹기다. 긴 말할 것 없이 바로 아래의 코드를 살펴보자.

/*************************************************
 ** 트리에 존재하는 모든 노드 갯수를 구하는 알고리즘
*************************************************/
typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
} TreeNode;

//			n1
//		n3		n2
//	n4		n5

int get_node_count(TreeNode *root) { // 트리에 존재하는 모든 노드의 갯수를 구한다.
	if (!root)
		return 0;
	else
		return get_count(root->left) + get_count(root->right) + 1;
}

void main() {
	TreeNode n4 = { 500, NULL, NULL };
	TreeNode n5 = { 200, NULL, NULL };
	TreeNode n3 = { 100, &n4, &n5 };
	TreeNode n2 = { 50, NULL, NULL };
	TreeNode n1 = { 0, &n2, &n3 };

	printf("모든 노드 개수 = %d\n", get_node_count(&n1));
}

/*************************************************
 ** End Line
*************************************************/

 위와 마찬가지로 데브맷은 탈출조건을 if(!root) 로 설정했다. 즉, 막상 내려가래서 내려갔는데 아무도 없네? 라는 상황을 탈출 조건으로 생각한 것이다. (왼쪽이든 오른쪽이든) 내려갔는데 아무도 없으므로 return 값은 0으로 주고, 다시 한 칸 올라온다. 아래에는 아무도 없었지만 나 자신은 존재하므로 1을 더해준 후 다시 return 한다.

# 단말노드 갯수 구하기

---

 긴 말할 것 없이 아래의 코드를 살펴보자. 단말노드의 갯수를 구하는 경우는 if(root->left == NULL && root->right == NULL) 을 탈출조건으로 줬다. 즉, 내 자식이 존재하지 않을 때가 조건이다.

/*************************************************
 ** 트리에 있는 단말노드 갯수를 구하는 알고리즘
*************************************************/
typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
} TreeNode;

//			n1
//		n3		n2
//	n4		n5

int get_leaf(TreeNode *root) { // 트리에 존재하는 단말노드의 갯수를 구한다.
	if (!root)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	else
		return get_leaf(root->left) + get_leaf(root->right);
}

void main() {
	TreeNode n4 = { 500, NULL, NULL };
	TreeNode n5 = { 200, NULL, NULL };
	TreeNode n3 = { 100, &n4, &n5 };
	TreeNode n2 = { 50, NULL, NULL };
	TreeNode n1 = { 0, &n2, &n3 };

	printf("단말 노드의 갯수 = %d\n", get_leaf(&n1));
}

/*************************************************
 ** End Line
*************************************************/

 여기서의 if(!root)의 경우, 누군가 이 함수를 사용할 때 노드가 아무 것도 없는 걸 매개변수로 넘겼을 때를 대비하기 위함이다. 오류를 방지하는 용도로서 의미가 있는 구문인 것이다. 이 구문을 탈출조건문으로 사용하기 힘든 이유는, 이 조건만으로는 단말노드만을 셀 수 없기 때문이다. 직접 작성하다 보면 아마 벽에 막힐 것이다.

트리 기본 알고리즘.c