[Algorith] 이진 트리 (Tree) - 후위 순회 (Post-Oreder Traverse)

Appendix.c

main.c

Appendix.h

/*------------------*/
/* 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;
	NODE *ptrVisited=EndNode, *ptrPushed = EndNode;

	do
	{
		while(ptrNode !=EndNode && ptrNode != ptrVisited) // 이미 방문했거나 엔드노드가 아니라면 스택에 넣는다.
		{
			if(ptrNode != ptrPushed)
			{
				Push(ptrNode);
			}
			if(ptrNode->Right != EndNode)
			{
				Push(ptrNode->Right);
			}
			if(ptrNode->Left != EndNode)
			{
				Push(ptrNode ->Left);
			}
			ptrPushed = ptrNode->Left;
			ptrNode = ptrNode ->Left;


		}

		if(!IsStackEmpty())
		{
			ptrNode = Pop();
			if(ptrNode ->Left != EndNode && ptrNode ->Right == EndNode && ptrNode ->Left != ptrVisited)
			{
				Push(ptrNode);
				ptrNode = ptrNode ->Left;
			}
			if(ptrNode ->Right == EndNode || ptrNode ->Right ==ptrVisited)
			{
				Visit(ptrNode);
				ptrVisited = ptrNode;


			}
		}
		else
		{
			Finish = 1;
		}

	} while(!Finish);
}

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)
	{
		Traverse(ptrNode->Left);
		Traverse(ptrNode->Right);
		Visit(ptrNode);
	}
}