[Algorith] 이진 트리 (Tree) - 전위 순회 (Pre-Order Traverse)

Appendix.c

main.c

Appendix.h

나오는 순서는 위 그림과 같이 A -> B -> D -> E -> C -> F -> G 순서이다.

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

#include "Appendix.h"

/* Definition of External Functions */
extern void InitializeStack(void);
extern void Push(NODE *);
extern NODE *Pop(void);
extern int IsStackEmpty(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()
{
	InitializeStack();
	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)
{
	Push(ptrNode);
	while(!IsStackEmpty())
	{
		ptrNode=Pop();
		Visit(ptrNode);
		if(ptrNode->Right != EndNode) // 오른쪽의 값을 먼저 넣어 나중에 나오게 한다. (FILO 형식인 스택)
		Push(ptrNode->Right);
		if(ptrNode->Left != EndNode) // 왼쪽의 값을 나중에 넣어 먼저 나오게 한다.
		Push(ptrNode->Left); // 따라서 스택을 이용하여 전위 순회가 가능하게 한다.
	}
}

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 *Stack[MAX];
int Top;

void InitializeStack(void);
void Push(NODE *);
NODE *Pop(void);
int IsStackEmpty(void);

/* 스택 초기화 함수 */
void InitializeStack(void)
{
	Top=0;
}

void Push(NODE *ptrNode)
{
	Stack[Top]=ptrNode;
	Top=(Top++) % MAX;
}

NODE *Pop(void)
{
	NODE *ptrNode;
	if(!IsStackEmpty())
	{
		ptrNode = Stack[--Top];
		return ptrNode;
	}
	else
	{
		printf("Stack is Empty\n");
	}
	return NULL; // NULL 값인 0을 준다.
}

int IsStackEmpty(void)
{
	if(Top==0)
	return TRUE;
	else
	return FALSE;
}

스택을 이용한 전위 순회 알고리즘 -> 재귀적 호출 알고리즘  (재귀적 호출은 함수를 다중으로 사용하기 때문에 시스템에 과부하를 준다.)

기존의 Traverse() 함수를 아래와 같이 바꾼다.

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