어제 질문한 트리 노드 관련 질문입니다.
연블랙
질문 제목 :어제 질문한 트리 노드 관련 질문입니다.
질문 요약 :수다님의 답변대로 코드를 짠 결과, 제가 원하던 대로 결과가 나왔습니다. 문제는 이 트리 노드를 탐색할 때, 트리 노드가 모두 변해버려서 이 트리 노드의 탐색 횟수를 구하는데 문제가 있어서 질문 드립니다.질문 내용 :
#includestdio.h
#includestdlib.h
#includetime.htypedef struct tnode tnode;typedef struct tnode {
int data;
tnode *right, *left;
} tnode;tnode* getnode();
void const(tnode *);
void consn(tnode *[], tnode *, int);
void sons(int *, int, tnode **);
int get_height(tnode *);
int max(int, int);
int search(tnode *, int, int);
void printarray(int *);
void display(int, int);int main()
{
int a[30], i, height, ran, count, ave;
int sum = 0, c = 0;
tnode *t = getnode();
t-data = 0;
t-right = t-left = null;srand((unsigned)time(null));const(t);height = get_height(t);for (i = 0; i 30; i++)
{
sons(a, i, &t);if (a[i] 0)
{
while (a[i] 0)
{
sons(a, i, &t);
}
}
}printarray(a);for (i = 0; i 20; i++)
{
ran = rand() % 30;
count = search(t, a[ran], c);
sum = sum + count;
}ave = sum / 20;display(height, ave);free(t);
t = null;
return 0;
}tnode* getnode()
{
return (tnode *)malloc(sizeof(tnode));
}void const(tnode *t)
{
tnode *list[30];
int first = rand() % ((60 - 40) + 1) + 40;
int i, k, ran;srand((unsigned)time(null));list[0] = getnode();
list[0]-data = first;
list[0]-left = list[0]-right = null;for (i = 1; i 30; i++)
{
ran = (rand() % 100) + 1;list[i] = getnode();
list[i]-data = ran;
list[i]-right = null;
list[i]-left = null;
}again:
for (i = 0; i 30; i++)
{
for (k = i + 1; k 30; k++)
{
if (list[0]-data == list[k]-data)
{
list[0]-data = rand() % ((60 - 40) + 1) + 40;
goto again;
}else if (list[i]-data == list[k]-data)
{
list[i]-data = (rand() % 100) + 1;
goto again;
}
}
}t-data = list[0]-data;for (i = 1; i 30; i++)
{
consn(list, t, i);
}
}void consn(tnode *list[30], tnode *t, int data)
{
if (t == null)
{
t = list[data];
return;
}else if (t-left == null && list[data]-data t-data)
{
t-left = list[data];
return;
}else if (t-right == null && list[data]-data t-data)
{
t-right = list[data];
return;
}else
{
if (list[data]-data t-data)
{
&nbnbsp;consn(list, t-right, data);
return;
}else
{
consn(list, t-left, data);
return;
}
}
}void sons(int *a, int data, tnode **q)
{
if (data == 0)
{
if ((*q)-left != null)
{
sons(a, data, &(*q)-left);
}else
{
a[0] = (*q)-data;
(*q)-data = 0;if ((*q)-right != null)
{
(*q)-left = null;
return;
}else
{
*q = null;
return;
}
}
}else
{
if ((*q)-left != null)
{
sons(a, data, &(*q)-left);
}else if ((*q)-right != null)
{
if ((*q)-data == 0)
{
sons(a, data, &(*q)-right);
}else if ((*q)-data (*q)-right-data)
{
a[data] = (*q)-data;
(*q)-data = 0;
return;
}else
{
sons(a, data, &(*q)-right);
}
}else
{
if ((*q)-data == 0)
{
*q = null;
return;
}if ((*q)-right != null)
{
(*q)-left = null;
return;
}else
{
a[data] = (*q)-data;
*q = null;
return;
}
}
}
}int get_height(tnode *t)
{
if (t == null)
{
return 0;
}else
{
//t-left와 t-right의 높이 중 더 높은 값 + 1을 반환
return 1 + max(get_height(t-left), get_height(t-right));
}
}int max(int l, int r)
{
if (l = r)
{
return l; //l이 r보다 크거나 같다면 l을 반환한다
}
else
{
return r; //그렇지 않다면 r을 반환한다
}
}int search(tnode *t2, int key, int count)
{
if (t2 == null)
{
return 0;
}else if (t2-data == key)
{
count++;
return count;
}else if (t2-data key)
{
count++;
count = count + search(t2-right, key, count);
}else
{
count++;
count = count + search(t2-left, key, count);
}
return count;
}void printarray(int *a)
{
int i;for (i = 0; i 30; i++)
{
printf(%d , a[i]);
}
printf(\n);
}void display(int height, int ave)
{
printf(트리의 높이 : %d\n, height);
printf(평균 노드 탐색 횟수 : %d\n, ave);
}위 코드의 const함수가 실행하면 제가 원하던 트리 노드가 생성됩니다. 그리고 메인함수에서 for문과 while문을 사용해서 sons함수를 실행해서 배열에 제가 원하던 대로 오름차순으로 값이 저장됩니다. 문제는 이 코드가 실행된 후, 트리 노드 t의 노드들의 data값이 다 0이 되거나 몇 노드들은 null로 바뀐다는 점입니다. 제가 배열에 값을 넣기 위해서, 일부러 data값에 0을 넣거나 노드를 null로 바꾼건데요... search함수를 제대로 실행하려면 const함수 실행 후의 트리 노드 t가 유지되어야 한다는 점입니다.
그렇다고 sons함수의 매개변수를 이중포인터로 받지 않으면 배열에 제대로 된 값을 넣을 수도 없고... 어떻게 수정을 해야할지 도저히 모르겠습니다. 어떻게 해야될까요...ㅠ
