数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中从两棵二叉搜索树中计数和等于给定值x的节点对
给定两棵二叉搜索树作为输入和一个变量x。目标是从每棵树中找到节点对，使得节点值的和等于x。从BST_1取节点1，从BST_2取节点2，并添加两者的数据部分。如果sum=x，则递增计数。
让我们通过示例来理解。
输入
输出 - 从两棵二叉搜索树中计数和等于给定值x的节点对为 - 1
说明 - 节点对为(8,6)
输入
输出 - 从两棵二叉搜索树中计数和等于给定值x的节点对为 - 2
说明 - 节点对为(5,15)和(4,16)
下面程序中使用的方案如下
在这个方案中，我们将使用迭代中序遍历方法遍历BST。使用迭代中序遍历方法从最小节点到最大节点遍历BST 1，并使用迭代中序遍历方法的反向遍历BST 2。取两棵BST当前节点的和。如果sum为x，则递增计数。如果sum>x，则移动到BST 2中当前节点的中序前驱。如果sum 取两棵树BST_1和BST_2，它们具有整数数据部分以及指向子节点的左、右指针。 函数insert_node(int data)向树中插入一个具有数据的新节点，并返回指向它的指针。 使用inser_node()创建两棵BST，并将其传递给BST_sum_x(Tree* BST_1, Tree* BST_2, int x)。 函数BST_sum_x(Tree* BST_1, Tree* BST_2, int x)接受两棵树的根节点，并返回数据部分之和为x的节点对的数量。 将初始计数设置为0，表示具有和为x的节点对的数量。 对于迭代中序遍历，取两个变量Tree* stack_top_1, *stack_top_2; 创建两个栈stack stack_1, stack_2; 现在开始外层while循环。 使用while循环转到BST_1的最左（最小）节点，并将所有节点压入stack_1 使用while循环转到BST_2的最右（最大）节点，并将所有节点压入stack_2 如果任何一个栈为空，则中断外层while循环。 取两个栈的顶部节点，并将它们的数据部分相加，存储在temp中。 如果temp（和）== x，则递增计数。使用pop操作从stack_1和stack_2中移除顶部元素。 设置BST_1=stack_1->right 和 BST_2=stack_2->left（BST_1中的下一个后继和BST_2中的前驱） 如果temp 如果temp>x，则只从stack_2中移除顶部元素，并移动到BST_1中的下一个前驱。 在外层while循环结束时，count包含具有两棵BST节点且和为x的节点对的数量。 返回count作为结果。 如果我们运行上述代码，它将生成以下输出： 216次浏览示例
#include <bits/stdc++.h>
using namespace std;
struct Tree{
int data;
Tree* left, *right;
};
Tree* insert_node(int data){
Tree* newNode = (Tree*)malloc(sizeof(Tree));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
}
int BST_sum_x(Tree* BST_1, Tree* BST_2, int x){
int count = 0;
Tree* stack_top_1, *stack_top_2;
stack<Tree*> stack_1, stack_2;
if (BST_1 == NULL || BST_2 == NULL){
return 0;
}
while (1){
while (BST_1 != NULL){
stack_1.push(BST_1);
BST_1 = BST_1->left;
}
while (BST_2 != NULL){
stack_2.push(BST_2);
BST_2 = BST_2->right;
}
if (stack_1.empty() || stack_2.empty()){
break;
}
stack_top_1 = stack_1.top();
stack_top_2 = stack_2.top();
int temp = stack_top_1->data + stack_top_2->data;
if (temp == x){
count++;
stack_1.pop();
stack_2.pop();
BST_1 = stack_top_1->right;
BST_2 = stack_top_2->left;
}
else if (temp < x){
stack_1.pop();
BST_1 = stack_top_1->right;
}
else{
stack_2.pop();
BST_2 = stack_top_2->left;
}
}
return count;
}
int main(){
//BST 1
Tree* BST_1 = insert_node(15);
BST_1->left = insert_node(10);
BST_1->right = insert_node(8);
BST_1->left->left = insert_node(12);
BST_1->left->right = insert_node(24);
BST_1->right->left = insert_node(16);
//BST 2
Tree* BST_2 = insert_node(20);
BST_2->left = insert_node(16);
BST_2->right = insert_node(4);
BST_2->left->left = insert_node(18);
BST_2->left->right = insert_node(28);
BST_2->right->left = insert_node(22);
int x = 28;
cout<<"Count of pairs from two BSTs whose sum is equal to a given value x ar: "<<BST_sum_x(BST_1, BST_2, x);
return 0;
}输出
Count of pairs from two BSTs whose sum is equal to a given value x ar: 1
