이진 트리 Q1. 두 트리가 같은 구조인지 확인하기

자료구조 C 실습 · 이진 트리 · Q1

이진 트리 Q1. 두 트리가 같은 구조인지 확인하기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section E Binary Tree identical

두 개의 이진 트리가 구조적으로 같은 모양인지 재귀로 검사하는 문제다. 값만 비교하는 문제가 아니라, `왼쪽-오른쪽 하위 트리 구조가 동시에 같은가`를 끝까지 내려가며 확인해야 한다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Binary_Tree\Q1_E_BT.c

대상 함수: identical

카테고리: 이진 트리

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Create a binary tree1.
• 2: Create a binary tree2.
• 3: Check whether two trees are structurally identical.
• 0: Quit
• Creating tree1
• The resulting tree1 is

핵심 구현 흐름

STEP 1

두 노드가 모두 NULL이면 같은 구조로 본다.

STEP 2

한쪽만 NULL이면 구조가 다르므로 바로 false다.

STEP 3

현재 노드가 모두 존재하면 왼쪽 서브트리와 오른쪽 서브트리를 재귀로 함께 검사한다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: identical

int identical(BTNode *tree1, BTNode *tree2)

{
   // 두 노드가 모두 NULL이면 이 부분 트리는 구조적으로 동일하다고 판단
   if (tree1 == NULL && tree2 == NULL)
   {
        return 1;
   }
   // 두 노드 중 하나만 NULL이면 구조가 다르다고 판단
   else if(tree1 == NULL || tree2 == NULL)
   {
        return 0;
   }
   else 
   {
        // 양쪽 노드가 모두 존재하면, 각각의 왼쪽 자식과 오른쪽 자식이 모두 동일한지 재귀적으로 검사
        return identical(tree1->left, tree2->left) && identical(tree1->right, tree2->right);
   }
}

구현할 때 체크할 점

• NULL 비교 순서를 잘못 잡으면 재귀 진입 전에 segmentation fault가 난다.
• 문제 조건이 '구조적 동일성'인지 '값까지 동일'인지 먼저 확인해야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 값만 비교하는 문제가 아니라, `왼쪽-오른쪽 하위 트리 구조가 동시에 같은가`를 끝까지 내려가며 확인해야 한다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.