資料結構
網路
關係資料庫管理系統 (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
