수다닷컴

#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 pre_print(List *root); // 전위순회
void in_print(List *root); // 중위순회
void post_print(List *root); // 후위순회
void main()
{
root = NULL;
UI();
}
void UI()
{
int insert_value, delete_value;
int num;
while(1)
{
printf(\n);
printf(삽입1, 삭제2, 전위순회3, 중위순회4, 후위순회5 입력(처음입력값은 루트값) : );
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);
}*/
if(num == 3)
{
pre_print(root);
}
if(num == 4)
{
in_print(root);
}
if(num == 5)
{
post_print(root);
}
}
}
void pre_print(List *root)
{
if(root)
{
printf(%d - , root - data);
pre_print(root - L_link);
pre_print(root - R_link);
}
}
void in_print(List *root)
{
if(root)
{
in_print(root - L_link);
printf(%d - , root - data);
in_print(root - R_link);
}
}
void post_print(List *root)
{
if(root)
{
post_print(root - L_link);
post_print(root - R_link);
printf(%d - , root - data);
}
}
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);
}
}
가령 제가 이진트리에다가 값을 100-80-120-70-90-110-130 이렇게 삽입했습니다.
그리고 전위수식으로 출력했다고 치면 재귀함수로 출력하는데 재귀함수가 자기자신을 호출한다는건 이해가 됩니다.
그런데 null을 만난 이후에 함수가 위로 올라가더군요?
즉 70이 가리키는 L_link가 null을 만나면 L_link함수가 끝나는데
다음번에 또 호출할때 70으로 올라갔다가????????
올라간 70이 다시 R_link로 가보고
70이 가리키는 R_link도 널이되니깐
80으로 올라가더군요???????????????????
그리고 나서 80이 가리키는 R_link로 가더군요
그리고 나서 80이 가리키는 R_link에 90이 있으니까 이 90을 출력했다가
90이 가리키는 L_link로 가더군요????????
그리고 L_link가 null이 되니깐
다시 90으로 올라가고...........
그 90이 다시 R_link를 가리키고.........
R_link가 null이 되니깐 80으로 올라갔다가......
다시 100으로 올라가더군요???????????????
그리고 이번엔 100이 가리키는 R_link로 가보고.........
120을 출력한후 위에 쓴 부분이 반복되더군요......
이거 어떤 원리로 함수가 null을 만나게 되면 다시 그전 단계로 올라가는 건가요?
이것 때문에 햇갈리네요.......
위로 올라가는 것 때문에요.......
그리고 R_link함수에서 예를 들면 아까 90에서 다시 L_link로 간후 null이니깐
90으로 올라갔다가 다시 R_link를 가리키고 이것도 null이 되니깐
80으로 올라가는???????
이 원리를 좀 설명해 주시면 정말 감사하겠습니다.
아무리 책을 읽고 디버깅을 해봐도 잘 이해가 안되네요...
밑으로 타고 내려오는건 이해가 되는데 null을 만나니깐 함수가끝난뒤 왜 이전 단계로 다시 올라가는지...;;;;;;;;;;;;;;;;
그렇게 다 순회를 한후 올라갈 값이 완전히 없어야 함수를 끝내더군요.....;;;
??????????한 부분을 중심으로 정말 이해가 안됩니다 ㅠ.ㅠ

신청하기