수다닷컴

#includestdio.h
#includestdlib.h
typedef struct List
{
int data;
struct List *L_link;
struct List *R_link;
}List;
List *root;
void UI();
void insert_f(int insert_value);
void delete_f(int delete_value);
void main()
{
root = NULL;
UI();
}
void UI()
{
int insert_value, delete_value;
int num;
while(1)
{
printf(\n);
printf(삽입은 1, 삭제는 2를 입력하세요(처음입력값은 루트값이 됩니다) : );
scanf(%d, &num);
if(num == 1)
{
printf(삽입할 값을 입력하세요 : );
scanf(%d, & insert_value);
insert_f(insert_value);
}
if(num == 2)
{
printf(삭제할 값을 입력하세요 : );
scanf(%d, & delete_value);
delete_f(delete_value);
}
}
}
void insert_f(int insert_value)
{
List *search; // 탐색노드
List *parents; // 삽입될 노드의 부모노드
List *insert_node; // 삽입될 노드
search = root; // 탐색위치 초기화
while(search != NULL)
{
parents = search;
if(search - data insert_value)
{
search = search - L_link;
}
else if(search - data insert_value)
{
search = search - R_link;
}
else
{
break;
}
}
insert_node = (List *)malloc(sizeof(List));
insert_node - data = insert_value;
if(root == NULL)
{
root = insert_node;
insert_node - L_link = NULL;
insert_node - R_link = NULL;
}
else if(parents - data insert_node - data)
{
parents - L_link = insert_node;
insert_node - L_link = NULL;
insert_node - R_link = NULL;
}
else if(parents - data insert_node - data)
{
parents - R_link = insert_node;
insert_node - L_link = NULL;
insert_node - R_link = NULL;
}
else
{
printf(입력하신 값이 존재합니다.\n);
free(insert_node);
}
}
void delete_f(int delete_value)
{
List *del_node; // 삭제될 노드
List *parent = NULL; // 삭제될 노드의 부모노드
del_node = root; // 탐색위치 초기화
List *right = root - R_link; // 삭제될 노드가 루트일때 오른쪽 삽입
List *left = root - L_link; // 삭제될 노드가 루트일때 왼쪽 삽입
while(del_node != NULL && delete_value != del_node - data)
{
parent = del_node;
if(del_node - data delete_value)
{
del_node = del_node - L_link;
}
else
{
del_node = del_node - R_link;
}
}
if(del_node == NULL)
{
printf(삭제하려는 값이 노드에 없습니다.\n);
UI();
}
else if(del_node - L_link == NULL && del_node - R_link == NULL)
{
if(del_node == root)
{
root = NULL;
}
else if(parent - data del_node - data)
{
parent - L_link = NULL;
}
else
{
parent - R_link = NULL;
}
}
else if(del_node - L_link == NULL || del_node - R_link == NULL)
{
if(del_node - data == root - data) // 삭제할 노드가 root일 경우
{
if(del_node - L_link != NULL)
{
parent = del_node - L_link;
}
else
{
parent = del_node - R_link;
}
root = parent;
}
else
{
if(del_node - data parent - data)
{
parent - L_link = NULL;
if(del_node - L_link != NULL)
{
parent - L_link = del_node - L_link;
}
else
{
parent - L_link = del_node - R_link;
}
}
else
{
parent - R_link = NULL;
if(del_node - L_link != NULL)
{
parent - R_link = del_node - L_link;
}
else
{
parent - R_link = del_node - R_link;
}
}
} // end else
} // else if(del_node - L_link == NULL || del_node - R_link == NULL)
else
{
List *p_searching = NULL; // 삭제된 노드의 부모노드
List *p_right = del_node - R_link; // 삭제된 노드가 가리키던 오른쪽 노드
List *p_left = del_node - L_link; // 삭제된 노드가 가리키던 왼쪽 노드
List *son = root - L_link; // 후계자 노드
while(son - R_link != NULL) // 후계자 노드 탐색
{
p_searching = son;
son = son - R_link;
}
if(p_searching == NULL)
ULL)
{
p_searching = del_node;
}
if(del_node - data == root - data) // 삭제하려는 노드가 루트일때
{
if(p_searching == NULL) // 루트에 자식노드가 왼쪽 오른쪽 두개 뿐일 때
{
p_searching = del_node - L_link;
p_searching - L_link = NULL;
p_searching - R_link = p_right;
root = p_searching;
}
else // 루트에 자식노드가 여러개일 때
{
root = son;
p_searching - R_link = NULL;
root - R_link = right;
root - L_link = left;
}
}
else
{
if(del_node - data parent - data)
{
parent - R_link = NULL;
parent - R_link = son;
p_searching - R_link = NULL;
son - R_link = p_right;
if(son == son - R_link)
{
son - R_link = NULL; // 후계자노드와 자식노드가 가리키는 오른쪽 노드의 값이 같을때
}
son - L_link = p_left;
}
else
{
parent - L_link = NULL;
parent - L_link = son;
p_searching - R_link = NULL;
son - R_link = p_right;
if(son == son - R_link)
{
son - R_link = NULL; // 후계자노드와 자식노드가 가리키는 오른쪽 노드의 값이 같을때
}
son - L_link = p_left;
}
}
} // end else
List *debug = root; // 디버깅용
free(del_node);
} // end void delete_f(int delete_value)

헉헉...;; 변수 사용을 잘못했는지 코드가 너무 길어졌네요.....;;
특히나 삭제함수부분에서 예외처리 하느라 너무 시간을 끌었네요...ㅠ.ㅠ
그리고 // 후계자노드와 자식노드가 가리키는 오른쪽 노드의 값이 같을때 -- 이 주석달린 부분은 없어도 될것 같은데
제 프로그램 상 어쩔수 없이 해야만 했네요.....예외처리 때문에....ㅠ.ㅠ
이거 좀 간단하게 짤수 없을까요?
재귀함수로도 이진트리를 구현할 수 있다는데 어떻게 해야 하나요?
혹시 아시는 분은 알고리즘이나 소스좀 보여주세요.
그리고 비단 이진트리가 아니더라도 이 소스보단 더 간략하게 줄일수 있을것 같은데
이 소스를 간단하게 줄일수 있는 것과 재귀함수로 구현한 이진트리에 대해 알고리즘이나 소스를
알려주시면 정말 감사하겠습니다.

신청하기