Sıra istifadə edərək BST-də bir Yolu tərsinə çevirin

Sıra problemindən istifadə edərək BST-də bir tərs yolda İkili Axtarış verdik Ağac və düyün, bir yazın alqoritm yolu kökündən verilmiş düyününə qaytarmaq. Düyünün BST-də olduğunu düşünək.

misal

Input

Pin

Hədəf Nodu = 12
Buraxılış

Pin

Sifarişlə xain geri əvvəl
3 4 7 8 9 12 15 18
Geri döndükdən sonra sifariş qaydasında keçid
3 4 7 12 15 8 9 18

Sıra istifadə edərək BST-də bir Yolu tərsləşdirmək üçün alqoritm

Kökdən düyünə gedən yolu geri qaytarmaq, düyündən düyünə gedən yoldakı qovşaqların elementlərini geri qaytarmaqla eynidir. Məsələn, kökündən düyünə gedən yol 5 -> 10 -> 15 -> 20-dirsə, yolu geri qaytarmaq məlumatları tərs etməklə eynidir. Deməli, tərs yol 20 -> 15 -> 10 -> 5 olur.
Fikir kökündən verilmiş düyünə yolda gələn qovşaqların bütün dəyərlərini bir növbədə itələmək və itələdikdən sonra cari düyünü növbənin ön hissəsindəki elementlə əvəz etməkdir.

reversePathBST (kök, hədəf)

1. Kök boşdursa, geri qayıdın.
2. Kök dəyəri hədəfə bərabərdirsə, kök dəyərini növbəyə itələyin və kök dəyərini növbənin ön hissəsindəki elementlə əvəz edin. Növbənin önündəki elementi çıxarın.
3. Başqa bir halda kök dəyəri hədəfdən azdırsa, kök dəyərini növbəyə itələyin, kökün sol uşağı üçün reversePathBST-yə müraciət edin və sonra kök dəyərini növbənin önündəki elementlə əvəz edin. Ayrıca, növbənin ön hissəsindəki elementi çıxarın.
4. Başqa birində kökün dəyərini növbəyə itələyin, kökün sağ uşağı üçün reversePathBST-yə müraciət edin və sonra kök dəyərini növbənin ön hissəsindəki elementlə əvəz edin. Ayrıca, növbənin ön hissəsindəki elementi çıxarın.

Queue istifadə edərək BST-də bir yolun tərs olması üçün JAVA kodu

import java.util.LinkedList;
import java.util.Queue;

public class ReverseAPathInBSTUsingQueue {
    // class representing node of a BST
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // queue used to reverse the path in BST
    private static Queue<Integer> queue;

    // function to print inorder traversal of a tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static void reversePath(Node root, int target) {
        // if root is null return
        if (root == null) {
            return;
        }

        // add root's data to queue
        queue.add(root.data);

        if (root.data == target) {
            // Base case
        } else if (root.data > target) {
            // target is in left sub tree
            reversePath(root.left, target);
        } else {
            // target is in right sub tree
            reversePath(root.right, target);
        }

        // replace root's data with front of queue
        root.data = queue.poll();
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(8);
        root.left = new Node(4);
        root.right = new Node(9);
        root.left.left = new Node(3);
        root.left.right = new Node(7);
        root.right.right = new Node(15);
        root.right.right.left = new Node(12);
        root.right.right.right = new Node(18);

        // inorder traversal before reversing
        System.out.println("Inorder before reversal");
        inorder(root);
        System.out.println();

        queue = new LinkedList<>();
        reversePath(root, 12);

        // inorder traversal after reversing
        System.out.println("Inorder after reversal");
        inorder(root);
        System.out.println();
    }
}

Inorder before reversal
3 4 7 8 9 12 15 18 
Inorder after reversal
3 4 7 12 15 8 9 18

C ++ kodunu növbədən istifadə edərək BST-də tərs yol

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

// class representing node of a BST
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// queue used to reverse the path in BST
queue<int> q;

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

void reversePath(Node *root, int target) {
    // if root is null return
    if (root == NULL) {
        return;
    }
    
    // add root's data to queue
    q.push(root->data);
    
    if (root->data == target) {
        // Base case
    } else if (root->data > target) {
        // target is in left sub tree
        reversePath(root->left, target);
    } else {
        // target is in right sub tree
        reversePath(root->right, target);
    }
    
    // replace root's data with front of queue
    root->data = q.front();
    q.pop();
}

int main() {
    // Example Tree
    Node *root = new Node(8);
    root->left = new Node(4);
    root->right = new Node(9);
    root->left->left = new Node(3);
    root->left->right = new Node(7);
    root->right->right = new Node(15);
    root->right->right->left = new Node(12);
    root->right->right->right = new Node(18);

    // inorder traversal before reversing
    cout<<"Inorder before reversal"<<endl;
    inorder(root);
    cout<<endl;
    
    reversePath(root, 12);

    // inorder traversal after reversing
    cout<<"Inorder after reversal"<<endl;
    inorder(root);
    cout<<endl;
    
    return 0;
}

Inorder before reversal
3 4 7 8 9 12 15 18 
Inorder after reversal
3 4 7 12 15 8 9 18

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (log n)
Kosmik Mürəkkəblik = O (log n)
burada n - İkili Axtarış Ağacındakı qovşaq sayı.

References