Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 트리에서 XOR 결과가 홀수인 인접 노드 쌍 개수 구하기

개요

이 튜토리얼에서는 C++를 활용하여 이진 트리에서 XOR 연산 결과가 홀수가 되는 인접 노드 쌍의 개수를 구하는 프로그램을 만들어 보겠습니다.

여기서 '인접 노드'란 부모와 자식처럼 트리에서 직접 연결되어 있는 노드를 의미합니다. 즉, 이진 트리가 주어졌을 때 서로 연결된 노드 쌍 가운데 XOR 값이 홀수인 경우의 수를 세는 것이 우리의 과제입니다.

핵심 원리

XOR(배타적 논리합) 연산의 성질을 살펴보면, 두 수의 XOR 결과가 홀수가 되려면 반드시 한 수는 홀수이고 다른 한 수는 짝수여야 합니다. 따라서 이 문제는 사실상 '홀짝성이 서로 다른 인접 노드 쌍의 개수'를 세는 문제와 같습니다.

알고리즘 접근 방식

  1. 루트 노드부터 깊이 우선 탐색(DFS)으로 트리를 순회합니다.
  2. 현재 노드에 부모 노드가 존재하는지 확인합니다.
  3. 부모 노드의 값과 현재 노드의 값을 XOR 연산하여 그 결과가 홀수인지 검사합니다.
  4. 홀수라면 카운트를 1 증가시키고, 왼쪽 자식과 오른쪽 자식 노드로 재귀 호출을 이어갑니다.

C++ 구현 코드

#include <iostream>
using namespace std;
// 트리 노드 구조체 정의
struct Node {
   int data;
   struct Node *left, *right;
};
// XOR 결과가 홀수인 인접 노드 쌍의 개수 계산
int count_pair(Node* root, Node *parent=NULL){
   if (root == NULL)
      return 0;
   // 부모-자식 쌍의 XOR이 홀수인지 확인
   int res = 0;
   if (parent != NULL && (parent->data ^ root->data) % 2)
      res++;
   return res + count_pair(root->left, root) + count_pair(root->right, root);
}
// 새 노드 생성 함수
Node* newNode(int data){
   Node* temp = new Node;
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
int main(){
   struct Node* root = NULL;
   root = newNode(15);
   root->left = newNode(13);
   root->left->left = newNode(12);
   root->left->right = newNode(14);
   root->right = newNode(18);
   root->right->left = newNode(17);
   root->right->right = newNode(21);
   printf("%d ", count_pair(root));
   return 0;
}

실행 결과

5

결과 분석

예제 트리에서 홀짝성이 서로 다른 인접 노드 쌍은 다음과 같습니다.

  • 15(홀수) – 18(짝수)
  • 13(홀수) – 12(짝수)
  • 13(홀수) – 14(짝수)
  • 18(짝수) – 17(홀수)
  • 18(짝수) – 21(홀수)

반면 15–13처럼 두 노드가 모두 홀수인 경우에는 XOR 결과가 짝수가 되므로 제외됩니다. 따라서 최종적으로 5개의 쌍이 출력됩니다.

복잡도 분석

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(N)입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 O(H)(H는 트리의 높이)입니다.