Tree?
계층적 구조를 갖는 데이터를 표현하기 위한 자료구조
- 노드 : 데이터 표현
- 간선 : 노드의 계층 구조를 표현하기 위해 사용
용어
깊이는 Root Node가 0이다.
높이는 3이다.
구현
양파를 까면 양파가 나오듯이 트리도 분리를 하면 트리라서
재귀함수와 잘 맞다.
기본셋팅은 이렇게 해주도록 하자.
using NodeRef using 키워드 잊어 먹으면 안된다.
NodeRef CreateTree()
{
NodeRef root = std::make_shared<Node>("R1 개발실");
{
NodeRef node = std::make_shared<Node>("디자인팀");
root->_children.emplace_back(node);
{
NodeRef leaf = std::make_shared<Node>("전투");
node->_children.emplace_back(leaf);
}
{
NodeRef leaf = std::make_shared<Node>("경제");
node->_children.emplace_back(leaf);
}
{
NodeRef leaf = std::make_shared<Node>("스토리");
node->_children.emplace_back(leaf);
}
}
{
NodeRef node = std::make_shared<Node>("프로그래밍팀");
root->_children.emplace_back(node);
{
NodeRef leaf = std::make_shared<Node>("서버");
node->_children.emplace_back(leaf);
}
{
NodeRef leaf = std::make_shared<Node>("클라");
node->_children.emplace_back(leaf);
}
{
NodeRef leaf = std::make_shared<Node>("엔진");
node->_children.emplace_back(leaf);
}
}
{
NodeRef node = std::make_shared<Node>("아트팀");
root->_children.emplace_back(node);
{
NodeRef leaf = std::make_shared<Node>("배경");
node->_children.emplace_back(leaf);
}
{
NodeRef leaf = std::make_shared<Node>("캐릭터");
node->_children.emplace_back(leaf);
}
}
return root;
}Tree만드는 함수인데 길기만 하고 별거 없다.
그리고 Tree원소들 출력하는 함수이다.
이후 실행을 하면은
재귀적으로 잘나온다.
문제점 ❗
계층 구조가 뚜렷하게 출력이 되지 않는데,
이렇게만 조금 변경해주어도 계층구조가 표현이 된다. ㅎ
Root의 깊이, 높이 구하기 ❗❗
-
깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야하는 간선의 수 (aka. 몇층?)
-
높이(Height) : 가장 깊숙히 있는 노드의 깊이(max depth)
본인이 구현한 Height ❗❗❗
엄청 쓰레기에 똥같은 코드이다.
이딴식으로 짜면 알아보기도 힘들고 높이를 제대로 구할 수도 없다.
그냥 재귀함수가 뭔지 모르는 뇌임.
int GetHeight(NodeRef root)
{
int height = 1;
for (NodeRef& child : root->_children)
{
height = std::max(height, GetHeight(child) + 1);
}
return height;
}이코드를 보고 분석을 완벽하게 하기 바란다.
재귀함수와 트리의 가장 기본기라 정확하게 알아야함.
분석 ❗
첫번째 호출과정
트리가 이런 구조라고 가정을 하고 GetHeight(root)를 호출 한다면은
처음에 height = 1인 상태로 시작을 한다.
그리고 for (NodeRef& child : root->_children) 을 도는데
1번 부터 들어간다.
child는 1번이고
height = std::max(height, GetHeight(childe) + 1);로 인해서
이부분이
height = std::max(1, GetHeight("1번") + 1);
이렇게 된 셈이다.
그러면 root는 1번으로 바뀌고 다시 113줄의 for문을 시작을 하는데 child는 1번의 자식들을 돌게된다.
그리고 첫번째 호출 과정을 반복한다.
그러면 root는 1번 노드의 첫번째 자식이 되고
자식이 없으므로 바로 118번째 줄로 내려와 1을 return을 함.
그리고 root가 1번일 때의
height = std::max(height, "GetHeight(child)" + 1);
부분에서 "GetHeight(child)" => 1이기 때문에
height = std::max(height, 1 + 1);
구해주게 되면은 height = 2;가 된다.
지금까지 1번 노드의 첫번째 leaf node 계산이였고
1번 노드의 두번째 leaf node도 위와같은 방법으로 똑같이 계산을 해준다.
계산이 다 끝나면은 root가 r노드일경우로 돌아와
height = 3;으로 변경되고
그다음 r노드의 자식인 2번 노드를 1번 노드를 계산했을 때와 똑같이 계산을 해준다.
그리고 2번 노드에서 나온 최종 height값과
1번 노드에서 나오느 최종 height값과
std::max를 통해서 max값을 찾는 것이다.
(3번 노드도 똑같음)
결론
재귀함수 어떻게 동작을 하는지 잘 파악을 하고 있어야한다.
