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

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

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

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

例

入力 −

出力 −カウントは2です

説明 −指定されたツリーには2つのノードがあります。つまり、40と50に1つの子があるか、半分のノードがあります。他のノードには2つの子があるか、子がない場合があります。

反復

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

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

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

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

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

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

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

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

  としてプッシュします

• ！qu.empty（）

  の間にループします

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

  で初期化します。

• qu.pop（）

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

• IF（！temp-> leftAND temp-> right）OR（temp-> left AND！temp-> right）をチェックしてから、カウントを1ずつ増やします

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

  を実行します。

• カウントを返す

• 結果を印刷します。

例

// Program to count half nodes in a Binary Tree
#include <iostream>
#include <queue>
using namespace std;
struct Node{
   int data;
   struct Node* left, *right;
};
// Function to get the count of half Nodes
int halfcount(struct Node* node){
   // If tree is empty
   if (!node)
   return 0;
   int result = 0; // Initialize count of half nodes
   // Do level order traversal starting from root
   queue<Node *> myqueue;
   myqueue.push(node);
   while (!myqueue.empty()){
      struct Node *temp = myqueue.front();
      myqueue.pop();
      if ((!temp->left && temp->right) || (temp->left && !temp->right)){
         result++;
      }
      if (temp->left != NULL){
         myqueue.push(temp->left);
      }
      if (temp->right != NULL){
         myqueue.push(temp->right);
      }
   }
   return result;
}
/* To allocate new Node with the given data and NULL left
and right pointers. */
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: "<<halfcount(root);
   return 0;
}

出力

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

count is: 2

再帰的

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

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

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

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

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

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

• IF（root-> left =NULL AND root-> right！=NULL）OR（root-> left！=NULL AND root-> right ==NULL）をチェックしてから、カウントを1増やします

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

• カウントを返す

• 結果を印刷します。

例

// Recursive program to count half nodes
#include <bits/stdc++.h>
using namespace std;
// A binary tree Node has data, pointer to left
// child and a pointer to right child
struct Node{
   int data;
   struct Node* left, *right;
};
int halfcount(struct Node* root){
   if (root == NULL)
   return 0;
   int result = 0;
   if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right ==
   NULL)){
      result++;
   }
   result += (halfcount(root->left) + halfcount(root->right));
   return result;
}
/* to allocate a new Node with the given data and NULL left
and right pointers. */
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: "<<halfcount(root);
   return 0;
}

出力

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

count is: 2