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

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

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

• สร้าง struct node สำหรับ binary tree
• เขียนฟังก์ชันเพื่อแทรกโหนดใหม่เข้าไปใน binary search tree
  • จำไว้ว่าใน binary search tree องค์ประกอบทั้งหมดที่น้อยกว่า root จะอยู่ซ้าย และมากกว่าจะอยู่ขวา
• เริ่มต้นสองรายการว่างเพื่อเก็บโหนดซ้ายและขวาของต้นไม้
• วนลูปผ่าน binary search tree จนกว่าโหนดซ้ายหรือขวาจะเป็น NULL หรือทั้งสองรายการไม่ว่าง
  • เขียนลูปเพื่อเก็บองค์ประกอบทั้งหมดเข้าไปในรายการโหนดซ้าย
  • เขียนลูปเพื่อเก็บองค์ประกอบทั้งหมดเข้าไปในรายการโหนดขวา
  • รับโหนดสุดท้ายจากแต่ละรายการ
  • ตรวจสอบสองค่า
    • ถ้าค่าโหนดด้านซ้ายมากกว่าหรือเท่ากับค่าโหนดด้านขวา ให้หยุดลูป
    • ถ้าผลรวมของสองค่าเท่ากับตัวเลขที่กำหนด ให้พิมพ์และลบพวกมันออกจากรายการ
    • ถ้าผลรวมของสองค่าน้อยกว่าตัวเลขที่กำหนด ให้ลบโหนดสุดท้ายจากรายการซ้ายและย้ายไปทางขวาของโหนด
    • ถ้าผลรวมของสองค่ามากกว่าตัวเลขที่กำหนด ให้ลบโหนดสุดท้ายจากรายการขวาและย้ายไปทางซ้ายของโหนด

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int data) {
        this->data = data;
        left = NULL;
        right = 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);
    return 0;
}

ผลลัพธ์

ถ้าคุณรันโค้ดด้านบน คุณจะได้ผลลัพธ์ดังนี้

19 31
20 30

สรุป

หากคุณมีคำถามในบทช่วยสอนนี้ ให้ระบุในส่วนความคิดเห็น