preorder, postorder, inorder, heap, tree

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>

#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"); //개행문자 출력
    }
 

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>

#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); //아무것도 안해도 되지만 디버깅 위해 문장 출력
    }}
    
}

3. Write the swapTree function of C that swap left child and right child of all nodes.

<Figure 4. swapTree>

#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); //재귀호출 프린트
    }
}