뇌를 자극하는 알고리즘 - 4. 트리 : Left Child Right Sibling

구현 소스

LCRSTree.h

#ifndef LCRSTREE_H
#define LCRSTREE_H

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

typedef char Element;

// Left child Right Sibling Tree Struct 선언

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

	Element Data;

} LCRSNode;

LCRSNode* LCRS_CreateNode(Element NewData);

void LCRS_DestroyNode(LCRSNode* Node);
void LCRS_DestroyTree(LCRSNode* Root);
// DestroyTree 함수는 트리의 오른쪽 하위 Node부터 차례대로 메모리 해제를 하는 재귀구조의 함수

void LCRS_AddCildNode(LCRSNode* ParentNode, LCRSNode* ChildNode);
// ParentNode의 차일드를 추가하는 함수 
// - ParentNode의 차일드가 없을시 : ParentNode->LeftChild ChildNode
// - ParentNode의 차일드가 존재시 : ParentNode->LeftChild->RightSibling == NULL 인 Node에 ChildNode 연결

void LCRS_PrintTree(LCRSNode* Node, int Depth);
// Node와 이 Node에 해당하는 Depth를 인자로 넘기면 Node부터 차례대로 Tree의 최대 Height까지 모든 노드의 Data를 출력함.
// p.144쪽 Tree 그림을 참고하여 Node오 Depth인자에 따른 출력되는 Node의 Data들을 살펴보자면

// 1. Root Node인 A와 Depth 에 아무값이나(왠만하면 해당되는 Depth를 주는게 보기 좋음) 줄 시 - 모든 Node의 데이터 출력

// 2. A의 첫번째 Child Node인 B와 Depth로 아무값이나 주면 
// - B의 모든 Child Node와 B의 Sibling Node인 G,I 및 G,I의 차일드까지 모두 출력

// 3. B의 Sibling Node G를 전달시
// - G의 모든 Child와 Silbing인 I와 I의 모든 차일드까지 출력....


/////////////////////////////////////////////////////////
// Vitamin Quiz : 특정 레벨의 모든 노드를 출력하는 함수 작성
// 책에는 함수원형 매개변수에 Level만 나와있던데 뭐지 ㅡㅡ? Root 없이 어케 Level로만 구하라는겨
void LCRS_PrintNodesAtLevel(LCRSNode* Root, int Level);

#endif
-----------------------------------------------------------------------------------------
LCRSTree.cpp

#include "LCRSTree.h"


// 새로운 노드를 생성하는 함수
LCRSNode* LCRS_CreateNode(Element 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);
}

// DestroyTree 함수는 트리의 오른쪽 하위 Node부터 차례대로 메모리 해제를 하는 재귀구조의 함수
void LCRS_DestroyTree(LCRSNode* Root){

	if(Root->RightSibling != NULL) // RightSibling이 존재시
		LCRS_DestroyTree(Root->RightSibling); // RightSibling이 가리키는 노드를 매개변수로 하여 재귀호출

	if(Root->LeftChild != NULL) // LeftChild 존재시
		LCRS_DestroyTree(Root->LeftChild); // LeftChild가 가리키는 노드를 매개변수로 하여 재귀호출

	// 호출 종료시 링크 해제 및 메모리 해제
	Root->LeftChild = NULL;
	Root->RightSibling = NULL;
	
	printf("...Deleted Data : '%c' Node\n", Root->Data); 

	LCRS_DestroyNode(Root); 
}

// ParentNode의 차일드를 추가하는 함수 
// - ParentNode의 차일드가 없을시 : ParentNode->LeftChild ChildNode
// - ParentNode의 차일드가 존재시 : ParentNode->LeftChild->RightSibling == NULL 인 Node에 ChildNode 연결
void LCRS_AddCildNode(LCRSNode* ParentNode, LCRSNode* ChildNode){
	if(ParentNode->LeftChild == NULL)
	{
		ParentNode->LeftChild = ChildNode;
	}
	else
	{
		LCRSNode* TempNode = ParentNode->LeftChild;
		while( TempNode->RightSibling != NULL)
			TempNode = TempNode->RightSibling;

		TempNode->RightSibling = ChildNode;
	}


}

