C++で指定した値xと合計が一致する部分木の数を数える方法

この記事では、二分木（バイナリツリー）と値 x を入力として受け取り、ノードの重みの合計が x と一致するすべての部分木を見つける方法を解説します。

例1

入力

x = 14 の場合。入力された値から構築される木は以下の通りです。

出力

Count of subtrees that sum up to a given value x are: 1

説明

与えられた値は x = 14 です。値が 14 である葉ノードは1つだけなので、カウントは 1 となります。

例2

入力

x = 33 の場合。入力された値から構築される木は以下の通りです。

出力

Count of subtrees that sum up to a given value x are: 2

説明

与えられた値は x = 33 です。合計が 33 となる部分木は2つ存在するため、カウントは 2 となります。

プログラムで使用するアプローチ

このアプローチでは、再帰的にルートノードの左部分木と右部分木の重みの合計を計算し、最後にルート自身の重みを加算します。その合計が x と一致すれば、カウントを増やします。

• ルートへのポインタを持つ構造体 Tree_Node を定義して木を構築します。
• 関数 insert_Node(int data) は、この木に新しいノードを追加します。
• 関数 subtrees_x(Tree_Node* root, int x) は、木のルートポインタと値 x を受け取り、合計が x に一致する部分木の個数を返します。
• 再帰的にカウントを計算するため、static 変数 count を 0 で初期化します。
• Tree_Node 型の static ポインタ temp を root で初期化します。
• ルートから見た左部分木・右部分木のノード重みの合計を格納するため、変数 Left_subtree = 0、Right_subtree = 0 を初期化します。
• root が NULL の場合は、合計として 0 を返します。
• Left_subtree += subtrees_x(root->Left, x) により、左部分木のノードの合計を計算します。
• Right_subtree += subtrees_x(root->Right, x) により、右部分木のノードの合計を計算します。
• sum = Left_subtree + Right_subtree + root->data とします。
• sum が x と一致した場合、count をインクリメントします。
• temp != root の場合（開始ノードではない場合）は、Left_subtree + root->data + Right_subtree を合計として返します。
• 最後に count を返します。これが、ノードの合計が x に一致する木の個数となります。

コード例

#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
    int data;
    Tree_Node *Left, *Right;
};
Tree_Node* insert_Node(int data){
    Tree_Node* new_node = (Tree_Node*)malloc(sizeof(Tree_Node));
    new_node->data = data;
    new_node->Left = new_node->Right = NULL;
    return new_node;
}
int subtrees_x(Tree_Node* root, int x){
    static int count = 0;
    static Tree_Node* temp = root;
    int Left_subtree = 0, Right_subtree = 0;
    if(root == NULL){
        return 0;
    }
    Left_subtree += subtrees_x(root->Left, x);
    Right_subtree += subtrees_x(root->Right, x);
    int sum = Left_subtree + Right_subtree + root->data;
    if(sum == x){
        count++;
    }
    if(temp != root){
        int set = Left_subtree + root->data + Right_subtree;
        return set;
    }
    return count;
}
int main(){
    Tree_Node* root = insert_Node(10);
    root->Left = insert_Node(20);
    root->Right = insert_Node(12);
    root->Left->Left = insert_Node(14);
    root->Left->Right = insert_Node(1);
    root->Right->Left = insert_Node(21);
    root->Right->Right = insert_Node(11);
    int x = 14;
    cout<<"Count of subtrees that sum up to a given value x are: "<<subtrees_x(root, x);
    return 0;
}

出力

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

Count of subtrees that sum up to a given value x are: 1