이진 탐색 트리
-삽입삭제탐색을 효율적으로 하기 위해 고안된 이진 트리
->조건 -모든 원소의 키는 유일한 키를 가진다.
-왼쪽 서브 트리 키들은 루트 키보다 작다.
-오른쪽 서브트리의 키들은 루트의 키보다 크다.
-왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
이진 탐색 트리 구현 및 테스트
// 8.11 이진 탐색 트리
// 설명:삽입삭제탐색으로 효율적으로 하기 위해 고안된 이진 트리
// 조건:-모든 원소의 키는 유일한 키를 가진다.
// -왼쪽 서브 트리 키들은 루트 키보다 작다.
// -오른쪽 서브트리의 키들은 루트의 키보다 크다.
// -왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
#define 이진탐색트리
#ifdef 이진탐색트리
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct TreeNode {
element key;
struct TreeNode* left, * right;
} TreeNode;
TreeNode* search_cycle(TreeNode* node, int key);
TreeNode* search_repetition(TreeNode* node, int key);
TreeNode* new_node(int item);
TreeNode* insert_node(TreeNode* node, int key);
TreeNode* min_value_node(TreeNode* node);
TreeNode* max_value_node(TreeNode* node);
TreeNode* delete_node(TreeNode* root, int key);
void inorder(TreeNode* root); //중위 순회(오름차순 출력)
void postorder(TreeNode* root); //후위 순회(내림차순 출력)
int get_node_count(TreeNode* root);
int get_nonleaf_count(TreeNode* root);
int get_leaf_count(TreeNode* root);
int get_oneleaf_count(TreeNode* root);
int get_twoleaf_count(TreeNode* root);
TreeNode* change_node_key(TreeNode* root, int h);
int return_tree_sum(TreeNode* root);
int isBalanced(TreeNode* node);
int main(void)
{
TreeNode* root = NULL;
root = insert_node(root, 11);
root = insert_node(root, 3);
root = insert_node(root, 4);
root = insert_node(root, 1);
root = insert_node(root, 56);
root = insert_node(root, 5);
root = insert_node(root, 6);
root = insert_node(root, 2);
root = insert_node(root, 98);
root = insert_node(root, 32);
root = insert_node(root, 23);
inorder(root); printf("\n");
if (search_repetition(root, 30) != NULL)
printf("이진 탐색 트리에서 30을 발견함\n");
printf("트리의 최솟값은 %d입니다\n", min_value_node(root)->key);
printf("트리의 최댓값은 %d입니다\n", max_value_node(root)->key);
printf("트리의 모든 키의 합은 %d입니다\n", return_tree_sum(root));
printf("트리의 높이는 %d입니다\n", get_height(root));
printf("노드의 개수는 %d입니다\n", get_node_count(root));
printf("단말노드의 개수는 %d입니다\n", get_nonleaf_count(root));
printf("비단말노드의 개수는 %d입니다\n", get_leaf_count(root));
printf("비단말노드 중 자식이 하나인 노드의 개수는 %d입니다\n", get_oneleaf_count(root));
printf("비단말노드 중 자식이 둘인 노드의 개수는 %d입니다\n", get_twoleaf_count(root));
printf("값을 변경하겠습니다\n");
root = change_node_key(root, 10);
inorder(root); printf("\n");
//가장 큰 값을 삭제한다.
delete_node(root, max_value_node(root)->key);
//가장 작은 값을 삭제한다.
delete_node(root, min_value_node(root)->key);
printf("오름차순으로 정렬하겠습니다\n");
inorder(root); printf("\n");
printf("내림차순으로 정렬하겠습니다\n");
postorder(root); printf("\n");
if (isBalanced(root)) printf("이 트리는 서브 트리의 높이가 최대 1 차이나는 균형트리입니다");
return 0;
}
// 순환적인 탐색 함수
TreeNode* search_cycle(TreeNode* node, int key)
{
if (node == NULL) return NULL;
if (key == node->key) return node;
else if (key < node->key)
return search_cycle(node->left, key);
else
return search_cycle(node->right, key);
}
// 반복적인 탐색 함수
TreeNode* search_repetition(TreeNode* node, int key)
{
while (node != NULL)
{
if (key == node->key) return node;
else if (key < node->key)
node = node->left;
else
node = node->right;
}
}
// 새 노드 생성 함수
TreeNode* new_node(int item)
{
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// 삽입 함수
TreeNode* insert_node(TreeNode* node, int key)
{
//트리가 공백이면 새로운 노드 반환
if (node == NULL) return new_node(key);
//그렇지 않으면 순환적으로 트리를 내려간다.
if (key < node->key)
node->left = insert_node(node->left, key);
else if (key > node->key)
node->right = insert_node(node->right, key);
//변경된 루트 포인터를 반환
return node;
}
// 노드 중 최솟값을 갖는 노드 반환
TreeNode* min_value_node(TreeNode* node)
{
TreeNode* current = node;
//맨왼쪽 단말 노드가 가장 작은 값이다.
while (current->left != NULL)
{
current = current->left;
}
return current;
}
// 노드 중 최댓값을 갖는 노드 반환
TreeNode* max_value_node(TreeNode* node)
{
TreeNode* current = node;
//맨오른 단말 노드가 가장 큰 값이다.
while (current->right != NULL)
{
current = current->right;
}
return current;
}
// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제 후 새로운 루트 노드 반환
TreeNode* delete_node(TreeNode* root, int key)
{
if (root == NULL) return root;
//만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것
if (key < root->key) root->left = delete_node(root->left, key);
else if (key > root->key) root->right = delete_node(root->right, key);
else { //(key == root->key) 구하고자 하는 key의 값을 가지는 노드를 찾았을 때
// 1. 삭제하려는 노드가 아래에 더 이상의 노드가 없는 단말 노드일 때
// 단말 노드의 부모 노드를 찾아서 부모 노드 안의 링크필드를 NULL로 만들어 연결을 끊는다.
// 2. 삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
// 자기 노드는 삭제하고 서브 트리는 자기 노드의 부모 노드에 붙여준다.
if (root->left == NULL)
{
TreeNode* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
TreeNode* temp = root->left;
free(root);
return temp;
}
// 3. 삭제하려는 노드가 두개의 서브트리를 가지고 있는 경우
// 왼쪽 서브트리에서 가장 큰 값, 오른쪽 서브트리에서 제일 작은 값이 후계자 대상 노드가 된다.
TreeNode* temp = max_value_node(root->left); // 선택1.왼쪽 서브트리에서 가장 큰 값이 후계자
//TreeNode* temp = min_value_node(root->right); // 선택2.오른쪽 서브트리에서 가장 작은 값이 후계자
// 중위 순회시 후계 노드를 복사한다.
root->key = temp->key;
// 중위 순회시 후계 노드를 삭제한다.
//root->right = delete_node(root->right, temp->key);
root->left = delete_node(root->left, temp->key);
}
return root;
}
// 중위 순회 (왼쪽서브트리-노드-오른쪽서브트리) 이진 탐색 트리에서는 오름차순 정리
void inorder(TreeNode* root)
{
if (root != NULL)
{
inorder(root->left);
printf("[%d] ", root->key);
inorder(root->right);
}
}
// 후위 순회 (왼쪽서브트리-오른쪽서브트리-노드) 이진 탐색 트리에서는 내림차순 정리
void postorder(TreeNode* root)
{
if (root != NULL)
{
postorder(root->right);
printf("[%d] ", root->key);
postorder(root->left);
}
}
// 노드의 개수를 구하는 함수
int get_node_count(TreeNode* root)
{
if (root != NULL)
{
return 1 + get_node_count(root->left) + get_node_count(root->right);
}
return 0;
}
// 트리의 높이를 구하는 함수
int get_height(TreeNode* root)
{
if (root != NULL)
{
return 1 + max(get_height(root->right), get_height(root->left));
}
return 0;
}
// 단말 노드의 개수를 구하는 함수
int get_nonleaf_count(TreeNode* root)
{
if (root != NULL)
{
if (root->left == NULL && root->right == NULL)
return 1;
else
return get_nonleaf_count(root->left) + get_nonleaf_count(root->right);
}
return 0;
}
// 비단말 노드의 개수를 구하는 함수
int get_leaf_count(TreeNode* root)
{
if (root != NULL)
{
if (root->left != NULL || root->right != NULL)
return 1 + get_leaf_count(root->left) + get_leaf_count(root->right);
else
return 0;
}
return 0;
}
// 비단말 노드 중 자식이 하나인 노드의 개수 반환
int get_oneleaf_count(TreeNode* root)
{
if (root != NULL)
{
if ((root->left != NULL) && (root->right == NULL))
return 1 + get_oneleaf_count(root->left);
else if ((root->left == NULL) && (root->right != NULL))
return 1 + get_oneleaf_count(root->right);
else
return get_oneleaf_count(root->left) + get_oneleaf_count(root->right);
}
return 0;
}
// 비단말 노드 중 자식이 둘인 노드의 개수 반환
int get_twoleaf_count(TreeNode* root)
{
if (root != NULL)
{
if (root->left != NULL && root->right != NULL)
return 1 + get_twoleaf_count(root->left) + get_twoleaf_count(root->right);
else
return get_twoleaf_count(root->left) + get_twoleaf_count(root->right);
}
return 0;
}
// 모든 노드의 값을 h씩 증가시키는 함수
TreeNode* change_node_key(TreeNode* root, int h)
{
if (root != NULL)
{
root->key += h;
if (root->left != NULL) change_node_key(root->left, h);
if (root->right != NULL) change_node_key(root->right, h);
}
return root;
}
// 트리가 갖는 모든 key를 더한 값을 반환하는 함수
int return_tree_sum(TreeNode* root)
{
if (root != NULL)
{
return root->key + return_tree_sum(root->right)
+ return_tree_sum(root->left);
}
return 0;
}
// 균형 트리인지 아닌지 확인하는 함수
int isBalanced(TreeNode* node) {
if (node == NULL)
return 1;
int leftHeight = get_height(node->left);
int rightHeight = get_height(node->right);
//왼쪽 서브트리와 오른쪽서브트리의 높이차가 2이상 나지 않고 둘 다 균형이 잡혀있을 경우 참
if ((rightHeight - leftHeight) > -1
&& (rightHeight - leftHeight) < 2
&& isBalanced(node->left) && isBalanced(node->right))
return 0;
return 1;
}
#endif
댓글