C++のバイナリツリーでリーフ以外のノードをカウントする

二分木が与えられ、タスクは二分木で利用可能な非リーフノードの数を計算することです。

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

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

例

入力 −

出力 −非リーフノードの数は次のとおりです：3

説明 −与えられたツリーでは、子が0を超え、子が2未満であるため、非リーフノードとして27、14、および35があります。

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

• 左ノードへのポインタ、右ノードへのポインタ、およびノー​​ドに格納されているデータ部分を含むバイナリツリーの構造を作成します

• この関数が呼び出されるたびにノードを挿入する関数を作成します。そのためには、新しいノードにデータを挿入し、新しいノードの左右のポインタをNULLに設定して、ノードを返します。

• 二分木の非葉ノードの数を数える再帰関数を作成します。

  • ルートがNULLであるか、ルートの左側がNULLで、ルートの右側がNULLであるかを確認し、0を返します
  • Return1+左ポインタを使用したこの関数への再帰呼び出し+右ポインタを使用したこの関数への再帰呼び出し

• カウントを印刷する

例

#include <iostream>
using namespace std;
// Node's structure
struct Node {
   int data;
   struct Node* left;
   struct Node* right;
};
// To define the new node
struct Node* newNode(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
// Count the non leaf nodes.
int nonleaf(struct Node* root){
   if (root == NULL || (root->left == NULL && root->right == NULL)){
      return 0;
   }
   return 1 + nonleaf(root->left) + nonleaf(root->right);
}
// Main function
int main(){
   struct Node* root = newNode(10);
   root->left = newNode(21);
   root->right = newNode(33);
   root->left->left = newNode(48);
   root->left->right = newNode(51);
   cout << nonleaf(root);
   return 0;
}

出力

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

count of non-leaf nodes is: 2