TreeProgram.c
삽입, 삭제, 스왑, 출력, 종료가 가능한 트리 프로그램을 만들어 봅니다.
전위와 중위 탐색을 통하여 트리의 모습을 확인합시다.
/*=====================================================================================*/
/* Tree program.
/* -1. 삽입, 삭제, SWAP, 출력, 종료 가 가능한 프로그램.
-2. 종료를 실행하기 전까지는 트리가 텅 비어도 실행.
/* -3. 출력시에 전위 & 중위를 사용해서 트리의 모양을 예측할수 있어야 함.
ex) A
/* ↙ ↘
B D 전위: A B C D E F G H I
/* ↘ ↙ ↘ 후위: B C A E D G H F I
C E F
/* ↙ ↘
G I
/* ↘
H
/* -4.
/*=====================================================================================*/
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#define MAXWORD 100
#define END 0
#define CONTINUE 1
/* the tree node -워드를 입력받을 트리를 구성하는 스트럭쳐.(root형태) */
typedef struct tnode {
char *word; // points to the text.
struct tnode *left; // left child.
struct tnode *right; // right child.
} t_node;
/**************** 함수 선언.******************/
struct tnode *addtree(struct tnode *, char *);
void Prev_treeprint(struct tnode *);
void Center_treeprint(struct tnode *);
int getword(char *word, int );
struct tnode *talloc(void);
t_node *swap(t_node *root);
t_node *Deltree(struct tnode *root,char *w);
//t_node *Left_seach(t_node *p);
t_node *Dellword(struct tnode *p,char *w);
t_node *parent;
t_node *Son;
t_node *head;
/*************************************************************/
/* word frequency count. 메인함수.*/
/*************************************************************/
int main(void){
t_node *result;
struct tnode *root; // left 와 right의 어머니.
char word[MAXWORD]; // keyword를 입력받을 배열. 트리에 삽입될 것.
int c,ch;
int n=CONTINUE;
root=NULL;
Son = parent = NULL;
puts(" ┌────────────────────────────────┐");
puts(" │ │");
puts(" │ § Tree Data Program § │");
puts(" │ │");
puts(" │ ▶ 원하는 메뉴를 입력하세요. │");
puts(" │ │");
puts(" │ ▶ 1.삽입 2.삭제 3.SWAP 4.출력 5.종료 │");
puts(" │ │");
puts(" └────────────────────────────────┘");
puts("");
while(n!=END){
printf("\n숫자를 입력하시오(1~5):");
ch = c = 0;
while((c=getchar())!='\n')
ch=c;
switch(ch){
case '1': //삽입
if((head = talloc())==NULL)
{
printf("error ");
exit(1);
}
head->word='\0';
head->left=head;
head->right=head;
while(getword(word, MAXWORD)!=EOF){
root = addtree(root, word);
head->right=root;
}
break;
case '2': //삭제
printf("삭제 원하시는 단어를 입력하십시오.\n");
scanf("%s",&word);
root=Deltree(root,word);
break;
case '3': //SWAP
result=swap(root);
printf("--------swap--------\n");
printf("전위순회(swap) :");
Prev_treeprint(result);
puts("");
printf("중위순회(swap) :");
Center_treeprint(result);
break;
case '4': //출력
if((head->right==NULL)||(head->right==head)){
printf("저장된 데이터가 없습니다.\n");
break;
}
else{
printf("전위순회 :");
Prev_treeprint(root);
puts("");
printf("중위순회 :");
Center_treeprint(root);
break;
}
case '5': //종료
printf("이용해 주셔서 감사합니다.\n");
n= END;
break;
default :
printf("Error!!! 숫자를 잘못 입력하셨습니다.\n");
break;
}
getchar();
}
return 0;
}
/*************************************************************/
/* getword.
/* -한계값을 준 getchar.
/*************************************************************/
int getword(char *word, int i)
{
int cnt=0;
printf("입력하시오. 종료시엔 ctrl+z : ");
while((*(word+cnt)=getchar())!= ' ' && *(word+cnt) != '\n')
{
if(cnt==(MAXWORD-1)){
printf("단어의 크기가 초과했습니다.\n");
exit(1);
}
if(*(word+cnt)==EOF)
return *(word+cnt);
cnt++;
}
*(word+cnt)='\0';
//printf("%s",word);
return *(word+cnt);
}
/*************************************************************/
/* Left_seach.
/* -삭제할 노드를 인자로 받아 왼쪽후손들중 제일 큰값을 찾는 함수.
/*************************************************************/
/*
t_node *Left_seach(t_node *p)
{
t_node *temp;
t_node *before;
temp=p->left;
before=p;
if(temp->right==NULL){
temp=temp->left;
free(p);
return temp;
}
else if(temp->left!=NULL){
temp=temp->right;
free(p);
return temp;
}
else {
while(temp->right!=NULL)
{
if(temp->right->right==NULL)
before=temp;
temp=temp->right;
}
before->right=NULL;
free(p);
return temp;
}
}
*/
/*************************************************************/
/* Del word.
/* -삭제를 원하는 키값을 인자로 받아 그 노드를 찾아주는 함수.
/*************************************************************/
t_node *Dellword(struct tnode *p,char *w)
{
t_node *temp;
int cond;
if(p==NULL){
printf("값을 잘못 입력하셨습니다.\n");
exit(1);
}
else if((cond = strcmp(w,p->word))==0){
Son=p;
return Son;
}
else if (cond < 0) // 루트보다 작으면 왼쪽 자식..
{
temp = Dellword(p->left, w);
if(Son == p->left)
parent = p;
}
else
{ // 크면 오른쪽 자식..
temp = Dellword(p->right, w);
if(Son == p->right)
parent = p;
}
return Son;
}
/*************************************************************/
/* Deltree routine.
/* -root와 그 자식이 될 word를 받아옴.
/* -return 값은 새로 생성되는 스트럭쳐.(word 를 삽입함)
/*************************************************************/
t_node *Deltree(struct tnode *root,char *w)
{
// int cond;
// t_node *previous;
t_node *deleted;
t_node *move;
t_node *before;
deleted = Dellword(root,w);
// printf("delete=%s\nparent=%s\n",deleted->word,parent->word);
if(deleted->left!=NULL){ //del의 왼 자식이 있으면
move = deleted->left;
if(deleted==root)
parent=head;
before = deleted;
if((move->right==NULL)&&(move->left==NULL))
{
parent->right=move;
if(deleted->right == move){
move->right=NULL;
move->left=deleted->left;
}
else{
move->right=deleted->right;
move->left=NULL;
}
}
else
{
while(move->right!=NULL)
{
before = move;
move = move->right;
}
if(move->left!=NULL)
before->right=move->left;
else
before->right=NULL;
if(parent->left == deleted)
parent->left = move;
else
parent->right = move;
if(deleted->right == move){
move->right=NULL;
move->left=deleted->left;
}
else{
move->right=deleted->right;
move->left=deleted->left;
}
}
}
else if((deleted->left==NULL)&&(deleted->right==NULL)){
if(deleted==root)
parent=head;
if(deleted==root)
head->right=NULL;
else if(parent->left == deleted)
parent->left = NULL;
else
parent->right = NULL;
}
else{
if(deleted==root)
parent=head;
move=deleted->right;
if(parent->left == deleted)
parent->left = move;
else
parent->right = move;
}
free(deleted);
root=head->right;
printf("삭제되었습니다.\n");
return root;
}
/*************************************************************/
/* addtree routine.
/* -root와 그 자식이 될 word를 받아옴.
/* -return 값은 새로 생성되는 스트럭쳐.(word 를 삽입함)
/*************************************************************/
struct tnode *addtree(struct tnode *p,char *w)
{
int cond;
if(p==NULL){
if((p = talloc())==NULL)
{
printf("error ");
exit(1);
}
if((p->word = (char*)malloc(strlen(w)+1))==NULL)
{
printf("error ");
exit(1);
}
strcpy(p->word,w); //strcpy.
p->left = p->right = NULL;
//parent=p;
}
else if ( (cond = strcmp(w, p->word)) == 0 ) // 루트랑 같으면 에라...
printf("\n삽입불가\n");
else if (cond < 0) // 루트보다 작으면 왼쪽 자식..
p->left = addtree(p->left, w);
else // 크면 오른쪽 자식..
p->right = addtree(p->right, w);
return p;
}
/*************************************************************/
/* Prev_treeprint.
/* - 전위 순회로 출력.
/*************************************************************/
void Prev_treeprint(struct tnode *p)
{
if(p != NULL){
printf("%s ",p->word);
Prev_treeprint(p->left);
Prev_treeprint(p->right);
}
}
/*************************************************************/
/* Center_treeprint.
/* - 중위 순회로 출력.
/*************************************************************/
void Center_treeprint(struct tnode *p)
{
if(p != NULL){
Center_treeprint(p->left);
printf("%s ",p->word);
Center_treeprint(p->right);
}
}
/*************************************************************/
/* talloc함수.
/* -
/*************************************************************/
struct tnode *talloc(void){
return (struct tnode *)malloc(sizeof(struct tnode));
}
/*************************************************************/
/* 중위표기를 후위로 즉 left right를 바꿔주는 함수.
/*************************************************************/
t_node *swap(t_node *root){
t_node *temp;
if((temp = talloc())==NULL)
{
printf("error ");
exit(1);
}
if(root==NULL)
return NULL;
temp->right=swap(root->left);
temp->left=swap(root->right);
temp->word = (char*)malloc(strlen(root->word)+1);
strcpy(temp->word,root->word);
return temp;
}
이 글은 스프링노트에서 작성되었습니다.
'Programming Language > C' 카테고리의 다른 글
| _Mini_Project3_인사관리 시스템 (2) | 2010.10.14 |
|---|---|
| C Tutorial (배열이용 Heaptree) (1) | 2010.10.14 |
| C Tutorial (tree SWAP) (0) | 2010.10.14 |
| C Tutorial (D.L_list QUE) (0) | 2010.10.14 |
| C Tutorial (L_list 선택정렬) (2) | 2010.10.14 |
