数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中计算二叉树中和等于给定值 x 的对数
给定一个整数值和一个变量 x，任务是构建二叉树并找到和等于给定值 x 的对。
例如
输入
int x = 5，输入值后创建的树如下所示：
输出
Count of pairs in a binary tree whose sum is equal to a given value x are: 2
解释
we are given with an array of integer values that is used to form a binary tree and we will check whether there is a pair present in a binary tree whose sum equals to the given value x which is 5. So, the pairs formed are (2, 3) and (1, 4).
输入
int x = 8，输入值后创建的树如下所示：
输出
Count of pairs in a binary tree whose sum is equal to a given value x are: 3
解释
we are given with an array of integer values that is used to form a binary tree and we will check whether there is a pair present in a binary tree whose sum equals to the given value x which is 8. So, the pairs formed are (2, 6), (4, 4) and (5, 3).
以下程序中使用的方案如下：
创建一个节点结构，包含数据部分以及指向左子树和右子树的左指针和右指针。
输入一个整数值，并使用它们通过左指针和右指针将数据输入节点，从而创建二叉树。
输入 x 的值，该值将用于计算和值为 x 的对。
创建一个布尔函数来检查对的和是否为 x。
在函数内部，检查根是否为 NULL，如果是则返回 False
检查根是否不等于 ptr 并且根的数据 + ptr 的数据是否等于 x，如果是则返回 True。
通过传递根的左指针、ptr 和值 x 以及 x 的右指针、ptr 和 x 来递归调用 check 函数。现在检查任何条件是否返回 true，如果是则返回 true。
否则，返回 false。
创建一个函数 total_pairs 来计算和为 x 的对的数量
在函数内部，检查 ptr 是否为 NULL，如果是则返回 0。
通过传递根、ptr 和 x 作为参数来调用 check 函数。如果函数返回 true，则将总对数的值加 1
通过传递根、ptr 的左指针、x 和总计来递归调用函数 total_pairs，并且还传递根、ptr 的右指针、x 和总计。
将存储在变量 total 中的整数值作为结果打印出来。
示例
#include <bits/stdc++.h>
using namespace std;
struct tree_node {
int data;
tree_node *left, *right;
};
tree_node* create_node(int data){
tree_node* newNode = (tree_node*)malloc(sizeof(tree_node));
newNode−>data = data;
newNode−>left = newNode−>right = NULL;
}
bool check(tree_node* root, tree_node* ptr, int x){
if(root==NULL){
return false;
}
if (root != ptr && ((root−>data + ptr−>data) == x)){
return true;
}
if (check(root−>left, ptr, x) || check(root−>right, ptr, x)){
return true;
}
return false;
}
void total_pairs(tree_node* root, tree_node* ptr, int x, int& total){
if(ptr == NULL){
return;
}
if(check(root, ptr, x) == true){
total++;
}
total_pairs(root, ptr−>left, x, total);
total_pairs(root, ptr−>right, x, total);
}
int main(){
int x = 5;
int total = 0;
tree_node* root = create_node(5);
root−>left = create_node(2);
root−>right = create_node(3);
root−>left−>left = create_node(1);
root−>left−>right = create_node(4);
root−>right−>left = create_node(6);
total_pairs(root, root, x, total);
total = total / 2;
cout<<"Count of pairs in a binary tree whose sum is equal to a given value x are: "<< total;
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count of pairs in a binary tree whose sum is equal to a given value x are: 2
更新于：2021年1月7日
176 次查看
广告