bst_func.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#define TRUE 1
#define FALSE 0
typedef char NodeData;
typedef struct _TREENODE_ {
NodeData data;
struct _TREENODE_* left;
struct _TREENODE_* right;
}TREENODE;
typedef struct _NODEMAP_ {
int flag;
NodeData data;
}NODEMAP;
int getMax(int a, int b);
int countNode(TREENODE* node);
int getHeight(TREENODE* node);
void printGivenLevel(TREENODE* root, int level, NODEMAP* map, int pos);
void showTree(TREENODE* node);
TREENODE* searchNode(TREENODE * root, int key);
TREENODE* insertNode(TREENODE* root, char x);
void deleteNode(TREENODE** root, char x);
void displayInorder(TREENODE* root);
bst_func.c
#include "bst_func.h"
int getMax(int a, int b)
{
return ((a > b) ? a : b);
}
int countNode(TREENODE* node) {
if (node == NULL) return 0;
return 1 + countNode(node->left) + countNode(node->right);
}
int getHeight(TREENODE* node) {
if (node == NULL) {
return 0;
}
else {
return 1 + max(getHeight(node->left), getHeight(node->right));
}
}
void printGivenLevel(TREENODE* root, int level, NODEMAP* map, int pos)
{
if (root == NULL)
{
return;
}
if (level == 1) {
map[pos].data = root->data;
map[pos].flag = TRUE;
}
else if (level > 1)
{
printGivenLevel(root->left, level - 1, map, pos * 2);
printGivenLevel(root->right, level - 1, map, pos * 2 + 1);
}
}
void showTree(TREENODE* node)
{
int height = 0;
int numOfNodes = 0;
NODEMAP* treeArray = NULL;
char** square = NULL;
static int pos = 0;
int cnt_i;
int cnt_j;
int position;
int start, term, index;
height = getHeight(node);
if (height != 0) {
numOfNodes = (1 << height);
}
treeArray = (NODEMAP*)calloc(numOfNodes, sizeof(NODEMAP));
assert(treeArray != NULL);
square = (char**)calloc(height, sizeof(char*));
for (cnt_i = 0; cnt_i < height; cnt_i++)
{
square[cnt_i] = (char*)calloc(numOfNodes, sizeof(char));
memset(square[cnt_i], '.', numOfNodes);
}
pos = 1;
for (cnt_i = 1; cnt_i <= height; cnt_i++) {
printGivenLevel(node, cnt_i, treeArray, pos);
}
for (cnt_i = 1; cnt_i <= numOfNodes; cnt_i++)
{
treeArray[cnt_i - 1] = treeArray[cnt_i];
}
pos = 0;
start = (1 << (height - 1)) - 1;
term = (1 << (height));
index = (1 << (height - 2));
for (cnt_i = 0; cnt_i < height; cnt_i++)
{
for (cnt_j = start; cnt_j < numOfNodes; cnt_j += term)
{
if (treeArray[pos].flag == TRUE) {
if (treeArray[pos].data >= 0 && treeArray[pos].data <= 9) {
square[cnt_i][cnt_j] = (treeArray[pos].data + '0');
}
else {
square[cnt_i][cnt_j] = (treeArray[pos].data);
}
}
else {
square[cnt_i][cnt_j] = '.';
}
pos += 1;
}
term >>= 1;
start -= index;
index >>= 1;
}
printf("\n");
for (cnt_i = 0; cnt_i < height; cnt_i++)
{
for (cnt_j = 0; cnt_j < numOfNodes; cnt_j++)
{
printf("%c", square[cnt_i][cnt_j]);
}
printf("\n");
}
if (treeArray != NULL) {
free(treeArray);
}
if (square != NULL)
{
for (cnt_i = 0; cnt_i < height; cnt_i++)
{
if (square[cnt_i] != NULL)
{
free(square[cnt_i]);
}
}
free(square);
}
}
TREENODE * insertNode(TREENODE* root, char x)
{
TREENODE* p = root;
if (p == NULL) {
TREENODE* newNode = (TREENODE*)calloc(1, sizeof(TREENODE));
assert(newNode != NULL);
newNode->data = x;
return newNode;
}
else {
if (p->data < x) {
p->right = insertNode(p->right, x);
}
else if (p->data > x) {
p->left = insertNode(p->left, x);
}
}
return p;
}
void deleteNode(TREENODE** root, char x)
{
if (*root == NULL) {
printf("삭제할 노드가 존재하지않습니다\n");
return;
}
else {
TREENODE* cur = *root;
TREENODE* pre = *root;
while (cur->data != x) {
pre = cur;
if (cur->data < x) {
cur = cur->right;
}
else if (cur->data > x) {
cur = cur->left;
}
}
if (cur == NULL) {
printf("해당 노드는 존재하지 않습니다\n");
}
else {
if (cur->left == NULL && cur->right == NULL) {
if (pre != NULL) {
if (pre->left == cur) {
pre->left = NULL;
}
else {
pre->right = NULL;
}
}
else {
*root = NULL;
}
}
else if (cur->left != NULL && cur->right != NULL) {
TREENODE* succ = cur;
TREENODE* succ_parent = cur;
succ = succ->right;
while (succ->left != NULL) {
succ_parent = succ;
succ = succ->left;
}
cur->data = succ->data;
if (succ_parent->right == succ) {
succ_parent->right = succ->right;
}
else {
succ_parent->left = succ->right;
cur->data = succ->data;
}
free(succ);
succ = NULL;
}
else {
TREENODE* child = NULL;
if (cur->right==NULL) {
child = cur->left;
}
else {
child = cur->right;
}
if (pre != NULL) {
if (pre->left == cur) {
pre->left = child;
}
else {
pre->right = child;
}
}
else {
*root = child;
}
}
}
}
}
void displayInorder(TREENODE* root)
{
if (root == NULL) {
return;
}
else {
displayInorder(root->left);
printf("%c ", root->data);
displayInorder(root->right);
}
}
TREENODE* searchNode(TREENODE * root, int key)
{
if (root == NULL) {
return NULL;
}
else if (root->data == key) {
return root;
}
else {
if (root->data < key) {
return searchNode(root->right, key);
}
else {
return searchNode(root->left, key);
}
}
}
main.c
#include "bst_func.h"
int main() {
int ans;
char item;
bool Continue = true;
TREENODE* root = NULL;
root=insertNode(root, 'h');
insertNode(root, 'c');
insertNode(root, 'j');
insertNode(root, 'b');
insertNode(root, 'e');
insertNode(root, 'n');
insertNode(root, 'k');
insertNode(root, 'p');
while (Continue) {
printf("\n\n*-----------------------------*\n");
printf("\t1: 트리 출력\n");
printf("\t2: 문자 삽입\n");
printf("\t3: 문자 삭제\n");
printf("\t4: 문자 검색\n");
printf("\t5: 종료\n");
printf("*-----------------------------*\n");
printf("메뉴 입력 >> ");
scanf("%d", &ans);
switch (ans) {
case 1:
printf("\n\t[이진 트리 출력] ");
displayInorder(root);
printf("\n");
showTree(root);
break;
case 2:
printf("\n삽입할 문자를 입력하세요 :");
scanf(" %c", &item);
TREENODE* found1 = searchNode(root, item);
if (found1 != NULL) {
printf("\n해당 문자는 이미 존재하기에 삽입 불가능합니다\n");
}
else {
insertNode(root, item);
}
break;
case 3:
printf("\n삭제할 문자를 입력하세요 :");
scanf(" %c", &item);
deleteNode(&root, item);
break;
case 4:
printf("\n검색할 문자를 입력하세요 :");
TREENODE* found2 = searchNode(root, item);
scanf(" %c", &item);
found2 = searchNode(root, item);
if (found2 == NULL) {
printf("\n문자를 찾지 못하였습니다\n");
}
else {
printf("\n %c를 찾았습니다 \n", found2->data);
}
break;
case 5:
printf("종료\n");
Continue = false;
break;
default:
printf("해당 메뉴는 존재하지 않습니다. 다시 골라주세요\n");
break;
}
}
getchar();
return 0;
}
