수다닷컴

질문 제목 : bst(이진탐색트리)에 존재하는 모든 branches(가지들)의 depth(깊이)를 구하는 방법이진탐색트리에서 모든 branch들의 depth를 찾아array로 저장한 다음, 최대값, 최소값,평균값, 표준편차 찾기질문 내용 :

과제중입니다. 자료구조요..

이제 bst에 대해선 거의 숙지를 하고, 본격적으로 교수님이 요구하는 부분을 건드리려 하는데

도무지 감이 안잡히네요.교수님께서 요구하신 사항은, bst의 자료구조속에 자료를 넣고, 그 bst의 최대 깊이, branch중의 최소 깊이, 모든 branch들의 평균 깊이, 그리고 표준편차를 구하라는 겁니다. 물론 프로그래밍으로요,

최대 depth구하는건 구현했습니다.

그런데 아무 쓸모가 없더군요.. 일단 다 알아야 표준편차를 구하든가 하니깐요.ㅠ 자료의 갯수는 64개, 128개 이렇게 늘릴겁니다. 지금 아래에서는 실험적으로 10이로 지정해 놓았습니다.

소스 코드는 다음과 같습니다.

밑에 xml:namespace prefix...뭐 이런건 왜 뜨는지 모르겠네요 ㅠ 지우고 돌려보세요#include stdio.h
#include stdlib.h?xml:namespace prefix = o /?xml:namespace prefix = o /
#include math.h
#include time.h
#include stdbool.h
#include ctype.h
#include windows.htypedef struct node
{
int* dataptr;
struct node* left;
struct node* right;
}node;

typedef struct
{
int count;
int (*compare)(void* argu1, void* argu2);
node* root;
}bst_tree;

typedef struct
{
char h;
int numvalue;

} value;
bst_tree* bst_destroy(bst_tree* tree);
void bst_insert(bst_tree* tree, int* dataptr);
void bst_delete(bst_tree* tree, int* dltkey);
void* bst_retrieve(bst_tree* tree, int* keyptr);
void bst_traverse(bst_tree* tree, void (*process)(int* dataptr));
bool bst_empty(bst_tree* tree);
bool bst_full(bst_tree* tree);
int bst_count(bst_tree* tree);

static node* _insert(bst_tree* tree, node* root, node* newptr);
static node* _delete(bst_tree* tree, node* root, int* dataptr, bool* success);
static void* _retrieve(bst_tree* tree, int* dataptr, node* root);
static void _traverse(node* root, void (*process)(int* dataptr));
static void _destroy(node* root);bst_tree* bst_create(int (*compare)(void* argu1, void* argu2));
int createrand(void);
int comparevalue(void* num1, void* num2);
void addvalue(bst_tree* list, int val);
void printlist (bst_tree* list);
void processvalue(void* dataptr);
int max_depth(node* data);

int main(void)
{
int run, secondrun, valtocompare, standard;//variables for creating and comparing random values
int h, l, m, d;//h=highst depth of the tree, l=lowest depth of the tree, m=mean of the depth of branches
// d: standard deviation of depth of the tree
int lastnum=10; //n
int numarray[10];
bool isnumberalreadyin=false;

bst_tree* numtree;
srand((unsigned int)gettickcount());
numtree = bst_create(comparevalue);

for (run=0; runlastnum; run++)
{
valtocompare=rand()%1000;
numarray[run]=valtocompare;
while(!isnumberalreadyin)
{
standard=0;
for(secondrun=0; secondrun=run; secondrun++)
{
if (numarray[secondrun]==valtocompare)
{
valtocompare=rand()%1000;
standard++;
}
}

if (standard==0)
isnumberalreadyin=true;
}

addvalue(numtree, valtocompare);
}

printlist(numtree);
h=max_depth(numtree-root); //depth의 최댓값 구하기!

numtree = bst_destroy(numtree);

getch();
return 0;
}int comparevalue(void* num1, void* num2)
{
value firstnumber;
value secondnumber;

firstnumber = *(value*)num1;
secondnumber= *(value*)num2;

if(firstnumber.numvalue secondnumber.numvalue)
return -1;

if(firstnumber.numvalue secondnumber.numvalue)
return 1;
}

void addvalue(bst_tree *list, int randomvalue)
{

value* valptr;

valptr=(value*)malloc(sizeof(value));

if(!valptr)
printf(memory overflow in add\n);

valptr-numvalue=randomvalue;
bst_insert(list, valptr);

}
void printlist (bst_tree* list)
{
printf(\ntree list:\n);
bst_traverse (list, processvalue);
printf(end of the list\n);
return;
}

