資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中計算總和為給定值 x 的子樹
給定一棵二叉樹和一個作為輸入的值 x。目標是找到二叉樹中所有節點權重之和等於 x 的子樹。
例如
輸入
x = 14。輸入值後建立的樹如下所示
輸出
Count of subtrees that sum up to a given value x are: 1
解釋
we are given with a x value as 14. As we can see there is only one leaf node with the values as 14 therefore the count is 1.
輸入
x = 33。輸入值後建立的樹如下所示 -
輸出
Count of subtrees that sum up to a given value x are: 2
解釋
we are given with a x value as 33. As we can see there are two subtrees with the sum values as 33 therefore the count is 2.
以下程式中使用的方案如下 -
在這種方法中，我們將遞迴地計算根節點的左子樹和右子樹的權重之和，最後將其新增到根節點的權重中。如果總和等於 x，則遞增計數。
構造一棵以根作為其根指標的樹 Tree_Node。
函式 insert_Node(int data) 將節點新增到這棵樹中。
函式 subtrees_x(Tree_Node* root, int x) 獲取指向樹的根指標和 x，並返回總和為給定值 x 的子樹的數量。
將一個靜態變數 count 設為 0，因為我們將遞迴地計算 count。
將一個 Tree_node 型別的靜態節點作為根。
初始化變數 Left_subtree = 0，Right_subtree = 0。用於從根節點計算左右子樹中節點的權重之和。
如果根為 NULL，則返回總和為 0。
計算 Left_subtree += subtrees_x(root−>Left, x) 用於計算左子樹中節點的總和。
計算 Right_subtree += subtrees_x(root−>Right, x) 用於計算左子樹中節點的總和。
設定 sum=Left_subtree + Right_subtree + root−>ldata。
如果 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
279 次檢視
