Chúng ta được cung cấp hai cây tìm kiếm nhị phân làm đầu vào và một biến x. Mục đích là tìm các cặp nút từ mỗi cây sao cho tổng giá trị của các nút bằng x. Lấy nút 1 từ BST_1 và nút 2 từ BST_2 và thêm phần dữ liệu của cả hai. Nếu tổng =x. Số lượng tăng dần.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào
Đầu ra - Đếm các cặp từ hai BST có tổng bằng một giá trị x cho trước là - 1
Giải thích - Cặp là (8,6)
Đầu vào
Đầu ra −Tổng số các cặp từ hai BST có tổng bằng một giá trị x cho trước là - 2
Giải thích - Các cặp là (5,15) và (4,16)
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng tôi sẽ duyệt qua BST bằng cách sử dụng phương pháp inorder lặp đi lặp lại. Duyệt BST 1 từ nút nhỏ nhất đến nút lớn nhất bằng cách sử dụng phương pháp inorder lặp lại và duyệt BST 2 từ đảo ngược của phương pháp inorder lặp lại. Lấy tổng các nút hiện tại của cả hai BST. Nếu tổng là x số gia tăng. Nếu sum> x thì di chuyển đến tiền thân nhỏ hơn của nút hiện tại trong BST 2. Nếu sum
Lấy hai cây BST_1 và BST_2 có phần dữ liệu nguyên và các con trỏ trái, phải đến các nút con.
Hàm insert_node (int data) chèn một nút mới vào Cây với dữ liệu và trả về một con trỏ tới nó.
Tạo cả hai BST bằng cách sử dụng insert_node () và chuyển tới BST_sum_x (Tree * BST_1, Tree * BST_2, int x).
Hàm BST_sum_x (Cây * BST_1, Cây * BST_2, int x) lấy các nút gốc của cả hai cây và trả về số lượng các cặp nút với tổng phần dữ liệu là x.
Lấy số lượng ban đầu là 0 cho số cặp có tổng x.
Đối với các trình duyệt inorder lặp đi lặp lại, lấy hai biến Tree * stack_top_1, * stack_top_2;
Tạo hai ngăn xếp ngăn xếp stack_1, stack_2;
Bây giờ bắt đầu vòng lặp while bên ngoài.
Đi tới nút ngoài cùng bên trái (nhỏ nhất) của BST_1 bằng vòng lặp while và đẩy tất cả các nút vào ngăn xếp_1
Đi tới nút ngoài cùng bên phải (lớn nhất) của BST_2 bằng cách sử dụng vòng lặp while và đẩy tất cả các nút vào ngăn xếp_2
Nếu bất kỳ ngăn xếp nào trống, hãy phá vỡ vòng lặp while bên ngoài.
Lấy các nút trên cùng của cả hai ngăn xếp và thêm các phần dữ liệu của chúng và lưu trữ trong thời gian tạm thời.
Nếu temp (sum) ==x thì số gia tăng. Xóa các phần tử trên cùng khỏi cả stack_1 và stack_2 bằng thao tác bật lên.
Đặt BST_1 =stack_1-> phải và BST_2 =stack_2-> trái (người kế nhiệm tiếp theo trong BST_1 và người tiền nhiệm trong BST_2)
Nếu temp
IF temp>
x thì chỉ xóa phần trên khỏi ngăn xếp_2 và chuyển sang phần trước tiếp theo trong BST_1.
Ở cuối bên ngoài while, số đếm có một số cặp với nút của cả hai BST có tổng x.
Kết quả là số lượt trả lại.
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Ví dụ
#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;
} Đầu ra
Count of pairs from two BSTs whose sum is equal to a given value x ar: 1