特定の二分木が完全な二分木であるかどうかをチェックするC++プログラム

二分木が与えられた場合、タスクはそれが完全な二分木であるかどうかを確認することです。すべてのノードに0個または2個の子がある場合、バイナリツリーは完全なバイナリツリーであると言われます。

例

入力-1

出力：

1

説明： リーフノードを除くすべてのノードには2つの子があるため、完全な二分木です。

入力-2：

出力：

0

説明： ノード2には子が1つしかないため、完全な二分木ではありません。

この問題を解決するためのアプローチ

特定の二分木がいっぱいかどうかを確認するために、左側のサブツリーと右側のサブツリーを再帰的に確認できます。

• ノードとその子を持つ特定の二分木を入力します。
• ブール関数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

説明： 指定されたバイナリツリーのすべてのリーフノードには子ノードがないため、完全なバイナリツリーではありません。したがって、出力は0になります。