// Node와 이 Node에 해당하는 Depth를 인자로 넘기면 Node부터 차례대로 Tree의 최대 Height까지 모든 노드의 Data를 출력함.
void LCRS_PrintTree(LCRSNode* Node, int Depth){
	int i=0;

	// 들여쓰기로 트리의 Depth 표현
	for(i=0;i<Depth;i++)
		printf("ㅡ");

	printf("%c\n",Node->Data);
	
	if(Node->LeftChild != NULL) // 차일드 존재시
		LCRS_PrintTree(Node->LeftChild , Depth+1); // 재귀 호출 - Node의 Child의 깊이는 Node의 Depth에 +1 한 값과 같음
	if(Node->RightSibling != NULL) // 형제 존재시
		LCRS_PrintTree(Node->RightSibling , Depth); // 재귀 호출 - 형제 노드의 깊이는 모두 같음(같은 레벨의 노드)
}


// Vitamin Quiz : 특정 레벨의 모든 노드를 출력하는 함수 작성
// - 뭔가 이리저리 만지다 보니 만들어져버렸는데 recursive로...
//   이걸 iterative로 바꾸고 싶은데 좀 복잡하네..
void LCRS_PrintNodesAtLevel(LCRSNode* Root, int Level){		
	
	if( (Root->LeftChild != NULL) && (Level>=0) )
		LCRS_PrintNodesAtLevel(Root->LeftChild, Level-1);
	if( (Root->RightSibling != NULL) && (Level>=0) )
		LCRS_PrintNodesAtLevel(Root->RightSibling, Level);	
	if(Level == 0)
	{
		printf("%c\n", Root->Data);
		return ;
	}		
	
}
-----------------------------------------------------------------------------------------

main.cpp

#include "LCRSTree.h"

int main(){
	// p.144쪽의 트리 구조 형성

	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');

	// Root Node의 Child Node - B,G,F
	LCRS_AddCildNode(Root,B);
	LCRS_AddCildNode(Root,G);
	LCRS_AddCildNode(Root,I);
	// B Node의 Child - C,D
	LCRS_AddCildNode(B,C);
	LCRS_AddCildNode(B,D);
	// D Node의 Child - E,F
	LCRS_AddCildNode(D,E);
	LCRS_AddCildNode(D,F);
	
	// G Node의 Child - H
	LCRS_AddCildNode(G,H);

	// I Node의 Child - J
	LCRS_AddCildNode(I,J);
	// J Node의 Child - K
	LCRS_AddCildNode(J,K);

	// 1번의 경우
	// 1. Root Node인 A와 Depth 에 아무값이나(왠만하면 해당되는 Depth를 주는게 보기 좋음) 줄 시
	//  - 모든 Node의 데이터 출력
	printf("*** Tree *** \n");
	LCRS_PrintTree(Root,0);
	printf("************ \n");
	
	// 2번의 경우
	// 2. A의 첫번째 Child Node인 B와 Depth로 아무값이나 주면 
	// - B의 모든 Child Node와 B의 Sibling Node인 G,I 및 G,I의 차일드까지 모두 출력
	printf("*** Tree *** \n");
	LCRS_PrintTree(B,1);
	printf("************ \n");

	// 3. B의 Sibling Node G를 전달시
    // - G의 모든 Child와 Silbing인 I와 I의 모든 차일드까지 출력....
	printf("*** Tree *** \n");
	LCRS_PrintTree(G,1);
	printf("************ \n");

	printf("= Level 1 =\n");
	LCRS_PrintNodesAtLevel(Root,1);
	printf("= Level 2 =\n");
	LCRS_PrintNodesAtLevel(Root,2);
	printf("= Level 3 =\n");
	LCRS_PrintNodesAtLevel(Root,3);
	
	LCRS_DestroyTree(Root);

	return 0;
}
-------------------------------------------------------------------------------------------

실행결과