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