在C++中查找BST中具有给定和的全部数对
在本教程中,我们将编写一个程序,该程序查找二叉搜索树中所有和等于给定数字的数对。
我们将把树的值存储在两个不同的列表中以查找数对。让我们看看解决问题的步骤。
为二叉树创建一个结构体节点。
编写一个函数以将新节点插入到二叉搜索树中。
记住,在二叉搜索树中,所有小于根的元素都较小,而右边的元素都较大。
初始化两个空列表以存储树的左节点和右节点。
迭代二叉搜索树,直到左节点或右节点为NULL或两个列表都不为空。
编写一个循环以将所有元素存储到左节点列表中。
编写一个循环以将所有元素存储到右节点列表中。
获取每个列表中的最后一个节点。
检查两个值。
如果左侧节点值大于或等于右侧节点值,则中断循环。
如果两个值的和等于给定数字,则打印并将其从列表中删除。
如果两个值的和小于给定数字,则从左列表中删除最后一个节点并移动到节点的右侧。
如果两个值的和大于给定数字,则从右列表中删除最后一个节点并移动到节点的左侧。
示例
让我们看看代码。
#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; right_side_nodes.pop_back(); left_side_nodes.pop_back(); current_left = left_side_node->right; current_right = right_side_node->left; } } } 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, 50); }t, *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 tar) { 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 < tar) { left_side_nodes.pop_back(); current_left = left_side_node->right; } else if (left_side_value + right_side_value > tar) { right_side_nodes.pop_back(); current_right = right_side_node->left; } else { cout << left_side_node->data << " " << right_side_node->data << endl; right_side_nodes.pop_back(); left_side_nodes.pop_back(); current_left = left_side_node->right; current_right = right_side_node->left; } } } 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, 50); }
输出
如果运行以上代码,则会得到以下结果。
19 31 20 30
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
结论
如果您在本教程中遇到任何疑问,请在评论部分中提出。
广告