C++ ย้อนกลับเส้นทางใน BST โดยใช้ Queue

กำหนด Binary Search Tree (BST) และเราต้องการย้อนกลับเส้นทางจากคีย์เฉพาะ ตัวอย่างเช่น:

วิธีการหาคำตอบ

ในวิธีนี้ เราจะสร้าง queue และ push ทุกโหนดจนกว่าจะได้ root

ตัวอย่าง

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

struct node {
    int key;
    struct node *left, *right;
};

struct node* newNode(int item){
    struct node* temp = new node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(struct node* root){
    if (root != NULL) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}

void Reversing(struct node** node, int& key, queue& q1){
    /* ถ้าต้นไม้ว่างเปล่า แล้ว return */
    if (node == NULL)
        return;
    if ((*node)->key == key){ // ถ้าหาคีย์เจอ
        q1.push((*node)->key); // เรา push เข้า queue
        (*node)->key = q1.front(); // เราเปลี่ยนองค์ประกอบแรกของ queue กับปัจจุบัน
        q1.pop(); // เรา pop องค์ประกอบแรก
    }
    else if (key < (*node)->key){ // ถ้าคีย์น้อยกว่าค่าของโหนดปัจจุบัน
        q1.push((*node)->key); // เรา push องค์ประกอบเข้า queue
        Reversing(&(*node)->left, key, q1); // เราไปที่ subtree ซ้ายด้วยการเรียกซ้ำ
        (*node)->key = q1.front(); // เราย้อนกลับองค์ประกอบ
        q1.pop(); // เรา pop องค์ประกอบแรก
    }
    else if (key > (*node)->key){ // ถ้าคีย์มากกว่า key ของโหนด
        q1.push((*node)->key); // เรา push node key เข้า queue
        Reversing(&(*node)->right, key, q1); // เราไปที่ subtree ขวาด้วยการเรียกซ้ำ
        (*node)->key = q1.front(); // แทนที่ queue front เป็น node key
        q1.pop(); // เรา pop องค์ประกอบแรก
    }
    return;
}

struct node* insert_node(struct node* node, int key){
    if (node == NULL)
        return newNode(key); // ถ้าต้นไม้ว่าง คืนโหนดใหม่
    if (key < node->key) // ไม่เช่นนั้น เรา push เข้าต้นไม้
        node->left = insert_node(node->left, key);
    else if (key > node->key)
        node->right = insert_node(node->right, key);
    return node; // คืนโหนด
}

int main(){
    struct node* root = NULL;
    queue q1;
    int k = 80;
    /****************Creating the BST*************************/
    root = insert_node(root, 50);
    insert_node(root, 30);
    insert_node(root, 20);
    insert_node(root, 40);
    insert_node(root, 70);
    insert_node(root, 60);
    insert_node(root, 80);
    cout << "Before Reversing :\n";
    inorder(root);
    cout << "\n";
    Reversing(&root, k, q1);
    cout << "After Reversing :\n";
    // พิมพ์ inorder ของต้นไม้ที่ย้อนกลับเส้นทาง
    inorder(root);
    return 0;
}

ผลลัพธ์

Before Reversing : 20 30 40 50 60 70 80
After Reversing : 20 30 40 80 60 70 50

คำอธิบายโค้ด

ในวิธีนี้ เราเพียงแค่จะค้นหาคีย์ที่กำหนด ขณะที่เราเดินทางผ่านต้นไม้ เรา push ทุกโหนดเข้า queue และตอนนี้เมื่อเราหาโหนดที่มีค่าเท่ากับคีย์ เราสลับค่าของโหนดในเส้นทางทั้งหมดกับค่าที่อยู่หน้าคิว และในกระบวนการนี้ เส้นทางของเราจะกลายเป็นย้อนกลับ

สรุป

เราแก้ปัญหาการย้อนกลับเส้นทางใน BST โดยใช้ queue และการเรียกซ้ำ เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ปกติ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์