트리에 대해(C언어)

1. 트리 개념과 용어

1-1. 트리 개념

트리는 우리가 알고 있는 Tree, 즉 나무를 의미한다. 나무처럼 생긴 자료구조라서 트리라고 불린다.

우리 생활 속 나무

여기서 나무는 잎, 가지, 뿌리를 갖는다. 이 3가지를 트리라는 자료구조에서 주된 개념으로 사용하게 된다. 그런데 우린 이 나무를 거꾸로 뒤집어 사용할 것이다. 하지만 뿌리에서 잎으로 뻗어나가는 구조는 변함이 없다.

1-2. 트리 용어

트리 구조

트리는 앞서 얘기한 잎, 가지, 뿌리 세 가지 요소로 구성 되어 있다.

 

노드(Node): 뿌리, 가지, 잎 모두 노드라는 요소로 구성

잎(Leaf): 가지 끝에 달린 노드 단말 노드라고도 부름

가지(Branch):뿌리와 잎 사이에 존재하는 모든 노드

뿌리(Root): 최상단에 존재하는 노드

 

트리의 우측 가지와 잎들의 관계를 보면 부모(Parent), 자식(Children), 형제(Sibling)가 적혀 있는 것을 볼 수 있다. 이도 역시 트리에서 자주 사용하는 용어로 현재 노드의 상단을 부모 노드, 현재 노드는 그 자식이 되고, 같은 부모에서 뻗은 다른 노드는 형제 노드가 된다.

 

경로와 깊이

한 노드에서 다른 노드로 가는 길을 경로(Path)라고 한다. 중간에 거치는 노드의 수를 길이(Length)라고 한다. 마지막으로 깊이(Depth)는 뿌리에서 내가 가리키는 노드까지 경로의 길이를 뜻한다. 여기서 노드를 잇는 선은 간선(Edge)이다.

깊이 시각화

이 밖에도 비슷하게 사용되는 용어로 레벨(Level)과 높이(Height)가 있다. 레벨은 같은 깊이에 있는 노드들의 집합! 이고, 높이는 잎은 0부터 시작하고, 이 후 노드의 높이는 자식 중 높이가 가장 큰 높이에 +1을 한 값이다. 트리의 높이는 Root의 높이이다. 차수(Degree)는 자식의 개수로 보통 "트리의 차수"는 자식이 가장 많은 노드의 차수를 나타낸다.

1-3. 트리의 사용처

• 운영체제의 파일 시스템 구조
• HTML, XML문서를 다룰 때 사용하는 DOM(트리 구조)
• 트리 기반 검색 엔진 또는 데이터베이스 구현

2. 트리 구현

"왼쪽 자식-오른쪽 형제(Left Child-Right Sibling)" 표현법으로 구현할 것이다.

상상도

구조체에 데이터를 담는 변수 하나, 왼쪽에는 자식을 카리키는 포인터, 오른쪽엔 형제를 가리키는 포인터를 선언한다. 부모와 연결 된 한 자식이 다른 형제들을 연결하는 구조이다. 이렇게 되면 한 노드의 다량의 자식과 형제가 표현 가능하다.

 

2-1. 트리 ADT

• 생성과 소멸
• 자식 노드 연결

2-2. 트리 코드

1. 노드 정의

typedef char ElementType;

typedef struct tagLCRSNode
{
	struct tagLCRSNode* LeftChild;
	struct tagLCRSNode* RightSibling;
	ElementType Data;
}LCRSNode;

• 자식 노드 포인터
• 형제 포인터
• 데이터 변수

2. 트리 생성 소멸

LCRSNode* LCRS_CreateNode(ElementType NewData)
{
	LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
	NewNode->LeftChild = NULL;
	NewNode->RightSibling = NULL;// 안전하게 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);
	}

	LCRS_DestroyNode(Root);
}

• 노드는 단순하게 free
• Tree는 연결 되어 있는 노드들이 많기에 재귀함수로 노드들을 모두 제거

3. 새로운 노드 연결과 전체 트리 출력

자식을 연결하는 두 가지 경우

자식 연결 연산의 경우 그림으로 이해하면 훨씬 편하다.

첫째, 연결하고자 하는 노드의 자식이 없는 경우 새 노드는 자식이 된다.

둘째, 연결하고자 하는 노드의 자식이 존재하면 형제 노드에 연결되고, 형제가 존재한다면 형제 노드들의 끝에 연결한다.

void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode* Child)// 자식 연결 로직
{
	if (Parent->LeftChild == NULL)// 자식이 없다면 자식으로 연결
	{
		Parent->LeftChild = Child;
	}

	else// 자식이 있다면 형제들 중 하나로 연결
	{
		LCRSNode* Cur = Parent->LeftChild;

		while (Cur->RightSibling != NULL)
			Cur = Cur->RightSibling;

		Cur->RightSibling = Child;
	}
}
// Root부터 모든 노드를 출력 Root -> 자식 -> 형제 순
void LCRS_PrintTree(LCRSNode* Node, int Depth)
{
	//들여쓰기
	for (int 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);
}

 

4. 특정 레벨에 있는 노드들 출력

// 특정 레벨에 있는 노드를 출력.
void LCRS_PrintNodeAtLevel(LCRSNode* Node, int Level)
{
	if (Node == NULL)
		return;

	if (Level == 0)// 0을 기준으로 도달 여부 확인
	{
		printf("%c ", Node->Data);
	}

	else if (Level > 0)// 아직 층이 낮기에 다음 레벨로 이동
	{
		LCRS_PrintNodeAtLevel(Node->LeftChild, Level - 1);
	}
	// 맞는 층이라면 출력을 위해 아니라면 형제의 자식을 찾기 위해 호출
	LCRS_PrintNodeAtLevel(Node->RightSibling, Level);
}

재귀를 할수록 Level변수의 값이 변하여 ADT와는 맞지 않다고 생각된다(한칸만 내려가도 사용자가 원하는 레벨이 무엇인지 알 수 없기 때문). 그러나 재귀로 구현하였기에 이렇게 작성하였다. 반복문으로 변질된 ADT를 방지하고, 스택 오버 플로우도 미연에 방지할 수 있을 것 같다.

5. main에서 출력

#include "LCRSTree.h"

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');
	LCRSNode* L = LCRS_CreateNode('L');
	LCRSNode* M = LCRS_CreateNode('M');

	// 트리에 노드 추가 (자식 관계를 나타내기 위해 코드 들여쓰기)
	LCRS_AddChildNode(Root, B);
		LCRS_AddChildNode(B, C);
			LCRS_AddChildNode(C, D);
			LCRS_AddChildNode(C, E);
		LCRS_AddChildNode(B, F);
			LCRS_AddChildNode(F, G);
			LCRS_AddChildNode(F, H);

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

	LCRS_AddChildNode(Root, K);
		LCRS_AddChildNode(K, L);
			LCRS_AddChildNode(L, M);

	// 트리 출력
	LCRS_PrintTree(Root, 0);

	LCRS_PrintNodeAtLevel(Root, 2);

	// 트리 소멸
	LCRS_DestroyTree(Root);
}

 

전체 트리 출력

전체 트리 출력 결과이다. 테스트함수에서 연결한 바와 같이 트리의 구조가 잘 연결되어 있다.

레벨 출력

특정 레벨의 트리도 잘 출력된다. 이렇게 알파벳으로 트리의 구조를 파악할 수 있었다. 더 자세한 내용은 "이것이 자료구조+알고리즘이다"에서 확인할 수 있다. 해당 책에서 많이 참고하여 작성하게 되었다.

책 구매 링크

참고자료

https://yoongrammer.tistory.com/68