트리 - 전위&중위 순회 알고리즘

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define mal (node *)malloc(sizeof(node))

typedef struct _node 

{

char data;

struct _node *left;

struct _node *right;

int degree;

int level;

}node;

node *head, *end, *stack[8], *parent, *leftChild, *rightChild;

int top = 0, bool_treeCount = 0, degreecursor = 1, levelcursor = 1, bool_fullTree = 0

, bool_firstpop = 0;

void push(node *cursor);

node *pop();

int stackEmpty();

void addtree(); //add

void preview(node *cursor); //view - pre

void inview(node *cursor); // view - in

void arrow(char a);

void push(node *cursor)

{

stack[top] = cursor;

top = (top++) % 8;

}

node *pop()

{

node *cursor;

if (!stackEmpty())

{

cursor = stack[--top];

return cursor;

}

else

printf("Error::스택에 든 값이 없습니다!\n");

return NULL;

}

int stackEmpty()

{

int a;

(top == 0) ? (a = 1) : (a = 0);

return a;

}

void addtree()

{

if (levelcursor == 3 && degreecursor == 5)

{

printf("Error::더 이상 추가할 수 없습니다!\n");

return NULL;

}

if (bool_treeCount == 0)

{

parent = mal;

printf("글자를 입력해주세요 : ");

parent->data = getchar();

head->left = parent, head->right = parent;

parent->left = end, parent->right = end;

++bool_treeCount;

++levelcursor;

}

else if (levelcursor == 2)

{

if (degreecursor == 1)

{

leftChild = mal;

parent->left = leftChild;

leftChild->left = end, leftChild->right = end;

parent = leftChild;

++degreecursor;

}

else

{

rightChild = mal;

head->right->right = rightChild;

rightChild->left = end, rightChild->right = end;

parent = rightChild;

--degreecursor;

++levelcursor;

}

printf("글자를 입력해주세요 : ");

parent->data = getchar();

}

else

{

if (degreecursor < 3)

parent = head->left->left;

else

parent = head->right->right;

printf("글자를 입력해주세요 : ");

if (degreecursor % 2 == 1)

{

leftChild = mal;

parent->left = leftChild;

leftChild->data = getchar();

leftChild->left = end, leftChild->right = end;

}

else

{

rightChild = mal;

parent->right = rightChild;

rightChild->data = getchar();

rightChild->left = end, rightChild->right = end;

}

++degreecursor;

}

}

void preview(node *cursor)

{

push(cursor);

while (!stackEmpty())

{

cursor = pop();

arrow(cursor->data);

if (cursor->right != end)

push(cursor->right);

if (cursor->left != end)

push(cursor->left);

}

}

void inview(node *cursor)

{

if (cursor != end)

{

inview(cursor->left);

arrow(cursor->data);

inview(cursor->right);

}

}

void arrow(char a)

{

(bool_firstpop != 0) ? (printf(" -> ")) : (++bool_firstpop);

printf("%c", a);

}

int main()

{

char command[5];

head = mal, end = mal;

head->left = end, head->right = end, end->left = end, end->right = end;

head->degree = -1, head->level = -1, end->degree = -1, end->level = -1;

printf("이 프로그램은 이진트리 입출력 프로그램입니다.\n단, level은 최대 3으로 한정합니다.\n노드 추가는 중위 순회 방식을 따릅니다.\n명령어는 다음과 같습니다.\n");

while (1)

{

printf("add-트리의 노드 추가, view-트리 출력, exit-종료\n명령어를 입력해주세요 : ");

scanf("%s", &command);

if (!strcmp(command, "add"))

{

while (getchar() != '\n');

addtree();

}

else if (!strcmp(command, "exit"))

break;

else if (!strcmp(command, "view"))

{

printf("전위 출력 - pre, 중위 출력 - in\n명령어를 입력해주세요 : ");

scanf("%s", &command);

if (!strcmp(command, "pre"))

preview(head->left);

else if (!strcmp(command, "in"))

inview(head->left);

else

continue;

printf("\n");

--bool_firstpop;

}

else

printf("잘못 입력하셨습니다.\n");

}

return 0;

}