트리 기초

📚 트리(Tree)란?

✅ 트리의 특징

• 계층적 구조를 표현하는 데 특화된 자료구조
• 노드(Node)와 간선(Edge)로 구성
• 방향이 있는 그래프(비순환) 형태이며, 하나의 루트(Root) 노드를 가짐

✅ 주요 용어 정리

용어	설명
루트(Root)	최상위 노드, 부모가 없는 유일한 노드
부모(Parent)	자식 노드를 직접 소유한 노드
자식(Child)	어떤 노드의 하위에 있는 노드
형제(Sibling)	같은 부모를 공유하는 노드들
잎(Leaf)	자식이 없는 노드
깊이(Depth)	루트에서 특정 노드까지 도달하는 데 필요한 간선 수
높이(Height)	트리의 최대 깊이
서브트리(Subtree)	트리의 일부분으로, 하나의 노드와 그 하위 노드들

---

🧱 코드

1️⃣ Node 구조체 정의

struct Node
{
	Node() {}
	Node(const string& data) : data(data) {}

	string data; // 노드의 이름 또는 정보
	vector<NodeRef> children; // 자식 노드 리스트
};

• NodeRef는 shared_ptr<Node>의 별칭으로, 메모리 자동 관리
• children은 자식 노드들을 담는 컨테이너로, 다형적인 트리 구성 가능

---

2️⃣ 트리 생성 함수: CreateTree

NodeRef CreateTree()
{
	NodeRef root = make_shared<Node>("R1 개발실");

	// 디자인팀
	NodeRef design = make_shared<Node>("디자인팀");
	design->children.push_back(make_shared<Node>("전투"));
	design->children.push_back(make_shared<Node>("경제"));
	design->children.push_back(make_shared<Node>("스토리"));
	root->children.push_back(design);

	// 프로그래밍팀
	NodeRef dev = make_shared<Node>("프로그래밍팀");
	dev->children.push_back(make_shared<Node>("서버"));
	dev->children.push_back(make_shared<Node>("클라"));
	dev->children.push_back(make_shared<Node>("엔진"));
	root->children.push_back(dev);

	// 아트팀
	NodeRef art = make_shared<Node>("아트팀");
	art->children.push_back(make_shared<Node>("배경"));
	art->children.push_back(make_shared<Node>("캐릭터"));
	root->children.push_back(art);

	return root;
}

• 트리의 루트 노드는 "R1 개발실"
• 팀 단위로 자식 노드가 연결되며, 팀마다 세부 분야가 다시 연결되는 3단계 계층 구조

---

3️⃣ 트리 출력 함수: PrintTree

void PrintTree(NodeRef root, int depth)
{
	for (int i = 0; i < depth; i++)
		cout << "-";
	cout << root->data << endl;

	for (NodeRef& child : root->children)
		PrintTree(child, depth + 1);
}

• depth 만큼 -를 출력해 트리의 계층 구조 시각화
• 자식 노드들을 재귀 호출로 깊이 우선 탐색(DFS) 형태로 출력

---

4️⃣ 트리의 높이 구하기: GetHeight

int GetHeight(NodeRef root)
{
	int height = 1;

	for (NodeRef& child : root->children)
	{
		height = max(height, GetHeight(child) + 1);
	}

	return height;
}

• 각 자식의 높이를 재귀적으로 호출하며 가장 깊은 노드의 높이 반환
• 트리의 재귀적 구조를 완벽하게 활용한 예제

---

5️⃣ 메인 함수: 전체 실행 흐름

int main()
{
	NodeRef root = CreateTree();

	PrintTree(root, 0);

	int height = GetHeight(root);
	cout << "Tree Height : " << height << endl;
}

• 트리 생성 → 출력 → 높이 계산까지 한 번에 확인 가능

---

📌 실행 결과

R1 개발실
-디자인팀
--전투
--경제
--스토리
-프로그래밍팀
--서버
--클라
--엔진
-아트팀
--배경
--캐릭터
Tree Height : 3

• Tree Height : 3은 루트부터 가장 깊은 노드(예: 전투, 서버, 배경 등)까지의 깊이가 3이라는 의미입니다.

---

🧠 트리 구조의 응용

트리는 다음과 같은 다양한 분야에서 활용됩니다:

• 파일 시스템 구조
• 게임 오브젝트 계층
• UI 컴포넌트 트리
• 씬 그래프
• AI 트리 (FSM, BT)
• 계층적 애니메이션 구조

트리를 깊이 있게 이해하고 직접 구현해보는 과정은 자료구조 마스터의 필수 코스입니다!

---