Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm cặp có tổng bằng số đã cho trong cây tìm kiếm nhị phân.
Chúng tôi sẽ lưu trữ và các giá trị của cây trong hai danh sách khác nhau để tìm các cặp. Hãy xem các bước để giải quyết vấn đề.
-
Tạo một nút cấu trúc cho cây nhị phân.
-
Viết hàm để chèn một nút mới vào cây tìm kiếm nhị phân.
-
Hãy nhớ rằng, trong cây tìm kiếm nhị phân, tất cả các phần tử nhỏ hơn gốc sẽ nhỏ hơn và bên phải lớn hơn.
-
-
Khởi tạo hai danh sách trống để lưu trữ các nút bên trái và bên phải của cây.
-
Lặp lại cây tìm kiếm nhị phân cho đến khi các nút bên trái hoặc bên phải là NULL hoặc cả hai danh sách đều không trống.
-
Viết một vòng lặp để lưu trữ tất cả các phần tử vào danh sách các nút bên trái.
-
Viết một vòng lặp để lưu trữ tất cả các phần tử vào danh sách các nút bên phải.
-
Lấy các nút cuối cùng từ mỗi danh sách.
-
Kiểm tra hai giá trị.
-
Nếu giá trị nút bên trái lớn hơn hoặc bằng giá trị nút bên phải thì ngắt vòng lặp.
-
Nếu tổng hai giá trị bằng một số đã cho thì in và ngắt vòng lặp.
-
Nếu tổng hai giá trị nhỏ hơn số đã cho, thì hãy xóa nút cuối cùng khỏi danh sách bên trái và chuyển sang bên phải của nút.
-
Nếu tổng hai giá trị lớn hơn số đã cho, thì hãy xóa nút cuối cùng khỏi danh sách bên phải và chuyển sang bên trái của nút.
-
-
Ví dụ
Hãy xem mã.
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node *left, *right, *root;
Node(int data) {
this->data = data;
left = NULL;
right = NULL;
root = NULL;
}
};
Node* insertNewNode(Node *root, int data){
if (root == NULL) {
root = new Node(data);
return root;
}
if (root->data < data) {
root->right = insertNewNode(root->right, data);
}
else if (root->data > data) {
root->left = insertNewNode(root->left, data);
}
return root;
}
void findThePairs(Node *node, int target) {
vector<Node*> left_side_nodes;
vector<Node*> right_side_nodes;
Node *current_left = node;
Node *current_right = node;
while (current_left != NULL || current_right != NULL || (left_side_nodes.size() > 0 && right_side_nodes.size() > 0)) {
while (current_left != NULL) {
left_side_nodes.push_back(current_left);
current_left = current_left->left;
}
while (current_right != NULL) {
right_side_nodes.push_back(current_right);
current_right = current_right->right;
}
Node *left_side_node = left_side_nodes[left_side_nodes.size() - 1];
Node *right_side_node = right_side_nodes[right_side_nodes.size() - 1];
int left_side_value = left_side_node->data;
int right_side_value = right_side_node->data;
if (left_side_value >= right_side_value) {
break;
}
if (left_side_value + right_side_value < target) {
left_side_nodes.pop_back();
current_left = left_side_node->right;
}
else if (left_side_value + right_side_value > target) {
right_side_nodes.pop_back();
current_right = right_side_node->left;
}
else {
cout << left_side_node->data << " " << right_side_node->data << endl;
break;
}
}
}
int main() {
Node *root = NULL;
root = insertNewNode(root, 25);
root = insertNewNode(root, 20);
root = insertNewNode(root, 30);
root = insertNewNode(root, 15);
root = insertNewNode(root, 21);
root = insertNewNode(root, 19);
root = insertNewNode(root, 31);
findThePairs(root, 36);
} Đầu ra
Nếu bạn thực hiện chương trình trên, bạn sẽ nhận được kết quả sau.
15 21
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.