C ++のバイナリツリー（反復および再帰）の完全なノードをカウントします

バイナリツリーが与えられ、タスクは、反復的かつ再帰的なアプローチを使用して、バイナリツリーで使用可能な完全なノードの数を計算することです。フルノードとは、両方の子があり、子がnullでないノードです。フルノードでは、正確に2つの子を持つノードを考慮することに注意してください。

バイナリツリーは、データストレージの目的で使用される特別なデータ構造です。二分木には、各ノードが最大2つの子を持つことができるという特別な条件があります。バイナリツリーには、検索が並べ替えられた配列と同じくらい高速であり、挿入または削除操作がリンクリストと同じくらい高速であるため、順序付き配列とリンクリストの両方の利点があります。非リーフノードは、子が0を超え、子が2つ未満であるため、親ノードとも呼ばれます。

二分木の構造を以下に示します-

例

入力 −

出力 −カウントは2です

説明 −指定されたツリーには2つのノードがあります。つまり、正確に2つの子を持つ10と20、または完全なノードの他のノードには1つの子があるか、子がありません。

反復

以下のプログラムで使用されているアプローチは次のとおりです

• データ部分、左ポインタ、右ポインタを含むノードの構造を作成します。

• 二分木にノードを挿入する関数を作成します。

• フルノードをカウントする関数を作成します。

• 関数内で、IF！nodeをチェックしてから、ツリーにノードがないために戻ります。

• フルノードの数を格納するために一時変数の数を宣言します

• キュータイプ変数を作成します。たとえば、qu

• キュー内のノードをqu.push（node）

  としてプッシュします

• ！qu.empty（）

  の間にループします

• 一時変数を作成します。たとえば、ノードタイプの一時変数を作成し、queue.front（）

  で初期化します。

• qu.pop（）

  を使用して要素をポップします

• IF（！temp->左およびtemp->右）をチェックしてから、カウントを1ずつ増やします

• IF（temp-> left！=NULL）を確認してから、qu.push（temp-> left）

  を実行します。

• IF（temp-> right！=NULL）をチェックしてから、qu.push（temp-> right）

• カウントを返す

• 結果を印刷します。

例

// Iterative program to count full nodes
#include <iostream>
#include <queue>
using namespace std;
struct Node{
   int data;
   struct Node* left, *right;
};
// Function to count the full Nodes in a binary tree
int fullcount(struct Node* node){
   // Check if tree is empty
   if (!node){
      return 0;
   }  
   queue<Node *> myqueue;
   // traverse using level order traversing
   int result = 0;
   myqueue.push(node);
   while (!myqueue.empty()){
      struct Node *temp = myqueue.front();
      myqueue.pop();
      if (temp->left && temp->right){
         result++;
      }
      if (temp->left != NULL){
         myqueue.push(temp->left);
      }
      if (temp->right != NULL){
         myqueue.push(temp->right);
      }
   }
   return result;
}
struct Node* newNode(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int main(void){
   struct Node *root = newNode(10);
   root->left = newNode(20);
   root->right = newNode(30);
   root->left->left = newNode(40);
   root->left->right = newNode(50);
   root->left->left->right = newNode(60);
   root->left->right->right = newNode(70);
   cout <<"count is: "<<fullcount(root);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます-

count is: 2

再帰的

以下のプログラムで使用されているアプローチは次のとおりです

• データ部分、左ポインタ、右ポインタを含むノードの構造を作成します。

• 二分木にノードを挿入する関数を作成します。

• フルノードをカウントする関数を作成します。

• 関数内で、IF！nodeをチェックしてから、ツリーにノードがないために戻ります。

• 一時変数カウントを宣言して、ハーフノードのカウントを保存します

• IF（ルート->左およびルート->右）をチェックしてから、カウントを1ずつ増やします

• set count =count + recursive_call_to_this_function（root-> left）+ recursive_call_to_this_function（root-> right）

• カウントを返す

• 結果を印刷します。

例

// Recursive program to count full nodes
#include <iostream>
using namespace std;
struct Node{
   int data;
   struct Node* left, *right;
};
// Function to get the count of full Nodes
int fullcount(struct Node* root){
   if (root == NULL){
      return 0;
   }
   int result = 0;
   if (root->left && root->right){
      result++;
   }
   result += (fullcount(root->left) +
   fullcount(root->right));
   return result;
}
struct Node* newNode(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int main(){
   struct Node *root = newNode(10);
   root->left = newNode(20);
   root->right = newNode(30);
   root->left->left = newNode(40);
   root->left->right = newNode(50);
   root->left->left->right = newNode(60);
   root->left->right->right = newNode(70);
   cout <<"count is: "<<fullcount(root);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます-

count is: 2