// 이진 탐색 트리를 이용한 메모 저장 프로그램.
#include <stdio.h>
#include <stdlib.h> // malloc
#include <string.h> // srcmp
#include <conio.h> // _getch()
#define MAX_NAME 50 // 최대 제목 길이 50
#define MAX_TEXT 300 // 최대 내용 길이 300
/** 메모 데이터 정의(데이터노드) **/
typedef struct DataType
{
char Name[MAX_NAME]; // 메모의 제목
char Text[MAX_TEXT]; // 메모의 내용
}DataType;
/** 메모장 구조 정의(트리) **/
typedef struct MyMemo {
DataType Memo;
struct MyMemo* left;
struct MyMemo* right;
}MyMemo;
/** 문자열 비교 함수 **/
int Compare(DataType A, DataType B) //strcmp 를 한번에 할수 없기 때문에 비교결과를 반환하는 함수를 만듦.
{
return strcmp(A.Name, B.Name); // 각 문자열의 아스키코드 값을 비교
}
/** 메모 삽입 함수 **/
void AddMemo(MyMemo** Root, DataType Memo)
{
MyMemo* Current = (*Root); // 현재노드. 처음엔 루트를 넣음
MyMemo* Parent = NULL; // 부모노드
MyMemo* NewNode = NULL; // 새로운 노드
while (Current != NULL) // 자식이 없는 노드를 찾는 알고리즘
{
if (Compare(Memo, Current->Memo) == 0)
{
printf(" > 메모 생성 실패. 동일한 제목이 존재합니다.\n");
return;
}
Parent = Current;
if (Compare(Memo, Current->Memo) < 0) //작으면 왼쪽
Current = Current->left;
else
Current = Current->right; // 크면 오른쪽
}
NewNode = (MyMemo*)malloc(sizeof(MyMemo)); // 새로운 노드 생성!
if (NewNode == NULL)
return;
NewNode->Memo = Memo;
NewNode->left = NULL;
NewNode->right = NULL;
if (Parent != NULL) // 위 알고리즘에서 부모를 찾은 경우
{
if (Compare(Memo, Parent->Memo) < 0)
Parent->left = NewNode;
else
Parent->right = NewNode;
}
else // 부모노드를 못찾은 경우는 새 노드가 루트가 된다.
*Root = NewNode;
}
/** 메모 삭제 함수 **/
void DeleteMemo(MyMemo** Root, DataType Target) // 아니왜삭제가안돼개짜증나게
{
MyMemo* Current = (*Root);
MyMemo* Parent = NULL;
MyMemo* Child;
MyMemo* succ;
MyMemo* succ_p;
while (Current != NULL && Compare(Current->Memo, Target) != 0) // 타켓 노드의 바로 위까지 검색!
{
Parent = Current; // 삭제하고자 하는 노드의 부모를 찾는다.
if (Compare(Current->Memo, Target) < 0) // 노드가 비교대상 보다 작으면 -1, 크면 1
Current = Current->right;
else
Current = Current->left;
}
if (Current == NULL) {// 예외
//printf(" :: 메모가 존재하지 않습니다!\n\n");
return;
}
// 자식 노드가 없는 경우 -> Parent 는 Current 의 부모노드이다.
if ((Current->left == NULL) && (Current->right == NULL)) //and연산 -> 지우고자 하는 Current 노드의 자식이 없는 경우.
{
if (Parent != NULL)
{
if (Parent->left == Current)
Parent->left = NULL;
else
Parent->right = NULL;
}
else // 부모 노드가 없으므로 루트노드이다.
*Root = NULL;
}
//하나의 자식 노드가 있는 경우
else if ((Current->left == NULL) || (Current->right == NULL)) //or연산
{
if (Current->left != NULL) // 왼쪽, 오른쪽 노드 중 존재하는 노드를 자식으로 대입.
Child = Current->left;
else
Child = Current->right;
if (Parent != NULL)
{
if (Parent->left == Current) // 현재 노드의 자식을 부모에게 연결한다.
Parent->left = Child;
else
Parent->right = Child;
}
else
*Root = Child; // 부모가 없는 경우 자식이 루트로 된다.
}
// 자식이 2개인 경우.
else
{
succ_p = Current;
succ = Current->right;
while (succ->left != NULL)
{
succ_p = succ;
succ = succ->left;
}
if (succ_p->left = succ)
succ_p->left = succ->right;
else
succ_p->right = succ->right;
Current->Memo = succ->Memo;
Current = succ;
}
printf("\n * ─────────────────── *\n");
printf(" :: %s > 삭제완료 \n\n", Current->Memo.Name);
free(Current); // 노드 공간 반환.
}
/** 전체 메모 출력(제목만 출력됨) **/
int PrintMemo(MyMemo* Root)
{
MyMemo* Current = Root;
if (Current != NULL)
{
printf(" > %s\n", Current->Memo.Name); // 전위순회
if (Current->left != NULL)
PrintMemo(Current->left);
if (Current->right != NULL)
PrintMemo(Current->right);
}
else
{
printf(" > 메모가 존재하지 않습니다!\n\n");
return 0;
}
return 1;
}
/** 전위 출력**/
void Preorder(MyMemo* Root)
{
MyMemo* Current = Root;
if (Current != NULL)
{
printf(" > %s\n", Current->Memo.Name);
Preorder(Current->left);
Preorder(Current->right);
}
}
/** 중위 출력**/
void Inorder(MyMemo* Root)
{
MyMemo* Current = Root;
if (Current != NULL)
{
Preorder(Current->left);
printf(" > %s\n", Current->Memo.Name);
Preorder(Current->right);
}
}
/** 후위 출력**/
void Postorder(MyMemo* Root)
{
MyMemo* Current = Root;
if (Current != NULL)
{
Preorder(Current->left);
Preorder(Current->right);
printf(" > %s\n", Current->Memo.Name);
}
}
/** 메모 검색(제목입력 -> 본문출력) **/
MyMemo* SerchMemo(MyMemo* Root, DataType Target)
{
MyMemo* Current = Root;
if (Root = NULL)
return Root;
while (Current != NULL)
{
switch (Compare(Current->Memo, Target))
{
case 1:
Current = Current->left; //노드 값이 더 크면 왼쪽.
break;
case 0:
return Current;
break;
case -1:
Current = Current->right; // 노드값이 더 작으면 오른쪽.
break;
}
}
}
/** 메모 개수 카운트 **/
int CountMemo(MyMemo* Root)
{
MyMemo* Current = Root;
int Count = 0;
if (Current != NULL)
Count = 1 + CountMemo(Current->left) + CountMemo(Current->right);
return Count;
}
/** 화면 정리 대기 **/
void CLS()
{
printf("\n\n 메뉴로 돌아가려면 Enter 입력.");
_getch(); // Enter 을 입력받으면 화면을 지운다.
system("cls"); // 화면을 지우는 명령어.
}
int main(void)
{
DataType MemoData; // 메모의 데이터
MyMemo* Root = NULL; // 트리 생성
MyMemo* Temp; // 메모의 데이터를 임시 저장하는 노드.
FILE* file;
int UserSelect, exit = 0; // 스위치 변수, 메뉴 종료 변수.
while (exit != 1)
{
fflush(stdin); // 버퍼비움.
printf(" *──── 메모장 ────*\n");
printf("│ 1.메모작성 │\n");
printf("│ 2.메모삭제 │\n");
printf("│ 3.메모검색 │\n");
printf("│ 4.전체메모 │\n");
printf("│ 5.메모개수 │\n");
printf("│ 6.순회출력 │\n");
printf("│ 7.내보내기 │\n");
printf("│ 8.종료 │\n");
printf(" *─────────────────*\n");
printf(" :: 명령입력 > ");
scanf_s("%d", &UserSelect);
putchar('\n');
switch (UserSelect)
{
case 1: // 메모작성
getchar(); // 버퍼를 비워준다.
printf(" :: 메모를 작성합니다. \n\n");
printf(" :: 제목 > ");
gets(MemoData.Name);
printf("\n :: 내용 > ");
gets(MemoData.Text);
AddMemo(&Root, MemoData);
printf(" * ─────────────────── *\n");
printf(" :: 제목 > [%s]\n\n", MemoData.Name);
printf(" :: 내용 > %s", MemoData.Text);
CLS();
break;
case 2: // 메모 삭제
getchar();
printf("\n :: 메모를 삭제합니다. \n\n");
if (PrintMemo(Root))
{
printf("\n :: 제목 > ");
gets(MemoData.Name);
DeleteMemo(&Root, MemoData);
}
CLS();
break;
case 3: // 메모 검색(내용보기)
getchar();
if (PrintMemo(Root)) // PrintMemo -> 보여줄 메모가 있으면 1을 반환. 없으면 0을 반환.
{// 검색 전 모든 메모를 보여준다.
printf("\n :: 검색할 메모의 제목 입력 > ");
gets(MemoData.Name);
Temp = SerchMemo(Root, MemoData);
if (Temp != NULL) //예외처리 조건문. 함수에서 오류메세지를 빼냄.
{
printf("\n * ──── %s ──── *\n", Temp->Memo.Name);
printf(" %s\n\n", Temp->Memo.Text);
}
}
CLS();
break;
case 4: // 메모 전체 출력
getchar();
PrintMemo(Root);
CLS();
break;
case 5: // 메모 개수 카운트
getchar();
printf(" :: 메모의 개수 > %d", CountMemo(Root));
CLS();
break;
case 6: // 출력 순회 변경
getchar();
printf(" *─── 출력순회 ───*\n");
printf(" :: 1.전위순회\n");
printf(" :: 2.중위순회\n");
printf(" :: 3.후위순회\n");
printf(" *─────────────────*\n");
printf(" :: 명령입력 > ");
scanf("%d", &UserSelect);
putchar('\n');
if (UserSelect == 1)
Preorder(Root);
else if (UserSelect == 2)
Inorder(Root);
else if (UserSelect == 3)
Postorder(Root);
else
printf(" :: 올바른 메뉴를 입력하세요!\n");
CLS();
break;
case 7: // 파일 출력
getchar();
if (PrintMemo(Root))
{
printf("\n :: 파일로 만들 메모의 제목 입력 > ");
gets(MemoData.Name);
Temp = SerchMemo(Root, MemoData);
if (Temp != NULL)
{
file = fopen(Temp->Memo.Name, "w");
fprintf(file,Temp->Memo.Text);
printf("\n :: %s < 저장성공!\n",Temp->Memo.Name);
fclose(file);
}
else
printf(" :: 내용이 없습니다!\n");
}
CLS();
break;
case 8: // 종료
getchar();
printf(" :: 프로그램을 종료합니다. \n\n");
exit = 1;
return 0;
default: // 예외
getchar();
printf(" :: 올바른 메뉴를 입력하세요!\n");
CLS();
break;
}
}
}
