[자료구조] - LCRS_TREE 구현 (C++)

1. 개요

 

 이번 자료구조는 TREE의 종류 중 하나인 LCRS_TREE이다. LCRS는 Left Child Right Sibling의 약자로 왼쪽 포인터는 자식을, 오른쪽 포인터는 형제를 가리키는 TREE이다. 학교에서는 이 LCRS트리를 배운적은 없다. 일반적인 트리에 대한 개념을 배우고 이진 트리(이진 탐색 트리)와 수식트리를 배웠다. 따라서 LCRS트리는 스스로 모든 메소드를 구현해야 했는데 오히려 배운점이 더 많았다. 다음은 LCRS트리의 이론이다.

 

2. 이론

 

 LCRS트리는 앞에서 설명했듯이 왼쪽은 자식을 오른쪽은 형제를 가리키는 트리이다. 즉 data를 기리키는 필드 하나와 왼쪽, 오른쪽 포인터의 역할을 기리키는 포인터 두개로 구성되어있다. 다음은 LCRS트리이다.

---

LCRS 트리

---

 내가 배운 책에서는 LCRS트리가 C로 구현되어있지만, C++도 공부하고 확실하게 개념을 이해하기 위해 스스로 C++로 구현하였다. 객체지향적인 코딩을 바라며 코딩했지만 결과는 잘 모르겠다... 다음은 메소드와 소스 코드이다.

 

3. 소스코드

 

 다른 자료구조는 기능을 먼저 설명하였지만, LCRS트리(아마 앞으로 포스팅 되는 모든 자료구조들도)는 기능과 소스코드를 동시에 설명할 것이다. 다음은 노드로 사용할 구조체이다.

 

- Node 구조체

 

typedef struct Node {
	struct Node* lChild;
	struct Node* rSibling;
	char data;
} Node, *NodePtr;

 

 앞서 설명했듯이 Node는 data를 저장할 공간과, 왼쪽 오른쪽을 가리키는 포인터 두개의 필드로 구현하였다.

 

- 노드 추가

 

 노드를 추가하는 방법은 간단하다. A라는 노드의 자식으로 노드를 추가한다고 생각해보자, 가장 먼저 확인할 것은 이 노드에 자식의 존재 유무이다. 만약 존재하지 않는다면, A의 left포인터에 그대로 추가하면 되고, 만약 자식이 존재한다면 그 자식의 형제들 중 right포인터가 nullptr인 노드를 찾으면 된다. 즉, 형제의 끝을 찾으면 되는데 이는 while문으로 간단하게 해결할 수 있다. 다음은 소스 코드이다.

 

void LCRS_TREE::addChild(NodePtr pNode, char data) {
	
	NodePtr nData = getNode(data);
	
	if (pNode->lChild) {

		NodePtr buff = pNode->lChild;

		while (buff->rSibling)
			buff = buff->rSibling;

		buff->rSibling = nData;
	}
	else {
		depth++;
		pNode->lChild = nData;
	}
}

 

- 트리 출력

 

 트리를 출력하는 방법은 책에 있는 방법을 사용하였다. 노드의 깊이마다 공백을 출력하여 자식들이 한칸 뒤에 출력되게 하는 방법인데, 전위 순회를 통해 구현할 수 있다. 다음은 트리를 출력하는 메소드이다.

 

void LCRS_TREE::printTree(NodePtr pNode, int tmpDepth) {

	for (int i = 0; i < tmpDepth; i++)
		printf(" ");
	printf("%c\n", pNode->data);

	if (pNode->lChild)
		printTree(pNode->lChild, tmpDepth + 1);
	if (pNode->rSibling)
		printTree(pNode->rSibling, tmpDepth);
}

 

- 노드 탐색

 

 노드 탐색은 노드 추가 메소드를 위해 구현하였다. 책에는 없는 기능이지만, 전위 순회를 이용하면 구현할 수 있다고 생각하였다. 처음은 return문과 재귀함수를 사용해 구현하려 했으나 정말 많은 오류를 범했다. 따라서 result라는 변수를 매게변수로 넘겨주어 이 변수에 탐색하고 싶은 노드의 주소를 저장하는 방법으로 구현하였다. 다음은 소스코드이다.

 

