수다닷컴

질문 제목 : dfs(깊이우선검색, 스택이용) 질문입니다.밑에 코드 그대로 가져다 실행시키시면 바로 실행되는데요 그중 일부 노드는 경로가 구해지는대
일부 노드는 메모리 에러가 뜹니다.질문 내용 :

우선 코드 입니다.

#include stdio.h
#include stdlib.h
#include string.h

typedef struct treenode{
struct treenode *parent;
struct treenode *left;
int key;
struct treenode *right;
}treenode;

treenode *stack;
int size;
int top;

void initstack(int asize) //스택생성
{
size=asize;
stack=(treenode *)malloc(size*sizeof(treenode));
top=-1;
}

void freestack()//스택제거
{
free(stack);
}
int push(treenode* node)//스택 삽입
{
if (top size-1) {
top++;
stack[top]=*node;
return 0;
} else {
return -1;
}
}
int pop() //스택 탑 삭제
{
if (top = 0) {
stack[top--];
return 0;
} else {
return -1;
}
}
void insert_node(treenode **root, int key) //트리 삽입
{
treenode *p, *t;
treenode *n;
t=*root;
p=null;
while(t != null){
if(key == t-key)
return;
p=t;
if(keyt-key)
t=t-left;
else
t=t-right;
}
n=(treenode *)malloc(sizeof(treenode));
if(n==null)
return;
n-key=key;
n-left=n-right=null;
if(p!=null)
if(keyp-key)
{
p-left=n;
n-parent=p;
}
else
{
p-right=n;
n-parent=p;
}
else
{
*root=n;
(*root)-parent=n;
}
}
int shortest_route_stack(treenode* root, int key) //dfs이용해서 최단경로 찾고 그걸 출력하기위해서 부모노드사용
{
treenode* p=root;

push(p);
if(stack[top].key==key)
{
printf(경로 :%d\n, stack[top].key);
}
else
{
while(1)brle(1)
{
if(stack[top].key==key)
{
if(p-key!=stack[top].key)
p=&stack[top];

while(p-key!=root-key)
{
printf(%d-, p-key);
p=p-parent;
}
printf(%d\n, root-key);
return 0;
}
if((p-right==null)&&(p-left==null))
{
pop();
p=&stack[top];
}
else
{
pop();
if(p-right!=null) //여기가 아마 제가 에러가 뜨는 이유라고 생각이 드는데요...
push(p-right);안될라면 다안돼지 어떤건 돼고 몇개는 안돼니깐...미치겠습니다 ㅠ
if(p-left!=null)
push(p-left);
if(p-right-key==stack[top].key)
p=p-right;
if(p-left-key==stack[top].key)
p=p-left;
}
}
}
return 0;
}
preorder(treenode *root){//전체출력
if(root){
printf(%d , root-key);
preorder(root-left);
preorder(root-right);
}
}

int main()
{
treenode *list=null;
int sel=0, num=0;
initstack(256);
insert_node(&list, 10);
insert_node(&list, 5);
insert_node(&list, 3);
insert_node(&list, 7);
insert_node(&list, 15);
insert_node(&list, 12);
insert_node(&list, 18);
do{
puts(---------------------------------------------------------------);
puts(1.전체출력 2.최단경로 3.종료);
puts(---------------------------------------------------------------);
printf(사용하실 메뉴를 입력하세요 : );
scanf(%d, &sel);
switch(sel)
{
case 1:
puts(전체출력!!);
preorder(list);
puts();
puts();
puts();
break;
case 2:
printf(최단 경로를 확인하고 싶은 노드 입력 : );
scanf(%d, &num);
shortest_route_stack(list, num);
break;
case 3:
exit(1);
break;
}
}while(sel!=3);
return 0;
}
----------------------------------------------------------------------------

이걸 그대로 실행하시면 우선 입력은 제가 기본적으로 입력을 받아놨구요

입력은 이진트리 형태인데
10
515
37 1218
이러한 형태로 트리가 지금 입력돼어있는데요

10, 5, 15, 3, 7은 dfs탐색으로 최단경로가 탐색이돼는데요... 12와 18은 메모리 에러가 뜹니다.

짧은주석이나마 달아놨습니다ㅠㅠ 정말 제가 연습장에 스택그려가면서 여러번 해봤지만...

메모리 에러가 뜨는 이유를 모르겠습니다.........재발 도와주세요 고수님들 이거가지고 몇일째 고민중인지 한숨만...휴...

신청하기