[c++] 트리의 높이와 깊이(Tree Height and Depth)
트리(Tree)는 데이터 구조 중 하나로 계층적인 관계를 나타내는 데 자주 사용됩니다. 트리의 높이와 깊이는 트리 구조의 중요한 속성 중 하나로, 이 두 가지는 종종 혼동되는 개념입니다.
깊이(Depth)란 무엇인가요?
트리의 깊이는 노드가 루트(Root) 노드에서부터 얼마나 멀리 떨어져 있는지를 나타냅니다. 루트 노드의 깊이는 0입니다. 그리고 그 아래에 있는 자식 노드는 부모 노드의 깊이보다 1 증가된 값을 갖습니다. 이를 통해 각 노드의 깊이를 계산할 수 있습니다.
트리의 각 노드는 부모 노드에서 1 증가된 깊이를 갖습니다. 각 노드의 깊이를 계산하기 위해 재귀적인 알고리즘이 가장 일반적으로 사용됩니다.
int depth(Node* node) {
if (node == nullptr) {
return -1;
}
return 1 + depth(node->parent);
}
높이(Height)란 무엇인가요?
트리의 높이는 트리에 있는 노드 중 가장 깊이에 있는 노드의 깊이를 나타냅니다. 즉, 루트 노드에서 잎(Leaf) 노드까지의 가장 긴 경로의 길이를 의미합니다. 따라서 트리에 아무 노드도 없다면 그 트리의 높이는 -1이 됩니다. 높이를 계산하기 위해 재귀 함수가 주로 사용됩니다.
int height(Node* node) {
if (node == nullptr) {
return -1;
}
return 1 + max(height(node->left), height(node->right));
}
결론
트리의 높이와 깊이는 트리 구조를 분석하고 이해하는 데 도움이 되는 중요한 개념입니다. 적절한 탐색 알고리즘을 사용하여 트리의 높이와 깊이를 계산할 수 있습니다. 이러한 개념을 활용하여 효율적인 트리 구조를 설계하고 분석할 수 있습니다.
이상으로 트리의 높이와 깊이에 대한 간단한 소개를 마치겠습니다. 감사합니다.