반응형
1. Figure 1 and 2 show the recursive traversal algorithms(or programs) of preorder and postorder, respectively. Write the respectively corresponding iterative traversal algorithms(or programs) of preorder and postorder.
<Figure 2. Postorder traversal algorithm>
<Figure 1. Preorder traversal algorithm>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include <stdio.h> #include <stdlib.h> //exit 함수 사용때문에 넣음 #define MAX_STACK_SIZE 10 //스택 최대 크기 typedef struct node* treepointer; //node 자료형 포인터의 새로운 이름 treepointer typedef struct node{ char data; treepointer leftchild, rightchild; }node; //node 구조체 자료형의 새로운 이름 node, 안에는 char형 data와 treepointer형 leftchild, rightchild가 들어있다. void push(treepointer stack[],treepointer item,int *top); treepointer pop(treepointer stack[],int *top); void iterpreorder(treepointer node); void iterpostorder(treepointer node); int main(void) { int i; // int형 변수 i treepointer root; //treepointer 형 포인터 변수 root node tree[MAX_STACK_SIZE]; // node 배열 tree 크기는 10 for(i=0;i<MAX_STACK_SIZE;i++) //i=0부터 10보다 작을때까지 반복 {tree[i].leftchild=0; tree[i].rightchild=0;tree[i].data=0;} //배열의 원소 초기화 tree[0].data='+'; tree[0].leftchild=&tree[1]; tree[0].rightchild=&tree[2]; tree[1].data='*'; tree[1].leftchild=&tree[3]; tree[1].rightchild=&tree[4]; tree[2].data='E'; tree[3].data='*'; tree[3].leftchild=&tree[5]; tree[3].rightchild=&tree[6]; tree[4].data='D'; tree[5].data='/'; tree[5].leftchild=&tree[7]; tree[5].rightchild=&tree[8]; tree[6].data='C'; tree[7].data='A'; tree[8].data='B'; //문제에서와 같이 바이너리 트리 형성 root=&tree[0]; //root에 tree[0]의 주소 대입 (첫번째 노드) printf("preorder : ");iterpreorder(root); //preorder를 itr로 구현한 함수 호출 printf("postorder : ");iterpostorder(root);//postorder를 itr로 구현한 함수 호출 return 0; } void push(treepointer stack[],treepointer item,int *top) { if(*top>=MAX_STACK_SIZE-1) //만약에 top이가리키는주소의 값이 9이상이라면 {fprintf(stderr,"스택 과부하 원소 추가 불가능\n"); // 문장 출력하고 exit(EXIT_FAILURE);} //프로그램 종료 stack[++(*top)]=item; //stack의 맨 위에 item 삽입 } treepointer pop(treepointer stack[],int *top) { if((*top)==-1) //top이 가리키는 주소의 값이 -1 이라면 {fprintf(stderr,"스택 비어있음\n"); //문장 출력하고 exit(EXIT_FAILURE);} //프로그램 종료 return stack[(*top)--]; //제일 위에 있는 원소 return } void iterpreorder(treepointer node) { int top=-1; //int 형 변수 top을 -1로 초기화 treepointer stack[MAX_STACK_SIZE]; //treepointer 형 포인터배열 stack 크기는 10 push(stack,node,&top); //node를 stack에 쌓는다. while(1){ if(top==-1) break; //top이 -1이면 루프 탈출 어차피 마지막이 아니면 top이 -1이 될 일이 없다. node=stack[top]; //node에 stack의 top 원소 삽입 printf("%c", node->data); //node의 data 출력 pop(stack,&top); //stack의 top원소 pop if(node->rightchild) //node가 가리키는 구조체node에 rightchild가 있으면 push(stack,node->rightchild,&top); //stack에 쌓는다. if(node->leftchild) //node가 가리키는 구조체node에 leftchild가 있으면 push(stack,node->leftchild,&top); //stack에 쌓는다. } printf("\n"); //개행문자 출력 } void iterpostorder(treepointer node) { int top1=-1; //int 형 변수 top1을 -1로 초기화 int top2=-1; //int 형 변수 top2을 -1로 초기화 treepointer stack1[MAX_STACK_SIZE]; //treepointer 형 포인터배열 stack1 크기는 10 treepointer stack2[MAX_STACK_SIZE]; //treepointer 형 포인터배열 stack2 크기는 10 push(stack1,node,&top1); //node를 stack1에 쌓는다. while(1) { if(top1==-1)break; //top1이 -1이면 루프 탈출 어차피 마지막이 아니면 top1이 -1이 될 일이 없다. node=pop(stack1,&top1); //node에 stack에서 pop한 원소를 대입 push(stack2,node,&top2); // stack2에 node를 삽입 if(node->leftchild) //node가 가리키는 구조체node에 leftchild가 있으면 push(stack1,node->leftchild,&top1); //stack1에 쌓는다. if(node->rightchild) //node가 가리키는 구조체node에 rightchild가 있으면 push(stack1,node->rightchild,&top1); //stack1에 쌓는다. } while(1) { if(top2==-1)break; //top2가 -1이면 루프 탈출 어차피 마지막이 아니면 top2가 -1이 될 일이 없다. node=pop(stack2,&top2); //node에 stack2에서 pop한 원소 대입 printf("%c", node->data); //character type으로 출력 } printf("\n"); //개행문자 출력 } | cs |
2. Write a C function that searches for an arbitrary element in a max heap. What is the computing time of your function?
<Figure 3. Max heap>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <stdio.h> #define MAX_SIZE 8 //스택 최대 크기 typedef struct node* treepointer; //node 자료형 포인터의 새로운 이름 treepointer typedef struct node{ int data; treepointer leftchild, rightchild; }node; //node 구조체 자료형의 새로운 이름 node, 안에는 char형 data와 treepointer형 leftchild, rightchild가 들어있다. void search_max_heap(treepointer ptr,treepointer *res,int value); int main(void) { int i; // int형 변수 i treepointer root; //treepointer 형 포인터 변수 root treepointer res=0; //결과 값을 저장할 treepointer res node tree[MAX_SIZE]; // node 배열 tree 크기는 10 for(i=0;i<MAX_SIZE;i++) //i=0부터 10보다 작을때까지 반복 {tree[i].leftchild=0; tree[i].rightchild=0;tree[i].data=0;} //배열의 원소 초기화 tree[0].data=14; tree[0].leftchild=&tree[1]; tree[0].rightchild=&tree[2]; tree[1].data=12; tree[1].leftchild=&tree[3]; tree[1].rightchild=&tree[4]; tree[2].data=7; tree[2].leftchild=&tree[5]; tree[3].data=10; tree[4].data=8; tree[5].data=6; //교과서와 같이 트리 생성 root=&tree[0]; //root에 tree[0]의 주소 대입 (첫번째 노드) printf("번호 값 주소\n"); for(i=0;i<MAX_SIZE;i++) {printf("[%d]번 노드 : %d %d\n",i,tree[i].data,&tree[i]);} //트리의 각 노드 값과 주소 출력 search_max_heap(root,&res,10); //서치 펑션 호출, 10을 찾음 printf("찾은값 해당주소\n"); printf("%d %d\n",res->data,res); //찾고싶은 값의 주소와 값을 가리키는 res 출력 return 0; } void search_max_heap(treepointer ptr,treepointer *res,int value) { if(ptr){ //ptr이 NULL이 아니면 if(ptr->data==value) //ptr이 가리키는 data가 value와 같으면 *res=ptr; //res가 가리키는 포인터에 ptr의 주소 대입 else if(((ptr->data)>value)){ //ptr->data가 value보다 크면 search_max_heap(ptr->leftchild,res,value); //ptr->leftchild로 서치 펑션 재귀적 호출 search_max_heap(ptr->rightchild,res,value);} //ptr->rightchild로 서치 펑션 재귀적 호출 else if((ptr->data)<value){ //ptr->data가 value보다 작으면 printf("%d는 %d보다 작다.\n",ptr->data,value); //아무것도 안해도 되지만 디버깅 위해 문장 출력 }} } | cs |
3. Write the swapTree function of C that swap left child and right child of all nodes.
<Figure 4. swapTree>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include <stdio.h> #define MAX_SIZE 10 //스택 최대 크기 typedef struct node* treepointer; //node 자료형 포인터의 새로운 이름 treepointer typedef struct node{ char data; treepointer leftchild, rightchild; }node; //node 구조체 자료형의 새로운 이름 node, 안에는 char형 data와 treepointer형 leftchild, rightchild가 들어있다. void swap_bin_tree(treepointer ptr); void print(treepointer ptr); int main(void) { int i; // int형 변수 i treepointer root; //treepointer 형 포인터 변수 root node tree[MAX_SIZE]; // node 배열 tree 크기는 10 for(i=0;i<MAX_SIZE;i++) //i=0부터 10보다 작을때까지 반복 {tree[i].leftchild=0; tree[i].rightchild=0;tree[i].data=0;} //배열의 원소 초기화 tree[0].data='A'; tree[0].leftchild=&tree[1]; tree[0].rightchild=&tree[2]; tree[1].data='B'; tree[1].leftchild=&tree[3]; tree[1].rightchild=&tree[4]; tree[2].data='C'; tree[2].leftchild=&tree[5]; tree[3].data='D'; tree[3].rightchild=&tree[6]; tree[4].data='E'; tree[5].data='F'; tree[5].rightchild=&tree[7]; tree[6].data='G'; tree[7].data='H'; //교과서와 같이 이진 트리 구현 root=&tree[0]; //root에 tree[0]의 주소 대입 (첫번째 노드) printf("번호 값 주소\n"); for(i=0;i<MAX_SIZE;i++) {printf("[%d]번 노드 : %c %d\n",i,tree[i].data,&tree[i]);} //각 노드의 값과 주소 출력 swap_bin_tree(root); //트리 스왑 print(root); //스왑된 트리 확인 return 0; } void swap_bin_tree(treepointer ptr) { treepointer temp; //treepointer 즉 node의 포인터 temp if(ptr){ //ptr이 NULL이아니면 temp=ptr->leftchild; ptr->leftchild=ptr->rightchild; ptr->rightchild=temp; //temp라는 빈 물 컵을 이용해 left와 right의 스왑 if(ptr->leftchild) //leftchild가 null이 아니면 (불필요한 반복 줄이기 위해 한번 더 검사) swap_bin_tree(ptr->leftchild); //스왑 if(ptr->rightchild) //rightchild가 null이 아니면 (불필요한 반복 줄이기 위해 한번 더 검사) swap_bin_tree(ptr->rightchild); //스왑 }} void print(treepointer ptr) { if(ptr){ printf("노드 : %c %d\n",ptr->data,ptr); //노드 값, 주소 출력 if(ptr->leftchild) //ptr->leftchild가 NULL이 아니면 (불필요한 반복 줄이기 위해 한번 더 검사) printf("노드 왼쪽 자식 : %c %d\n",(ptr->leftchild)->data,ptr->leftchild); //노드 왼쪽 자식 값, 주소 출력 if(ptr->rightchild) //ptr->rightchild가 NULL이 아니면 (불필요한 반복 줄이기 위해 한번 더 검사) printf("노드 오른쪽 자식 : %c %d\n",(ptr->rightchild)->data,ptr->rightchild); //노드 오른쪽 자식 값, 주소 출력 if(ptr->leftchild) //ptr->leftchild가 NULL이 아니면 print(ptr->leftchild); // 재귀호출 프린트 if(ptr->rightchild) //ptr->rightchild가 NULL이 아니면 print(ptr->rightchild); //재귀호출 프린트 } } | cs |
반응형
'컴퓨터 & 프로그래밍 & 전자공학 > Data Sturcture' 카테고리의 다른 글
| 데이터 스트럭처 보고서 (0) | 2017.10.16 |
|---|---|
| dfs, bfs, prim, kruskal (0) | 2017.10.01 |
| stack, queue (0) | 2017.10.01 |
| 참고 사항 (0) | 2017.10.01 |
| 하노이의 탑, iterative, recursive fucntcion, 이진 탐색 (0) | 2017.10.01 |