void LCRS_TREE::findNode(NodePtr pNode,NodePtr &result, char data) {

	if (pNode->data == data) 
		result = pNode;
	
	if (pNode->lChild || pNode->rSibling) {
		if (pNode->lChild) 
			findNode(pNode->lChild, result, data);

		if (pNode->rSibling) 
			findNode(pNode->rSibling, result, data);
	}
}

 

- 전체코드

 

 위의 메소드 말고도 노드를 생성하고, root를 반환하는 등 부가적인 메소드가 존재하기에 전체 코드를 올린다.

 

- LCRS_TREE.h

 

#pragma once
#include <cstdio>

typedef struct Node {
	struct Node* lChild;
	struct Node* rSibling;
	char data;
} Node, *NodePtr;

class LCRS_TREE
{
private:
	NodePtr root;
	int depth;
public:
	LCRS_TREE();
	~LCRS_TREE();
	void addChild(NodePtr pNode, char data);
	NodePtr getNode(char data);
	NodePtr getRoot() { return root; }
	void findNode(NodePtr pNode, NodePtr &result, char data);
	void setRoot(char data);
	void printTree(NodePtr pNode, int tmpDepth);
};

 

- LCRS-TREE.cpp

 

#include "LCRS_TREE.h"



LCRS_TREE::LCRS_TREE()
{
	root = nullptr;
	depth = 0;
}


LCRS_TREE::~LCRS_TREE()
{
}

NodePtr LCRS_TREE::getNode(char data) {
	NodePtr nNode	= new Node;
	nNode->data		= data;
	nNode->lChild	= nullptr;
	nNode->rSibling = nullptr;

	return nNode;
}

void LCRS_TREE::addChild(NodePtr pNode, char data) {
	
	NodePtr nData = getNode(data);
	
	if (pNode->lChild) {

		NodePtr buff = pNode->lChild;

		while (buff->rSibling)
			buff = buff->rSibling;

		buff->rSibling = nData;
	}
	else {
		depth++;
		pNode->lChild = nData;
	}
}

void LCRS_TREE::findNode(NodePtr pNode,NodePtr &result, char data) {

	if (pNode->data == data) 
		result = pNode;
	
	if (pNode->lChild || pNode->rSibling) {
		if (pNode->lChild) 
			findNode(pNode->lChild, result, data);

		if (pNode->rSibling) 
			findNode(pNode->rSibling, result, data);
	}
}

void LCRS_TREE::setRoot(char data) {
	
	root = getNode(data);
}

void LCRS_TREE::printTree(NodePtr pNode, int tmpDepth) {

	for (int i = 0; i < tmpDepth; i++)
		printf(" ");
	printf("%c\n", pNode->data);

	if (pNode->lChild)
		printTree(pNode->lChild, tmpDepth + 1);
	if (pNode->rSibling)
		printTree(pNode->rSibling, tmpDepth);
}

 

3. 실행결과

 

 다음은 main함수의 소스코드와 그에 해당하는 실행결과이다.

 

- main.cpp

 

#include "LCRS_TREE.h"

int main(void) {
	LCRS_TREE tree;
	tree.setRoot('A');
	tree.addChild(tree.getRoot(), 'B');
	tree.addChild(tree.getRoot(), 'C');
	tree.addChild(tree.getRoot(), 'D');
	
	NodePtr buff = nullptr;

	tree.findNode(tree.getRoot(), buff, 'C');
	tree.addChild(buff, 'E');

	tree.findNode(tree.getRoot(), buff, 'E');
	tree.addChild(buff, 'F');

	tree.findNode(tree.getRoot(), buff, 'B');
	tree.addChild(buff, 'G');

	tree.printTree(tree.getRoot(),0);

	return 0;
}

 

- 실행결과

---

실행결과

---