입력받은 이진 트리가 다른 이진 트리의 하위 트리인지 확인하는 C++ 프로그램

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 형태의 자료구조입니다. 두 자식 노드는 각각 왼쪽 자식(left child)과 오른쪽 자식(right child)으로 구분됩니다.
이 글에서는 하나의 이진 트리가 다른 이진 트리 안에 포함되어 있는지, 즉 하위 트리(subtree)인지 판별하는 C++ 프로그램을 알고리즘과 함께 살펴보겠습니다.

하위 트리 판별 알고리즘

판별 과정은 두 단계로 나뉩니다. 먼저 두 트리가 완전히 동일한지 검사하는 identical() 함수를 정의하고, 이를 활용해 메인 트리를 순회하며 하위 트리 여부를 확인하는 Subtree() 함수를 작성합니다.

시작
    함수 identical():
        두 노드 r1과 r2를 매개변수로 받는다.
        만약 r1과 r2가 모두 NULL이면
            true를 반환한다.
        만약 r1 또는 r2 중 하나만 NULL이면
            false를 반환한다.
        다음 조건의 결과를 반환한다.
        (r1->d == r2->d 이고
         identical(r1->l, r2->l)이 참이고
         identical(r1->r, r2->r)이 참)

    함수 Subtree(node *T, node *S):
        만약 S == NULL이면
            true를 반환한다.
        만약 T == NULL이면
            false를 반환한다.
        만약 identical(T, S)의 결과가 참이면
            true를 반환한다.
        그렇지 않으면 Subtree(T->l, S) 또는 Subtree(T->r, S)의 결과를 반환한다.
종료

핵심 로직 설명

identical() 함수는 두 트리(또는 서브트리)의 모든 노드 값과 구조가 완전히 일치하는지 재귀적으로 비교합니다. Subtree() 함수는 메인 트리 T의 루트부터 시작하여 왼쪽과 오른쪽 자식 노드를 순서대로 탐색하면서, 각 노드 위치에서 S와 동일한 서브트리가 존재하는지 확인합니다. 한 가지 주의할 점은 빈 트리(S == NULL)는 어떤 트리의 하위 트리로도 간주한다는 것입니다.

C++ 예제 코드

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
struct n {
   int d;
   struct n* l;
   struct n* r;
};
bool Identical(struct n * r1, struct n *r2) {
   if (r1 == NULL && r2 == NULL)
      return true;
   if (r1 == NULL || r2 == NULL)
      return false;
   return (r1->d == r2->d && Identical(r1->l, r2->l) && Identical(r1->r, r2->r));
}
bool Subtree(struct n *T, struct n *S) {
   if (S == NULL)
      return true;
   if (T == NULL)
      return false;
   if (Identical(T, S))
      return true;
   return Subtree(T->l, S) || Subtree(T->r, S);
}
struct n* newN(int d) {
   struct n* nod =
   (struct n*)malloc(sizeof(struct n));
   nod->d = d;
   nod->l = NULL;
   nod->r = NULL;
   return(nod);
}
int main() {
   struct n *T = newN(24);
   T->r = newN(2);
   T->r->r = newN(5);
   T->l = newN(7);
   T->l->l = newN(3);
   T->l->l->r = newN(40);
   T->l->r = newN(6);
   struct n *S = newN(20);
   S->r = newN(5);
   S->l = newN(3);
   S->l->r = newN(50);
   if (Subtree(T, S))
      cout<<"given tree is subtree of Binary tree"<<"\n";
   else
      cout<<"given tree is not subtree of Binary tree"<<"\n";
   struct n *T1 = newN(30);
   T1->r = newN(20);
   T1->r->r = newN(19);
   T1->l = newN(17);
   T1->l->l = newN(4);
   T1->l->l->r = newN(40);
   T1->l->r = newN(15);
   struct n *S1 = newN(17);
   S1->r = newN(15);
   S1->l = newN(4);
   S1->l->r = newN(40);
   if (Subtree(T1, S1))
      cout<<"given tree is subtree of Binary tree";
   else
      cout<<"given tree is not subtree of Binary tree";
   getchar();
   return 0;
}

실행 결과

given tree is not subtree of Binary tree
given tree is subtree of Binary tree

첫 번째 테스트에서 사용한 트리 S(루트 값 20)는 메인 트리 T 어디에도 값이 20인 노드가 존재하지 않기 때문에 하위 트리가 아닌 것으로 판별됩니다. 반면 두 번째 테스트의 트리 S1(루트 값 17)은 메인 트리 T1의 왼쪽 부분과 구조 및 노드 값이 정확히 일치하므로 하위 트리로 판별됩니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(m × n)입니다. 여기서 m은 메인 트리의 노드 수, n은 하위 트리 후보의 노드 수를 의미합니다. 메인 트리의 모든 노드 위치에서 identical() 비교를 수행하기 때문입니다.