Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ค้นหาคู่ทั้งหมดที่มีผลรวมที่กำหนดใน BST ใน C++


ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมที่จะหาคู่ทั้งหมดที่มีผลรวมเท่ากับตัวเลขที่ระบุในแผนผังการค้นหาแบบไบนารี

เราจะเก็บค่าของต้นไม้ในสองรายการที่แตกต่างกันเพื่อค้นหาคู่ มาดูขั้นตอนการแก้ปัญหากัน

  • สร้างโหนด struct สำหรับไบนารีทรี

  • เขียนฟังก์ชันเพื่อแทรกโหนดใหม่ลงในแผนผังการค้นหาแบบไบนารี

    • โปรดจำไว้ว่า ในแผนผังการค้นหาแบบไบนารี องค์ประกอบทั้งหมดที่น้อยกว่ารูทจะเล็กกว่า และส่วนขวาจะใหญ่กว่า

  • เริ่มต้นรายการว่างสองรายการเพื่อเก็บโหนดซ้ายและขวาของทรี

  • วนซ้ำบนแผนผังการค้นหาแบบไบนารีจนกว่าโหนดด้านซ้ายหรือด้านขวาจะเป็น 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

บทสรุป

หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น