LCRS 트리

1. 트리

트리는 대표적인 비선형구조입니다. 구현했을 때, 가장 적합한 모습이 나무 모양이라서, 이름이 트리입니다. 트리에는 각 노드마다 역할과 이름이 있습니다. 지금부터 간단하게 그 이름만 짚고 넘어가겠습니다.

부모, 자식, 형제노드

부모노드와 자식노드는 서로가 있어야 생기는 관계입니다. 부모노드는 자식노드를 가지고 있는 노드를 자식노드의 부모노드라고 하고, 그 때의 부모노드의 밑에 있는 노드를 자식노드라고 합니다. 그리고 같은 부모노드를 둔 자식노드끼리 형제노드라고 합니다. 위 그림에서 F-B F-G B-A B-D D-C D-E G-I I-H가 부모-자식관계입니다. B-C D-E H-I F-G가 형제노드 관게입니다.

루트, 단말노드

루트노드는 부모노드가 없는 노드를 루트노드라고 하고, 단말노드는 자식노드가 없는 노드를 단말노드라고 합니다. 위 그림에서 루트노드는 F이고, 단말노드는 A C E H입니다.

Path, Length, Depth, Level, Height, Degree

path : 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
length : 출발 노드에서 도착 노드까지 거치는 간선의 개수
depth : 루트 경로의 길이
level : 루트 노드(level=0)부터 노드까지 연결된 간선 수의 합
height : 가장 긴 루트 경로의 길이
degree : 각 노드의 자식의 개수

2. LCRS 트리

LCRS는 Left-Child, Right-Sibling 직역하면, 왼쪽 자식노드 오른쪽 형제노드 입니다. 원래 연결리스트에서 NextNode PrevNode가 노드 마다 있었다면, 여기서는 ChildNode와 SiblingNode가 노드마다 있습니다.

헤더파일

LCRSTree.h

#ifndef LCRS_TREE_H
#define LCRS_TREE_H

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

void LevelPrintTree(LCRSNode* Node, int Level);


#endif

먼저 LCRSNode를 먼저 보면,

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

	ElementType Data;
}LCRSNode;

자식노드와 형제노드의 주소값을 저장할 수 있습니다.

함수들을 살펴보면,

LCRSNode* LCRS_CreateNode(ElementType NewData); -> Node 생성함수
void LCRS_DestroyNode(LCRSNode* Node); -> Node 삭제함수
void LCRS_DestroyTree(LCRSNode* Root); -> Tree 삭제함수

void LCRS_AddChildNode(LCRSNode* ParentNode, LCRSNode* ChildNode); -> Tree에 Node추가하기
void LCRS_PrintTree(LCRSNode* Node, int Depth); -> Tree 출력함수

void LevelPrintTree(LCRSNode* Node, int Level); -> Level에 있는 Node들 출력함수

소스파일

LCRSTree.c

#include "LCRSTree.h"

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; i < Depth - 1; i++) {
		printf(" "); //공백 3칸
	}

	if (Depth > 0) { //자식 노드 여부 표시
		printf("+--");
	}

	//노드 데이터 출력
	printf("%c\n", Node->Data);

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

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

void LevelPrintTree(LCRSNode* Node, int Level) {

	if (Level == 0) {
		printf("%c\n", Node->Data);
	}

	if (Level < 0) {
		return;
	}

	if (Node->LeftChild != NULL) {
		LevelPrintTree(Node->LeftChild, Level - 1);
	}

	if (Node->RightSibling != NULL) {
		LevelPrintTree(Node->RightSibling, Level);
	}
}

함수들을 살펴보겠습니다.

LCRSNode* LCRS_CreateNode(ElementType NewData) {
	LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode)); -> Node 동적할당
	NewNode->LeftChild = NULL; -> 자식노드와 형제노드 주소값 저장공간
	NewNode->RightSibling = NULL; -> 초기화
	NewNode->Data = NewData; -> 데이터 저장

	return NewNode; -> Node반환
}

void LCRS_DestroyNode(LCRSNode* Node) {
	free(Node); -> Node 동적 할당 해제
}

void LCRS_DestroyTree(LCRSNode* Root) {//재귀적으로 Tree를 전체 삭제합니다.
	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; -> 자식노드의 형제노드에 연결
	}
}

이 트리의 단점은 추가하는 방식에서 크게 나타납니다. 트리의 장점은 부모노드에 자식노드가 붙는게 장점입니다. 근데 분포도가 골고루 퍼져있을 때, 장점이 더 좋아집니다. 탐색할 때, 더 짧게 탐색해도 찾을 수 있기 때문입니다. 하지만 LCRS트리는 분포도를 골고루 퍼지게 할 수 없습니다. 한 곳에 뭉쳐버리면 그냥 연결리스트와 다를 바가 없습니다. 따라서 LCRS트리는 트리구조만 이해하는데, 도움이 됐으면 좋겠습니다.

마저 살펴보면,

void LCRS_PrintTree(LCRSNode* Node, int Depth) {
	//들여쓰기
	int i = 0;
	for (i = 0; i < Depth - 1; i++) {
		printf(" "); //공백 3칸
	}

	if (Depth > 0) { //자식 노드 여부 표시
		printf("+--");
	}

	//노드 데이터 출력
	printf("%c\n", Node->Data); -. 데이터 출력

	if (Node->LeftChild != NULL) {
		LCRS_PrintTree(Node->LeftChild, Depth + 1); -> 자식노드로 이동
	}

	if (Node->RightSibling != NULL) {
		LCRS_PrintTree(Node->RightSibling, Depth); -> 형제노드로 이동
	}
}

void LevelPrintTree(LCRSNode* Node, int Level) {

	if (Level == 0) {
		printf("%c\n", Node->Data); -> Level이 0이 됐을 때, 출력합니다.
	}

	if (Level < 0) {
		return; -> Level이 음수는 없기 때문에 함수 종료
	}

	if (Node->LeftChild != NULL) {
		LevelPrintTree(Node->LeftChild, Level - 1); -> 왼쪽 자식노드로 이동(자식노드로 갔기 때문에 Level-1합니다.
	}

	if (Node->RightSibling != NULL) {
		LevelPrintTree(Node->RightSibling, Level); -> 형제노드로 이동
	}
}

트리는 재귀적인 사고가 필요합니다. 그림을 그려가며 이해하면 도움이 많이 됩니다.

실행예시

LCRSTreeMain.c

#include "LCRSTree.h"

int main() {
	//노드 생성
	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);

	LevelPrintTree(Root, 1);


	printf("\n\n\n");
	//트리 출력
	LCRS_PrintTree(Root, 0);

	//트리 소멸
	LCRS_DestroyTree(Root);

	return 0;
}

결과

B
G
I



A
+--B
 +--C
 +--D
  +--E
  +--F
+--G
 +--H
+--I
 +--J
  +--K