[자료구조] 트리 기초
글의 ㄹㄴㅇㄹ약 설명 부분.
목차
Tree 트리 구조
본문내용넣기
부분코드
본문내용넣기
부분코드
본문내용넣기
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
using NodeRef = shared_ptr<struct Node>; // 생명주기 관리
struct Node
{
Node() { }
Node(const string& data) : data(data) { }
string data;
vector<NodeRef> children;
};
NodeRef CreateTree()
{
NodeRef root = make_shared<Node>("R1 개발실");
{
NodeRef node = make_shared<Node>("디자인팀");
root->children.push_back(node);
{
NodeRef leaf = make_shared<Node>("전투");
node->children.push_back(leaf);
}
{
NodeRef leaf = make_shared<Node>("경제");
node->children.push_back(leaf);
}
{
NodeRef leaf = make_shared<Node>("스토리");
node->children.push_back(leaf);
}
}
{
NodeRef node = make_shared<Node>("프로그래밍팀");
root->children.push_back(node);
{
NodeRef leaf = make_shared<Node>("서버");
node->children.push_back(leaf);
}
{
NodeRef leaf = make_shared<Node>("클라");
node->children.push_back(leaf);
}
{
NodeRef leaf = make_shared<Node>("엔진");
node->children.push_back(leaf);
}
}
{
NodeRef node = make_shared<Node>("아트팀");
root->children.push_back(node);
{
NodeRef leaf = make_shared<Node>("배경");
node->children.push_back(leaf);
}
{
NodeRef leaf = make_shared<Node>("캐릭터");
node->children.push_back(leaf);
}
}
return root;
}
//void PrintTree(NodeRef root)
//{
// cout << root->data << endl;
//
// for (NodeRef& child : root->children)
// PrintTree(child); // 재귀함수
//}
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) : 루트에서 어떤 노드에 도달하기 위해 거처야 하는 간선의 수 (aka. 몇 층?)
// 높이(height) : 가장 깊숙히 있는 노드의 깊이 (max(depth))
int GetHeight(NodeRef root)
{
int height = 1;
for (NodeRef& child : root->children)
{
height = max(height, GetHeight(child) + 1); // 높이의 max값 호출. 자식들의 각각의 높이가 다를 수도 있다.
}
return height;
}
int main()
{
NodeRef root = CreateTree();
//PrintTree(root);
PrintTree(root, 0);
int height = GetHeight(root);
cout << "Tree Height : " << height << endl;
}
|
cs |
마무리
마무리
'⭐ Programming > 자료구조와 알고리즘' 카테고리의 다른 글
[알고리즘] 우선순위 큐 Priority Queue (0) | 2022.10.31 |
---|---|
[자료구조] 이진 트리, 힙 이론, 힙 트리 (0) | 2022.10.31 |
[자료구조] 다익스트라 알고리즘 (0) | 2022.10.31 |
[자료구조] BFS를 이용한 길찾기 구현 (0) | 2022.10.31 |
[자료구조] BFS (Breadth First Search) 너비 우선 탐색 (0) | 2022.10.28 |
댓글
이 글 공유하기
다른 글
-
[알고리즘] 우선순위 큐 Priority Queue
[알고리즘] 우선순위 큐 Priority Queue
2022.10.31 -
[자료구조] 이진 트리, 힙 이론, 힙 트리
[자료구조] 이진 트리, 힙 이론, 힙 트리
2022.10.31 -
[자료구조] 다익스트라 알고리즘
[자료구조] 다익스트라 알고리즘
2022.10.31 -
[자료구조] BFS를 이용한 길찾기 구현
[자료구조] BFS를 이용한 길찾기 구현
2022.10.31