주어진 이진 트리가 전체 이진 트리인지 여부를 확인하는 C++ 프로그램

이진 트리가 주어지면 작업은 전체 이진 트리인지 여부를 확인하는 것입니다. 모든 노드에 0 또는 2개의 자식이 있는 경우 이진 트리를 전체 이진 트리라고 합니다.

예를 들어

입력-1

<강한>

출력:

1

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

입력-2:

<강한>

출력:

0

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

이 문제를 해결하기 위한 접근 방식

주어진 이진 트리가 가득 찼는지 여부를 확인하려면 왼쪽 하위 트리와 오른쪽 하위 트리를 재귀적으로 확인할 수 있습니다.

• 노드와 그 자식이 있는 주어진 바이너리 트리를 입력합니다.
• 부울 함수 isFullBinaryTree(Node*root)는 루트 노드를 입력으로 사용하고 전체 이진 트리이면 True를 반환하고 그렇지 않으면 거짓을 반환합니다.
• 기본 조건에서 루트 노드가 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

설명: 주어진 이진 트리의 모든 리프 노드에는 자식 노드가 없으므로 전체 이진 트리가 아닙니다. 따라서 출력은 0입니다.