C++로 구현하는 전체 이진 트리(Full Binary Tree) 판별 프로그램

이진 트리(Binary Tree)가 주어졌을 때, 해당 트리가 전체 이진 트리(Full Binary Tree)인지 판별하는 것이 목표입니다. 전체 이진 트리란 모든 노드가 자식을 갖지 않거나(0개), 정확히 두 개의 자식을 가지는 이진 트리를 의미합니다.

예시

입력-1

출력:

1

설명: 리프 노드를 제외한 모든 노드가 두 개의 자식을 가지고 있으므로, 이 트리는 전체 이진 트리입니다.

입력-2

출력:

0

설명: 노드 2가 자식을 하나만 가지고 있으므로, 이 트리는 전체 이진 트리가 아닙니다.

문제 해결 접근 방법

주어진 이진 트리가 전체 이진 트리인지 확인하려면 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 검사하는 방법을 사용할 수 있습니다.

• 노드와 그 자식들로 구성된 이진 트리를 입력으로 받습니다.
• 불리언 함수 isFullBinaryTree(Node* root)는 루트 노드를 입력으로 받아, 트리가 전체 이진 트리이면 true를, 그렇지 않으면 false를 반환합니다.
• 기저 조건에서 루트 노드가 NULL이거나 비어 있는 경우 true를 반환합니다.
• 왼쪽 서브트리와 오른쪽 서브트리가 모두 NULL이라면 true를 반환합니다.
• 이후 왼쪽 서브트리와 오른쪽 서브트리에 대해 각각 재귀적으로 검사한 뒤, 그 결과를 반환합니다.

구현 예제

#include<iostream>
using namespace std;
struct treenode {
    int data;
    treenode * left;
    treenode * right;
};
struct treenode * createNode(int d) {
    struct treenode * root = new treenode;
    root -> data = d;
    root -> left = NULL;
    root -> right = NULL;
    return root;
}
bool isFullBinaryTree(struct treenode * root) {
    if (root == NULL) {
        return true;
    }
    if (root -> left == NULL and root -> right == NULL) {
        return true;
    } else if (root -> left and root -> right) {
        return (isFullBinaryTree(root -> left) and isFullBinaryTree(root -> right));
    }
    return false;
}
int main() {
    struct treenode * root = NULL;
    root = createNode(1);
    root -> left = createNode(2);
    root -> right = createNode(3);
    root -> left -> right = createNode(4);
    root -> left -> left = createNode(5);
    root -> right -> left = createNode(6);
    if (isFullBinaryTree(root)) {
        cout << "1" << endl;
    } else {
        cout << "0" << endl;
    }
    return 0;
}

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

출력

0

설명: 위 예제에서 노드 3은 자식을 하나만 가지고 있습니다. 전체 이진 트리가 되려면 모든 노드가 자식을 0개 또는 2개 가져야 하므로, 이 트리는 전체 이진 트리가 아니며 출력 결과는 0이 됩니다.