<뇌를 자극하는 알고리즘 #4>: 트리(LCRSTree) 퀴즈풀이

Vitamin Quiz

---

 문제) 아래 예제 프로그램에서 특정 레벨의 모든 노드를 출력하는 함수 LCRS_PrintNodesAtLevel(LCRSNode *Root, int Level)를 작성하라. 함수의 원형은 다음과 같다.

void LCRS_PrintNodesAtLevel(LCRSNode *Root, int Level);

풀이 // 이 글은 드래그 및 복붙이 안되므롤 아래 첨부한 파일을 다운받아 보시기 바랍니다. 첫 번째는 교재의 소스코드, 두 번째는 데브맷의 풀이 소스입니다.

---

이 문제의 핵심은 원하는 레벨의 모든 노드를 출력하기 위해서는 부모노드의 정보를 기억할 필요가 있다는 겁니다.

/*************************************************
 ** LCRSTree Vitamin Quiz
*************************************************/

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

typedef char ElementType;

typedef struct tagLCRSNode
{
	struct tagLCRSNode* LeftChild;
	struct tagLCRSNode* RightSibling;

	ElementType Data;
} LCRSNode;


LCRSNode* LCRS_CreateNode(ElementType NewData);
void      LCRS_DestroyNode(LCRSNode* Node);
void      LCRS_DestroyTree(LCRSNode* Root);

void      LCRS_AddChildNode(LCRSNode* ParentNode, LCRSNode *ChildNode);
void      LCRS_PrintTree(LCRSNode* Node, int Depth);

LCRSNode* LCRS_CreateNode(ElementType NewData)
{
	LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
	NewNode->LeftChild = NULL;
	NewNode->RightSibling = NULL;
	NewNode->Data = NewData;

	return NewNode;
}

void LCRS_DestroyNode(LCRSNode* Node)
{
	free(Node);
}

void LCRS_DestroyTree(LCRSNode* Root)
{
	if (Root->RightSibling != NULL)
		LCRS_DestroyTree(Root->RightSibling);

	if (Root->LeftChild != NULL)
		LCRS_DestroyTree(Root->LeftChild);

	Root->LeftChild = NULL;
	Root->RightSibling = NULL;

	LCRS_DestroyNode(Root);
}

void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode *Child)
{
	if (Parent->LeftChild == NULL)
	{
		Parent->LeftChild = Child;
	}
	else
	{
		LCRSNode* TempNode = Parent->LeftChild;
		while (TempNode->RightSibling != NULL)
			TempNode = TempNode->RightSibling;

		TempNode->RightSibling = Child;
	}
}

void LCRS_PrintTree(LCRSNode* Node, int Depth)
{
	int i = 0;
	for (i = 0; iData);

	if (Node->LeftChild != NULL)
		LCRS_PrintTree(Node->LeftChild, Depth + 1);

	if (Node->RightSibling != NULL)
		LCRS_PrintTree(Node->RightSibling, Depth);
}



void LCRS_PrintNodesAtLevel(LCRSNode *Root, int Level)
{
	int i;
	LCRSNode *Parent = NULL;
	Level--;
	while (Level--) // 바로 전 부모까지 이동
	{
		Root = Root->LeftChild;
	}
	Parent = Root; // 바로 전 부모 정보 저장

	for (i = 0; i < Level; i++)
		printf(" ");

	while (Parent) { // 부모 또한 우측으로 계속 이동한다는 게 핵심입니다.
		while (Parent->LeftChild) { // 각 부모별로 왼쪽 자식부터 오른쪽 자식까지 순회합니다.
			printf("%c ", Parent->LeftChild->Data);
			Parent->LeftChild = Parent->LeftChild->RightSibling;
		}
		Parent = Parent->RightSibling; // 부모를 우측으로 이동합니다.
	}
}

int main(void)
{
	/*  노드 생성 */
	LCRSNode* Root = LCRS_CreateNode('A');

	LCRSNode* B = LCRS_CreateNode('B');
	LCRSNode* C = LCRS_CreateNode('C');
	LCRSNode* D = LCRS_CreateNode('D');
	LCRSNode* E = LCRS_CreateNode('E');
	LCRSNode* F = LCRS_CreateNode('F');
	LCRSNode* G = LCRS_CreateNode('G');
	LCRSNode* H = LCRS_CreateNode('H');
	LCRSNode* I = LCRS_CreateNode('I');
	LCRSNode* J = LCRS_CreateNode('J');
	LCRSNode* K = LCRS_CreateNode('K');

	/*  트리에 노드 추가 */
	LCRS_AddChildNode(Root, B);
	LCRS_AddChildNode(B, C);
	LCRS_AddChildNode(B, D);
	LCRS_AddChildNode(D, E);
	LCRS_AddChildNode(D, F);

	LCRS_AddChildNode(Root, G);
	LCRS_AddChildNode(G, H);

	LCRS_AddChildNode(Root, I);
	LCRS_AddChildNode(I, J);
	LCRS_AddChildNode(J, K);

	/*  트리 출력 */
	LCRS_PrintTree(Root, 0);
	LCRS_PrintNodesAtLevel(Root, 2); // 비타민 퀴즈 실험부분

	/*  트리 소멸시키기 */
	LCRS_DestroyTree(Root);

	return 0;
}

/*************************************************
 ** End Line
*************************************************/

데브맷 풀이.c