Кезекті пайдаланып BST жолды кері бұрыңыз


Күрделілік дәрежесі орта
Жиі кіреді Bloomberg Google Грейфтерлер HSBC Microsoft Target Corporation
Екілік іздеу ағашы Екілік ағаш кезек Траверсал ағаш Ағаштарды кесу

Кезекте тұрған есептер көмегімен BST жолының кері бағытында біз екілік іздеу жасадық ағаш және түйін, жазыңыз алгоритм берілген түйінге тамырдан жолды кері бұру. Түйін BST-де бар деп есептейік.

мысал

енгізу

Кезекті пайдаланып BST жолды кері бұрыңыз

Мақсатты түйін = 12
шығыс

Кезекті пайдаланып BST жолды кері бұрыңыз

Қалпында көлденең қалпына келтіруге дейін
3 4 7 8 9 12 15 18
Реверстен кейін тәртіп бойынша жүру
3 4 7 12 15 8 9 18

Кезекті қолдану арқылы BST жолды кері бұру алгоритмі

Түбірден түйінге жолды кері бұру түбірден түйінге дейінгі жолдағы түйіндердің элементтерін кері қайтарумен бірдей. Мысалы, егер түбірден түйінге дейінгі жол 5 -> 10 -> 15 -> 20 болса, онда жолды кері бұру деректерді кері қайтарумен бірдей. Сонымен, кері жол 20 -> 15 -> 10 -> 5 құрайды.
Идея түбірден бастап берілген түйінге жолға түсетін түйіндердің барлық мәндерін кезекте итеріп, итергеннен кейін ағымдағы түйінді кезектің алдыңғы жағындағы элементпен ауыстыру.

reversePathBST (түбір, мақсат)

  1. Егер түбір нөл болса, қайтарыңыз.
  2. Егер түбір мәні мақсатқа тең болса, онда түбір мәнін кезекке итеріп, түбір мәнін кезектің алдыңғы жағындағы элементпен ауыстырыңыз. Кезектің алдындағы элементті алып тастаңыз.
  3. Басқа жағдайда, егер түбір мәні мақсаттан аз болса, онда түбір мәнін кезекке итеріп, түбірдің сол жақ пернесі үшін reversePathBST рекурсивті шақырыңыз, содан кейін түбір мәнін кезектің алдындағы элементпен ауыстырыңыз. Сонымен қатар, кезектің алдыңғы жағындағы элементті алып тастаңыз.
  4. Басқасы түбірдің мәнін кезекке итермелейді, түбірдің оң баласы үшін рекурсивті түрде reversePathBST шақырады, содан кейін түбір мәнін кезектің алдыңғы жағында орналасқан элементпен ауыстырады. Сонымен қатар, кезектің алдыңғы жағындағы элементті алып тастаңыз.

Кезекті пайдалану арқылы BST жолды кері бұруға арналған JAVA коды

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 ++ кодын кезекті пайдаланып BST-де кері жолға арналған код

#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

Күрделілікті талдау

Уақыттың күрделілігі = O (журнал n)
Ғарыштың күрделілігі = O (журнал n)
мұндағы n - екілік іздеу ағашындағы түйіндер саны.

Әдебиеттер тізімі