#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#define max(a, b) (((a) > (b)) ? (a) : (b))
int BN[100] = {0};
int cnt = 0;
typedef struct TreeNode
{
int key;
int balance;
struct TreeNode *left, *right;
} TreeNode;
int get_height(TreeNode *node)
{
int height = 0;
if (node != NULL)
{
height = 1 + max(get_height(node->left), get_height(node->right));
}
return height;
}
int get_balance(TreeNode *node)
{
if (node == NULL)
return 0;
return get_height(node->left) - get_height(node->right);
}
TreeNode *new_node(int item)
{
TreeNode *temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->key = item;
temp->balance = 0;
temp->left = NULL;
temp->right = NULL;
return temp;
}
TreeNode *insert_node(TreeNode **node, int key)
{
if (*node == NULL)
(*node) = new_node(key);
if (key < (*node)->key)
{
(*node)->left = insert_node(&((*node)->left), key);
(*node)->balance = get_balance(*node);
if (((*node)->balance) < -1 || ((*node)->balance) > 1)
{
BN[cnt] = (long int)((*node)->key);
cnt++;
}
}
else if (key > (*node)->key)
{
(*node)->right = insert_node(&((*node)->right), key);
(*node)->balance = get_balance(*node);
if (((*node)->balance) < -1 || ((*node)->balance) > 1)
{
BN[cnt] = (long int)((*node)->key);
cnt++;
}
}
return *node;
}
void inorder(FILE *stream, TreeNode *root)
{
if (root)
{
inorder(stream, root->left);
fprintf(stream, "%d ", root->key);
inorder(stream, root->right);
}
}
void preorder(FILE *stream, TreeNode *root)
{
if (root)
{
fprintf(stream, "%d ", root->key);
preorder(stream, root->left);
preorder(stream, root->right);
}
}
int main(void)
{
FILE *fp = fopen("AVL.in", "r");
FILE *fout = fopen("AVL.out", "w");
char op[100];
int input;
TreeNode *root = NULL;
while (fscanf(fp, "%s %d", op, &input) != EOF)
{
insert_node(&root, input);
fprintf(fout, "I ");
inorder(fout, root);
fprintf(fout, "\n");
fprintf(fout, "P ");
preorder(fout, root);
fprintf(fout, "\n");
if (BN[0] == 0)
fprintf(fout, "BN\n\n");
else
fprintf(fout, "BN %d\n\n", BN[0]);
cnt = 0;
}
fclose(fp);
fclose(fout);
return 0;
}
코드 설명
// 헤더 (1~4)
stdio.h와 stdlib.h 라이브러리를 포함하고, fscanf 오류 방지를 위해 _CRT_SECURE_NO_WARNINGS을 정의한다. 또한, max 함수도 정의한다.
// 전역변수 선언 (6~7)
전역변수 BN[100]과 cnt를 선언하고, 모두 0으로 초기화한다. BN은 어떤 한 트리에서 균형도의 절댓값이 2 이상인 모든 노드의 배열이다. cnt는 추후에 BN의 인덱스 값을 나타내기 위해 사용될 변수이다.
// TreeNode 구조체 선언 (9~14)
TreeNode 구조체를 선언한다. TreeNode 구조체에는 노드의 값을 나타내는 변수 key, 노드의 균형도를 나타내는 balance, 노드의 왼쪽 subtree를 가리키는 *left, 오른쪽 subtree를 가리키는 *right가 있다. 이 구조체의 자료형을 TreeNode라고 정의한다.
// get_height 함수 (16~24)
get_height 함수는 높이를 구하고자 하는 노드의 포인터 변수 *node를 인수로 받아 높이를 반환하는 함수이다. 지역변수 height를 선언하고 0으로 초기화한다. 만약 노드가 비어 있지 않으면, 높이는 노드의 왼쪽 subtree와 오른쪽 subtree의 높이 중 더 큰 값에 1을 더한 값이다. 왼쪽 subtree와 오른쪽 subtree의 높이는 재귀적으로 get_height 함수를 호출하여 구할 수 있다. 이렇게 최종적으로 구한 높이의 값을 반환한다.
// get_balance 함수 (26~31)
get_balance 함수는 균형도를 구하고자 하는 노드의 포인터 변수 *node를 인수로 받아 노드의 균형도를 반환하는 함수이다. 만약 노드가 비어 있으면 0을 반환하고, 그렇지 않으면 왼쪽 subtree의 높이에서 오른쪽 subtree의 높이를 뺀 값을 반환한다.
// new_node 함수 (33~41)
new_node 함수는 삽입하고자 하는 노드의 값인 item을 인수로 받아 노드의 포인터 변수를 반환하는 함수이다. 삽입하고자 하는 노드의 포인터 변수 temp를 동적 할당해준다. temp가 가리키는 key에 item 값을 대입하고, temp가 가리키는 balance에는 0을 대입하고, temp가 가리키는 left와 right에는 모두 NULL을 대입한 후, temp를 반환한다.
// insert_node 함수 (43~72)
insert_node 함수는 이중 포인터 *node와 삽입하고자 하는 노드의 값인 key를 인수로 받아 노드의 포인터 변수를 반환하는 함수이다. 만약 node가 간접 참조하는 값이 NULL이면 key를 매개변수로 new_node함수를 호출하여 새로운 노드를 삽입한다. 만약 key가 *node의 key값보다 작으면 *node의 왼쪽에 insert_node 함수를 재귀적으로 호출하여 값을 삽입하고, *node의 balance에 get_balance 함수를 호출하여 균형도를 갱신한다. 이 때, 만약 균형도가 -1보다 작거나 1보다 크면 BN에 *node의 key값을 대입하고, cnt 값을 하나 증가시킨다. 반대로, key가 *node의 key값보다 크면 *node의 오른쪽에 insert_node 함수를 재귀적으로 호출하여 값을 삽입하고, *node의 balance에 get_balance 함수를 호출하여 균형도를 갱신한다. 이 때도 마찬가지로, 균형도가 -1보다 작거나 1보다 크면 BN에 *node의 key값을 대입하고, cnt 값을 하나 증가시킨다.
// inorder 함수 (74~82)
inorder 함수는 파일 포인터 변수 *stream과 포인터 변수 *node를 인수로 받아 파일에 트리를 중위순회로 출력해주는 함수이다. root에서 root의 왼쪽 노드를 inorder 함수로 재귀적으로 호출한 후, 더 이상 왼쪽 노드가 존재하지 않으면 노드의 key값을 파일에 출력하고 노드의 오른쪽을 또 재귀적으로 탐색하여 결과적으로 왼쪽 subtree, 루트 노드, 오른쪽 subtree 순으로 파일에 출력하게 된다.
// preorder 함수 (84~92)
preorder 함수는 파일 포인터 변수 *stream과 포인터 변수 *node를 인수로 받아 파일에 트리를 전위순회로 출력해주는 함수이다. root 값을 먼저 파일에 출력한 후, root의 왼쪽 노드를 preorder 함수로 재귀적으로 호출한 후, 오른쪽 노드도 preorder 함수로 재귀적으로 호출하여 호출된 함수를 탈출하면서 결과적으로 루트 노드, 왼쪽 subtree, 오른쪽 subtree 순으로 파일에 값을 출력한다.
// main 함수 (94~125)
main 함수에서는 먼저 파일 포인터 *fp로 AVL.in 파일을 열고, *fout으로 AVL.out 파일을 열어 준다. AVL.in 파일에서 operation 문자를 저장할 변수 op[100]을 선언하고, 입력 값을 저장할 변수 input을 선언한다. 그리고 루트 노드 포인터 *root를 선언하고 NULL로 초기화한다. fscanf로 AVL.in 파일에서 한 줄 씩 데이터를 읽어오면서 End Of File을 만나기 전까지 while문을 반복한다. while문에서는 먼저 root 노드의 주소 값과 input을 매개변수로 insert_node 함수를 호출하여 트리에 노드를 삽입한다. 그리고 inorder 함수를 호출하여 중위순회로 트리를 출력하고, preorder 함수를 호출하여 전위순회로 트리를 출력한다. 만약 breaking node가 없으면 BN을 출력하지 않고, 그렇지 않으면 첫번째 breaking node인 BN[0]을 출력한다. 그리고, 다음 번 while문을 위해 cnt값을 다시 0으로 초기화 시켜준다. while문이 종료되면 AVL.in 파일과 AVL.out 파일을 닫고 main 함수를 종료한다.
