[Algorith] 이진 트리 (Tree) - 레벨 순회 (Level-Order Traverse)

Appendix.c

main.c

Appendix.h

A -> B -> C -> D -> E -> F -> G 순서로 나온다.

레벨 순회는 스택보다 큐를 사용하는 것이 바람직 하다.

/*------------------*/
/* main.c */
/*------------------*/

#include "Appendix.h"

/* Definition of External Functions */
extern void InitializeQueue(void);
extern void Put(NODE *);
extern NODE *Get(void);
extern int IsQueueEmpty(void);

/* Definition of Internal Functions */
void InitializeTree(void); // 트리의 기본적인 헤드와 엔드 노드를 만는다.
void MakeTree(void); // 트리의 기본적으로 들어갈 데이터의 값을 만든다.
void Traverse(NODE *); // 데이터의 값을 차례로 꺼낸다.
void Visit(NODE *); // 데이터의 값을 사용자에게 보여준다.

/* Definifion of Global Variables */
NODE *Parent, *LeftChild, *RightChild;
NODE *HeadNode, *EndNode;

void main()
{
	InitializeQueue();
	InitializeTree();
	MakeTree();
	Traverse(HeadNode->Left);
}

/* 트리의 초기화 */
void InitializeTree(void)
{
	HeadNode = (NODE *)malloc(sizeof(NODE));
	EndNode = (NODE * )malloc(sizeof(NODE));

	HeadNode->Left = EndNode;
	HeadNode->Right = EndNode;
	EndNode ->Left = EndNode;
	EndNode ->Right = EndNode;
}

/* 트리의 초기 구성 */
void MakeTree(void)
{
	Parent=(NODE *)malloc(sizeof(NODE));
	Parent->Data='A';
	LeftChild = (NODE *)malloc(sizeof(NODE));
	LeftChild ->Data = 'B';
	RightChild = (NODE *)malloc(sizeof(NODE));
	RightChild->Data ='C';
	Parent->Left=LeftChild;
	Parent->Right=RightChild;
	HeadNode->Left=Parent;
	HeadNode->Right=Parent;

	Parent = Parent->Left;
	LeftChild= (NODE *)malloc(sizeof(NODE));
	LeftChild->Data='D';
	LeftChild->Left=EndNode;
	LeftChild->Right=EndNode;

	RightChild = (NODE *)malloc(sizeof(NODE));
	RightChild -> Data = 'E';
	RightChild->Left=EndNode;
	RightChild->Right=EndNode;
	Parent->Left=LeftChild;
	Parent->Right=RightChild;

	Parent = HeadNode->Right->Right;
	LeftChild=(NODE *)malloc(sizeof(NODE));
	LeftChild->Data='F';
	LeftChild->Left=EndNode;
	LeftChild->Right=EndNode;

	RightChild= (NODE *)malloc(sizeof(NODE));
	RightChild->Data = 'G';
	RightChild ->Left=EndNode;
	RightChild->Right=EndNode;
	Parent->Left=LeftChild;
	Parent->Right=RightChild;
}

void Traverse(NODE *ptrNode)
{
	Put(ptrNode);
	while(!IsQueueEmpty())
	{
		ptrNode = Get();
		Visit(ptrNode);
		if(ptrNode ->Left !=EndNode)
		Put(ptrNode ->Left);
		if(ptrNode ->Right !=EndNode)
		Put(ptrNode ->Right);
	}
}

void Visit(NODE *ptrNode)
{
	printf("%2c -> ", ptrNode ->Data);
}

/*--------------*/
/* Appendix.h */
/*--------------*/

#ifndef _APPENDIX_H
#define _APPENDIX_H

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

typedef struct _NODE
{
	char Data;
	struct _NODE *Left;
	struct _NODE *Right;
} NODE;

NODE *HeadNode, *EndNode;

#endif _APPENDIX_H

/*------------------*/
/* Appendix.c */
/*------------------*/

#include "Appendix.h"

#define MAX 100

NODE *Queue[MAX];
int Front, Rear;

void InitializeQueue(void);
void Put(NODE *);
NODE *Get(void);
int IsQueueEmpty(void);

/* 스택 초기화 함수 */
void InitializeQueue(void)
{
	Front=Rear=0;
}

void Put(NODE *ptrNode)
{
	Queue[Rear]=ptrNode;
	Rear=(Rear++) % MAX;
}

NODE *Get(void)
{
	NODE *ptrNode;

	if(!IsQueueEmpty())
	{
		ptrNode = Queue[Front];
		Front=(Front++) % MAX;
		return ptrNode;
	}
	else
	{
		printf("Queue is Empty\n");
	}
	return NULL; // NULL 값인 0을 준다.
}

int IsQueueEmpty(void)
{
	if(Rear==Front)
	return TRUE;
	else
	return FALSE;
}