Colin's Blog
[c++] 부분 트리 확인(Subtree Check)

이번에는 부분 트리 확인(Subtree Check) 알고리즘에 대해 알아보겠습니다. 부분 트리 확인은 이진 트리에서 한 트리가 다른 트리의 부분 트리인지를 확인하는 알고리즘입니다.

부분 트리 확인 알고리즘

부분 트리 확인 알고리즘은 두 단계로 이루어집니다.

  1. 첫 번째 단계에서는 두 트리에서 같은 값을 가진 노드를 찾습니다. 이때, 대상 트리 (큰 트리)를 순회하면서, 각 노드에 대해 재귀적으로 두 번째 단계로 이동합니다.
  2. 두 번째 단계에서는 대상 트리와 입력 트리 (작은 트리)의 현재 노드가 같은 값을 가지고 있는지를 확인하고, 만약 값이 같다면 각 노드의 좌우 하위 트리에 대해 재귀적으로 이동합니다.

다음은 이를 구현한 C++ 코드 예시입니다.

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
};

bool isIdentical(Node* s, Node* t) {
    if (s == nullptr && t == nullptr) return true;
    if (s == nullptr || t == nullptr) return false;

    return (s->data == t->data) && isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
}

bool isSubtree(Node* s, Node* t) {
    if (s == nullptr) return false;
    if (isIdentical(s, t)) return true;

    return isSubtree(s->left, t) || isSubtree(s->right, t);
}

위 코드는 입력 트리 t가 대상 트리 s의 부분 트리인지를 확인하는 함수를 보여줍니다.

결론

부분 트리 확인 알고리즘은 효율적인 방법으로 두 이진 트리가 서로 관련되어 있는지를 확인할 수 있는 중요한 알고리즘입니다. C++을 사용하여 간단하게 구현할 수 있으며, 재귀적인 방식으로 구현되어 있어 이해하기 쉽습니다.

참고 자료

© 2018 Colin. All rights reserved.