[#4] Left Child Right Sibling Tree

---

Left Child Right Sibling 트리 

트리의 구조

• 트리는 뿌리(Root), 가지(Branch), 잎(Leaf) 세 가지 요소로 이루어져 있다.
• 잎 노드는 끝에 있다는 의미로 단말(Terminal) 노드라고 한다.
• 각 노드는 형제(Sibling), 자식(Children), 부모(Parent)로 구성되어 있다.
• 경로(Path)란 자신을 포함한 해당 노드까지 가는데 거쳐야할 노드들을 말한다.
• 경로는 길이(Length)라는 속성을 가지며, 출발 노드에서 목적지 노드까지 거쳐야하는 노드의 개수를 의미한다.
• 깊이(Depth)는 루트 노드에서 해당 노드까지의 경로의 길이를 뜻한다.
• 레벨(Level)은 깊이가 같은 노드들의 집합을 의미한다.
• 높이(Height)는 가장 깊은 곳에 있는 잎 노드 까지의 길이를 뜻한다.
• 노드의 차수(Degree)는 해당 노드가 가진 자식 노드의 개수를 뜻한다.
• 트리의 차수(Degree)는 트리 내에 있는 노드 가운데 자식 노드가 가장 많은 노드의 차수를 뜻한다. 

 

---

전체 코드

LCRSTree.h

// 2022-07-28 by
// Fubao & Jin
// LeftChild - RightSlibling 표현법
#ifndef __LCRSTREE_H__
#define __LCRSTREE_H__

#include <iostream>
#include <cstdlib>

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      LCRS_PrintNodesAtLevel(LCRSNode* Root, int Level);

#endif

 

LCRSTree.cpp

#include "LCRSTree.h"


LCRSNode* LCRS_CreateNode(ElementType NewData)
{
	LCRSNode* NewNode = new LCRSNode;
	NewNode->LeftChild = nullptr;
	NewNode->RightSibling = nullptr;
	NewNode->Data = NewData;
	return NewNode;
}

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

void LCRS_DestroyTree(LCRSNode* Root)
{
	if (Root->LeftChild != nullptr)
		LCRS_DestroyTree(Root->LeftChild);
	if (Root->RightSibling != nullptr)
		LCRS_DestroyTree(Root->RightSibling);
	Root->LeftChild = nullptr;
	Root->RightSibling = nullptr;
	LCRS_DestroyNode(Root);
}

void LCRS_AddChildNode(LCRSNode* ParentNode, LCRSNode* ChildNode)
{
	if (ParentNode->LeftChild == nullptr)
	{
		ParentNode->LeftChild = ChildNode;
	}
	else
	{
		// 자식 노드가 N > 1일 경우, 형제 노드의 끝으로 이동
		LCRSNode* TempNode = ParentNode->LeftChild;
		while (TempNode->RightSibling != nullptr)
			TempNode = TempNode->RightSibling;
		TempNode->RightSibling = ChildNode;
	}
}

void LCRS_PrintTree(LCRSNode* Node, int Depth)
{
	// 트리를 들여쓰기로 표현
	for (int i = 0; i < Depth; i++)
		std::cout << ' ';
	std::cout << Node->Data << std::endl;

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

void LCRS_PrintNodesAtLevel(LCRSNode* Root, int Level)
{
	if (Root != nullptr)
	{
		if (Level != 0)
		{
			LCRS_PrintNodesAtLevel(Root->LeftChild, Level - 1);
			LCRS_PrintNodesAtLevel(Root->RightSibling, Level);
		}
		else
			LCRS_PrintTree(Root, 0);
	}
}

 

• void LCRS_PrintNodesAtLevel(LCRSNode* Root, int Level)
  트리의 레벨을 입력받고 레벨에 맞는 트리 데이터를 출력해주는 함수이다. 교재의 문제로 출제가 됐었는데 구조가 잘 떠오르지 않아서 1시간 가량 해맸던 것 같다. 처음에는 while문과 if문으로 일정한 레벨만큼 출력해주면 되는 단순한 구조인 줄 알았는데 노드가 서로 형제가 아닐 경우에 동일한 레벨의 다른 노드로 넘어갈 방법이 잘 떠오르지 않았다. 결국 재귀함수로 어찌저찌 맞춰서 구현하니까 잘 작동했다. 하지만 완성을 해도 직관적으로 구조가 다 그려지는게 아니라서 조금 답답한 느낌이 든다. 복습을 계속하면서 익숙해져야겠다.

 

test_LCRSTree.cpp

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

	/* 트리에 노드 추가 */
	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);

	/* 트리 출력 */
	std::cout << "[모든 노드를 출력]" << std::endl;
	LCRS_PrintTree(Root, 0);
	
	/* 특정 레벨의 모든 노드를 출력 */
	std::cout << "[특정 레벨의 모든 노드를 출력]" << std::endl;
	LCRS_PrintNodesAtLevel(Root, 0);

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

	return 0;
}

 

 

---