[자료구조]트리(Tree) 특징 / 운행 3가지 / C++

초안 : 2020년 12월31일

1차수정 : 2023년 4월 10일

 

트리는 이름처럼 나무(tree)와 같은 자료구조이다. 

뿌리를 가지고 뻗어져 나뭇가지에서 잎들이 있는 모습을 거꾸로 뒤집으면 자료구조에서의 트리가 된다.

 

출처 : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

트리 관련 용어

- 노드(Node) : 실제로 저장하는 데이터

- 루트 노드(Root Node) : 최상위에 위치한 데이터

- 리프 노드(Leaf Node) : 마지막에 위치한 데이터들

- 부모-자식 : 연결된 노드들 간의 상대적 관계

- 깊이(Depth) : 노드 -> 루트 경로의 길이

- 높이(Height)  : 노드 -> 리프 경로의 최대 길이

- 하위 트리(Subtree) : 어떤 노드 아래의 모든 것을 포함하는 트리

 

트리의 용도

- 계층적 데이터를 표현한다.

- 검색 트리를 통해 효율적인 알고리즘 구현 가능

- 그 외...

 

 

 

게임에서의 트리

게임 개발을 할때의 트리를 사용한다면 내가 생각 나는건 '디트로이트 비컴 휴먼'이라는 게임에서의 진행도 모습이다.

 

출처 :https://myalrang.tistory.com/134

 

트리를 옆으로 돌려서 보여주고 있고, 플레이어의 선택에 따라 다음 노드가 바뀌며 스토리가 달라지는 게임이다.

 

두번째로는 '슬레이더 스파이어'라는 게임의 맵 선택이지다.

출처 : https://1boon.kakao.com/thisisgame/news001092

이건  기본 트리에서 좀 더 응용한 형태로 뿌리가 여러개로 시작하고 일반 나무와 같이 위로 올라간다.

 

두개의 게임을 보면 트리는 게임에서 직관적으로 맵, 선택지 등에 유저가 직접적인 영향을 받도록 사용 할 수도 있거나 혹은 뒤에서 보이지 않는 부분에서도 사용 될 수 있다.

 

 

 

트리를 간단하게 구현해보자.

 

Node라는 클래스에는 mData int형 데이터와 왼쪽/오른쪽/루트 노드를 가리키는 포인터 변수를 만들어준다.

 

 

루트 Node와 4개의 노드들을 선언해주고  루트에는 0 그 외에는 데이터값을 1~4 넣어준다.

 

root 노드 왼쪽은 노드1, 오른쪽엔 노드2

노드1 왼쪽에는 노드3, 오른쪽에는 노드4를 가리키게 되었다. 그러면 아래와 같이 연결되어진다.

매우 간단하게 연결해주었다.

 

운행방법 3가지

그리고 운행 3가지가 있는데 전위운행/중위운행/후위운행 3가지이다.

운행 함수들 보통 재귀함수로 호출된다고 보면 된다.

 

 

1. 전위 운행(PreOrder)을보면

현재 노드가 NULL이 아니라면 현재 노드의 데이터값을 출력하고 왼쪽 노드로 계속해서 들어간뒤, 

빠져나오며 오른쪽 노드로 들어간다.

출력 결과

그 다음은

2. 중위 운행(InOrder)이다.

 

전위운행과 비슷하지만 순서만 다르다. 현재 노드를 먼저 출력하지 않고, 왼쪽노드로 쭉 들어간다음부터 출력된다.

 

출력결과이다.

 

마지막으로 후위 운행(Post Order)이다.

 

 

이렇게 3가지를 놓고면 사실 다 똑같이 재귀함수로 만들어져 있고, 다음 재귀 함수를 타는 순서상의 미묘한 차이로 운행방법이 전반적으로 달라진다. 여기서 작성한 글은 기초적인 부분이긴하지만, 처음 보게된다면 복잡하게 느껴지기도 한다.

 

 

 

#include<iostream>
#include<algorithm>
using namespace std;


class Node {
public:
	Node()
		: mData(0)
		, mLeft(nullptr)
		, mRight(nullptr)
		, mRoot(nullptr)
	{}

	Node(int data)
		: mData(data)
		, mLeft(nullptr)
		, mRight(nullptr)
		, mRoot(nullptr)
	{}
public:
	int mData;
	Node* mLeft;
	Node* mRight;
	Node* mRoot;
};

void PostOrder(Node* node)
{
	if (node == nullptr)
	{
		return;
	}
	PostOrder(node->mLeft);	
	PostOrder(node->mRight);
	cout << node->mData << endl;
}

//중위 운행
void InOrder(Node* node)
{
	if (node == nullptr)
	{
		return;
	}
	InOrder(node->mLeft);
	cout << node->mData << endl;	
	InOrder(node->mRight);
}

//전위 운행
void PreOrder(Node* node)
{
	if (node == nullptr)
	{
		return;
	}

	cout << node->mData << endl;
	PreOrder(node->mLeft);
	PreOrder(node->mRight);
}


int main()
{
	D();
	Node* root = new Node(0);
	Node* node1 = new Node(1);
	Node* node2 = new Node(2);
	Node* node3 = new Node(3);
	Node* node4 = new Node(4);

	string a = "11aaaaaaaaaaaaaaaaa";

	for (size_t i = 0; i < a.size(); i++)
	{
		cout << i << endl;
	}

	root->mLeft = node1;
	root->mRight = node2;

	node1->mLeft = node3;
	node1->mRight = node4;

	cout << "전위 운행 : " << endl;
	PreOrder(root);
	cout << "------------" << endl;

	cout << "중위 운행 : " << endl;
	InOrder(root);
	cout << "------------" << endl;

	cout << "후위 운행 : " << endl;
	PostOrder(root);
	cout << "------------" << endl;
	return 0;
}

 

 

추가작성

hyo-ue4study.tistory.com/326

[자료구조] 재귀를 이용한 트리운행/스택을 이용한 트리운행