[자료구조] BFS&DFS&BST

소개글

[자료구조] BFS&DFS&BST에 대한 보고서 자료입니다.

본문내용

eft_child->count])
addq(front, &rear, tree->left_child);
if(tree->right_child && !visited[tree->right_child->count])
addq(front, &rear, tree->right_child);
}
else break;
}
}
void Preorder(tree_ptr tree){ /* preorder */
if(tree){
printf("%d\t", tree->key);
Preorder(tree->left_child);
Preorder(tree->right_child);
}
}
void Inorder(tree_ptr tree){ /* inorder */
if(tree){
Inorder(tree->left_child);
printf("%d\t", tree->key);
Inorder(tree->right_child);
}
}
void Postorder(tree_ptr tree){ /* postorder */
if(tree){
Postorder(tree->left_child);
Postorder(tree->right_child);
printf("%d\t", tree->key);
}
}
void zeroVisited(){ /* 전역배열 visited[]를 초기화 해준다. */
int i;
for(i=0; i visited[i] = FALSE;
}
name_ptr MakeName(char *a){ /* 이름 생성 */
name_ptr Newname;
Newname = malloc(sizeof(struct NameType));
if(Newname == NULL){
printf("Malloc() couldn't find any memory\n");
exit(1);
}
strcpy(Newname->name, a);
Newname->next = NULL;
Newname->down = NULL;
return Newname;
}
tree_ptr MakeTree(int num){ /* 트리 생성 */
tree_ptr Newtree;
Newtree = malloc(sizeof(struct TreeType));
if(Newtree == NULL){
printf("Malloc() couldn't find any memory\n");
exit(1);
}
Newtree->key = num;
Newtree->count = 0;
Newtree->left_child = NULL;
Newtree->right_child = NULL;
Newtree->parent = NULL;
return Newtree;
}
void level_tree(char *a){
name_ptr aname;
tree_ptr tree;
aname = CompareName(a);
if(aname == NULL){
printf("There isn,t choice name\n");
return;
}
tree=aname->down;
level_order(tree);
printf("\n");
}
void level_order(tree_ptr tree){ /* circular queue를 사용한 level_order */
int front=0, rear=0;
if(!tree) return ;
addq(front, &rear, tree);
while(front != rear){ /* 마지막에 left_child, right_child둘중 없는 경우가 발생하는 것을 막는다. */
tree=deleteq(&front, rear);
if(tree){
printf("%d\t", tree->key);
if(tree->left_child)
addq(front, &rear, tree->left_child);
if(tree->right_child)
addq(front, &rear, tree->right_child);
}
else break;
}
}
void addq(int front, int *rear, tree_ptr tree){ /* addq */
*rear = (*rear+1) % MAX_QUEUE_SIZE;
if(front == *rear){
--(*rear);
printf("Queue is full\n");
return;
}
queue[*rear] = tree;
}
tree_ptr deleteq(int *front, int rear){ /* deleteq */
if(*front == rear){
printf("Queue is empty!\n");
return NULL;
}
*front = (*front+1) % MAX_QUEUE_SIZE;
return queue[*front];
}
hw10.out
[Menu: 1.Insert, 2.Delete, 3.Pre, 4.In, 5.Post, 6.Level, 7.DFS, 8.BFS, 9.Exit]choice? 1 BST1
Enter the number(s) to be inserted to BST1: 30 50 10 80 5 40 20 100
choice? M
[Menu: 1.Insert, 2.Delete, 3.Pre, 4.In, 5.Post, 6.Level, 7.DFS, 8.BFS, 9.Exit]choice? I BST1
Enter the number(s) to be inserted to BST1: 1
choice? N BST1
1 5 10 20 30 40 50 80 100
choice? f BST1
30 10 5 1 20 50 40 80 100
choice? 8 BST1
30 10 50 5 20 40 80 1 100
choice? I BST1
Enter the number(s) to be inserted to BST1: 200
choice? N BST1
1 5 10 20 30 40 50 80 100
choice? D BST1
Enter the number(s) to be deleted from BST1: 30
choice? p BST1
40 10 5 1 20 50 80 100
choice? x
Thanks to you, Using my program. Have a nice Day!

키워드

자료구조,   BFS,   DFS,   BST,   트리