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

main.c

Appendix.h

Appendix.c

{

D -> B -> E -> A -> F -> C -> G 순서로 이동한다.

전위 순회의 코드를 이용하여 Traverse() 함수만 바꿔주면 된다.

/*------------------*/
/* 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)
{
	int Finish = 0;

	do // 일단 한번 실행한다.
	{
		while(ptrNode != EndNode) // ptrNode가 EndNode이라면 while문을 패스한다.
		{
			Push(ptrNode);
			ptrNode = ptrNode ->Left; // EndNode가 나올때 까지 오른쪽으로 향하면서 스택에 넣는다.
		}

		if(!IsStackEmpty()) // 스택이 비지 않았다면 스택에서 꺼내고 오른쪽을 가리킨다. (스택에 넣는게 아니다)
		{
			ptrNode = Pop();
			Visit(ptrNode);
			ptrNode = ptrNode ->Right;
		}
		else
		{
			Finish = 1;
		}
	} while(!Finish); // Fisish가 1이 될때까지 반복한다.
}


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

/*------------------*/
/* 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;
}

/*--------------*/
/* 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

스택을 이용한 중위 순회 알고리즘 -> 재귀적 호출을 이용한 알고리즘

Traverse() 함수를 아래와 같이 바꿔주면 된다
/*---------------------------------------*/
void Traverse(NODE *ptrNode)
{
if(ptrNode != EndNode)
{
Traverse(ptrNode ->Left);
Visit(ptrNode);
Traverse(ptrNode->Right);
}
}