在 C++ 中的 BST 中查找具有给定和的所有对

  • Z时代
  • 2024-01-10
  • 分类：综合

在本教程中，我们将编写一个程序来查找二叉搜索树中总和等于给定数字的所有对。

我们将在两个不同的列表中存储树的值以找到对。让我们看看解决问题的步骤。

  • 为二叉树创建一个结构节点。

  • 编写一个函数将一个新节点插入到二叉搜索树中。

    • 请记住，在二叉搜索树中，所有小于 root 的元素都较小，而 right 较大。

  • 初始化两个空列表来存储树的左右节点。

  • 迭代二叉搜索树，直到左节点或右节点为 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

结论

如果您对本教程有任何疑问，请在评论部分提及。

以上是 在 C++ 中的 BST 中查找具有给定和的所有对 的全部内容， 来源链接： utcz.com/z/335648.html

回到顶部