Tree and Queue(연산) in C

1. include and define

1. include and define

stdio를 include하고 queue를 이용하기 위해 queue의 최대 크기를 define 한다.

2. 구조체 선언과 Tree의 root

2. 구조체 선언과 Tree의 root

T(tree)Node 구조체를 선언한다

struct TNode *left : Tree에서 왼쪽 아래에 위치하는 것을 의미

char data : node의 내용

struct TNode *right : Tree에서 오른쪽 아래에 위치하는 것을 의미

TNode *root : TNode에 대한 (root)시작점을 알려주는 전역변수

Queue를 위한 구조체 선언

*data : queue에 저장 될 내용

[MAX_QUEUE_SIZE] : queue에 저장될 최대 갯수

3. Queue

오류가 발생하면 error message를 출력

queue의 front 와 rear값을 -1로 초기화

queue가 비어있다면 1(true) 아니면fault)반환

(front==rear) : empty

queue가 가득 차있다면 1(true) 아니면fault)반환

(front==MAX_QUEUE_SIZE) : full

queue에 node를 삽입하기 위한 함수

if(queue full이면) 에러코드는  queueFull

q안의 data[rear+1]의 위치에 item이라는 data를 저장

삭제(출력)를 위한 함수

if(queue empty이면) 에러코드는  queueEmpty

*q안의 data[front+1]의 내용을 반환

4. Tree 순회(traversal)evaluate

inorder traversal(data(출력)가 중간(in)에 있음)

if(r안의 left가 NULL이 아니면 다시 InOider함수를 호출해서(아까 NULL이 아니였던) r안의 left값을 넣음

(r->left가 NULL일 때 까지 반복(재귀함수))

r->left가 NULL이 되었으면

r->data를 출력

if(방금 data를 출력 한 r안의 right가 NULL이 아니면 다시 InOider함수를 호출해서(아까 NULL이 아니였던) r안의 right값을 넣음

다시 r->left check

r->data를 출력

다시 r->right check

쭉쭉쭉(재귀함수)

preorder traversal (data(출력)가 맨 앞(pre)에 있음)

postorder traversal  (data(출력)가 맨 뒤(post)에 있음)

levelorder traversal(위에서 부터 좌에서 우로 순차적으로 읽어나감)

사실 levelorder을 위에 queue를 구연함

ptr(root)가 NULL이면 retrun

변수 선언

queue 초기화(front=-1,rear=-1)

ptr(root)을 q라는 queue에 삽입

while (무한 반복) {

data에 queue값을 삽입(root가 삽입되는거임)

if(data가 null이면) 무한루프 탈출

data출력

if(data의 left가 null이 아니라면)

queue에 data의 left값을 삽입

if(data의 right가 null이 아니라면)

queue에 data의 right값을 삽입

if(queue가 비어있다면) 무한루프 탈출

5. evaluate

if(root가 NULL이면)종료

if(root의 left와 right가 NULL이면)root의 data를 반환

재귀함수의 exit 혹은 node가 root하나 일때를 대비

op1에 evaluate(root의 left)

op2에 evaluate(root의 right)

재귀함수화 한다

연산

5. main