void processvalue(void* dataptr)
{
value avalue;
avalue = *(value*)dataptr;
printf(%d\n, avalue.numvalue);
return;
}

int max_depth(node* data)
{
int max = 0, depth;

if( data == null)
return 0;
else
{
depth = max_depth(data-left) + 1;
if( depth max)
max = depth;
depth = max_depth(data-right) + 1;
if( depth max)
max = depth;
return max;
}}//이건 depth의 최대값 구하는 함수

bst_tree* bst_create(int (*compare)(void* argu1, void* argu2))
{
bst_tree* tree;

tree=(bst_tree*)malloc(sizeof(bst_tree));
if(tree)
{
tree-root = null;
&nbsbsp; tree-count = 0;
tree-compare = compare;
}

return tree;
} //bst_create

bst_tree* bst_destroy(bst_tree* tree)
{
if(tree)
_destroy(tree-root);

free(tree);
return null;
} //bst_destroy

void bst_insert(bst_tree* tree, void* dataptr)
{
node* newptr;

newptr = (node*)malloc(sizeof(node));
if(!newptr)
return false;

newptr-right = null;
newptr-left = null;
newptr-dataptr = dataptr;o:aptr;
if(tree-count == 0)
tree-root = newptr;
else
_insert(tree, tree-root, newptr);
(tree-count)++;

}//bst_insert

void bst_delete (bst_tree* tree, void* dltkey)
{
bool success;
node* newroot;

newroot=_delete(tree, tree-root, dltkey, &success);
if(success)
{
tree-root=newroot;
(tree-count)--;
if (tree-count ==0)
//tree is now empty
tree-root=null;
}

}

void* bst_retrieve (bst_tree* tree, void * keyptr)
{
if(tree-root)
return _retrieve(tree, keyptr, tree-root);
else
return null;
}//bst_retrieve

void bst_traverse (bst_tree* tree, void (*process)(void* dataptr))
{
_traverse(tree-root, process);
return;
}// bst_traversebool bst_empty (bst_tree* tree)
{
return (tree-count == 0);
} //bst_empty

bool bst_full (bst_tree* tree)
{
node* newptr;

newptr = (wptr = (node*)malloc(sizeof(*(tree-root)));
if(newptr)
{
free (newptr);
return false;
}
else
return true;
}//bst_full

int bst_count (bst_tree* tree)
{
return (tree-count);
}//bst_countstatic node* _insert(bst_tree* tree, node* root, node* newptr)
{
if(!root)
return newptr;

if(tree-compare(newptr-dataptr, root-dataptr)0)
{
root-left=_insert(tree, root-left, newptr);
return root;
}

else
{
root-right = _insert(tree, root-right, newptr);
return root;
}
return root;
}//_insert

static node* _delete(bst_tree* tree, node* root, void* dataptr, bool* success)
{
node* dltptr;
node* exchptr;
node* newroot;
void* holdptr;

if(!root)
{
*success = false;
return null;
}

if(tree-compare(dataptr, root-dataptr)0)
root-left = _delete(tree, root-left, dataptr, success);
else if (tree-compare(dataptr, root-dataptr) 0)
root-right = _delete(tree, root-right, dataptr, success);
else
{
dltptr=root;
if(!root-left)
{
free (root-dataptr);
newroot = root-right;
free(dltptr);
*success = true;
return newroot;
}
else
if(!root-right)
{
newroot = root-left;
free(dltptr);
*success = true;
return newroot;
}
else
{
exchptr = root-left;
while(exchptr-right)
exchptr = exchptr-right;

holdptr = root-dataptr;
root-dataptr = exchptr-dataptr;
exchptr-dataptr= holdptr;
&; root-left = _delete(tree, root-left, exchptr-dataptr, success);
}
}
return root;
}//_delete

static void* _retrieve(bst_tree* tree, void* dataptr, node* root)
{
if(root)
{
if (tree-compare(dataptr, root-dataptr)0)
return _retrieve(tree, dataptr, root-left);
else if (tree-compare(dataptr, root-dataptr)0)
return _retrieve(tree, dataptr, root-right);
else
return root-dataptr;
}

else
return null;
}//_retrieve

static void _traverse(node* root, void (*process)(void* dataptr))
{
if (root)
{
_traverse (root-left, process);
process(root-dataptr);
_traverse (root-right, process);
}
return;
}//_traverse

static void _destroy(node* root)
{
if (root)
{
_destroy(root-left);
free (root-dataptr);
_destroy(root-right);
free(root);
}
return;
}

신청하기