[c++] 트리의 가장 깊은 노드(Deepest Node in a Tree)
이 글에서는 C++를 사용하여 이진 트리(Binary Tree)에서 가장 깊은 노드를 찾는 방법에 대해 설명하겠습니다.
이진 트리(Binary Tree)
이진 트리는 최대 두 개의 자식을 갖는 노드들로 이루어진 트리 구조입니다. 각 노드는 자신의 값과 왼쪽 자식 노드, 오른쪽 자식 노드에 대한 포인터를 가집니다.
구현
이진 트리를 나타내는 C++ 클래스를 다음과 같이 정의할 수 있습니다.
class Node {
public:
int value;
Node* left;
Node* right;
};
가장 깊은 노드 찾기
이진 트리에서 가장 깊은 노드를 찾기 위해서는 깊이 우선 탐색(DFS) 알고리즘이 사용됩니다. 이 알고리즘은 재귀적으로 트리를 탐색하면서 가장 깊은 노드를 찾아냅니다.
다음은 C++에서 깊이 우선 탐색을 사용하여 가장 깊은 노드를 찾는 코드 예시입니다.
Node* deepestNode(Node* root, int depth, int& maxDepth, Node*& result) {
if (root != nullptr) {
depth++;
if (depth > maxDepth) {
maxDepth = depth;
result = root;
}
deepestNode(root->left, depth, maxDepth, result);
deepestNode(root->right, depth, maxDepth, result);
}
return result;
}
Node* findDeepestNode(Node* root) {
int depth = 0;
int maxDepth = -1;
Node* result = nullptr;
return deepestNode(root, depth, maxDepth, result);
}
위 코드에서 findDeepestNode 함수는 주어진 이진 트리에서 가장 깊은 노드를 찾아 반환합니다.
결론
이진 트리에서 가장 깊은 노드를 찾는 것은 깊이 우선 탐색을 사용하여 간단하게 구현할 수 있습니다. 이를 통해 트리의 구조를 탐색하고 원하는 노드를 효율적으로 찾을 수 있습니다.
이상으로 C++에서 이진 트리의 가장 깊은 노드를 찾는 방법에 대해 알아보았습니다.