በሁለትዮሽ ፍለጋ ዛፍ ውስጥ መስቀለኛውን ከአነስተኛ እሴት ጋር ያግኙ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ብሉምበርግ የ Microsoft
የሁለትዮሽ ፍለጋ ዛፍ ሁለትዮሽ ዛፍ ስፌት የመጀመሪያ ፍለጋ ተራ ዛፍ

የሁለትዮሽ ፍለጋ ዛፍ ከተሰጠ ፣ በተሰጠው የሁለትዮሽ ፍለጋ ውስጥ አነስተኛውን እሴት ያለው መስቀለኛ መንገድ ለማግኘት ስልተ ቀመር ይጻፉ ዛፍ.

ለምሳሌ

ግቤት

በሁለትዮሽ ፍለጋ ዛፍ ውስጥ መስቀለኛውን ከአነስተኛ እሴት ጋር ያግኙ

ዉጤት
5

የዋህ አቀራረብ

ቀለል ያለ አቀራረብ የዛፍ ተሻጋሪ ማድረግ እና መስቀለኛ መንገዱን በሁሉም መስቀለኛ መንገዶች መካከል ካለው አነስተኛ እሴት ጋር ማግኘት ነው ፡፡ ይህ ዘዴ ለሁለትዮሽ ፍለጋ ዛፍ ብቻ ሳይሆን ለማንኛውም አጠቃላይ ዛፍም ይሠራል ፡፡
አንድ እናደርጋለን እንበል ደረጃ-ትዕዛዝ መተላለፍ አነስተኛውን እሴት ለማግኘት ፡፡

  1. ሥሩ ዋጋ ቢስ ከሆነ ዝቅተኛው እሴት የለም ፣ መመለስ ስፍር ቁጥር የለውም ፡፡
  2. አነስተኛውን እሴት ያስጀምሩ ማለቂያ የለውም ፡፡
  3. ወረፋ ይፍጠሩ እና ሥሩን ወደ እሱ ይግፉት ፡፡ ወረፋው ባዶ በማይሆንበት ጊዜ ደረጃ 4 ን ይድገሙ።
  4. አንድ መስቀለኛ መንገድ ከወረፋው ላይ ያስወግዱ ፣ አነስተኛውን እሴት እንደ ዝቅተኛ እሴት እና የአሁኑን መስቀለኛ ዋጋ ያዘምኑ። የአሁኑን መስቀለኛ መንገድ ልጆችን ወደ ወረፋው ይግፉ ፡፡
  5. ዝቅተኛውን እሴት ይመልሱ።

የጊዜ ውስብስብነት = ሆይ (n)
የቦታ ውስብስብነት = ሆይ (n)
በተጠቀሰው BST ውስጥ የአንጓዎች ጠቅላላ ቁጥር የት ነው ፡፡

መስቀለኛውን በአነስተኛ እሴት ለማግኘት የጃቫ ቪ ኮድ

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

public class FindTheNodeWithMinimumValueInABinarySearchTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

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

    private static int minValue(Node root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        // initialize min as infinite
        int min = Integer.MAX_VALUE;

        // do a level order traversal of the tree
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            // update minimum
            min = Math.min(min, curr.data);

            // add children of curr to queue
            if (curr.left != null)
                queue.add(curr.left);
            if (curr.right != null)
                queue.add(curr.right);
        }

        return min;
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(18);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.right.left = new Node(27);
        root.right.right = new Node(33);
        root.left.left.right = new Node(11);

        System.out.println(minValue(root));
    }
}
5

መስቀለኛውን በአነስተኛ እሴት ለማግኘት C + + ኮድ

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

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

int minValue(Node *root) {
    if (root == NULL) {
        return INT_MAX;
    }
    
    // initialize min as infinite
    int min = INT_MAX;
    
    // do a level order traversal of the tree
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        Node *curr = q.front();
        q.pop();
        
        // update minimum
        min = std::min(min, curr->data);
        
        // add children of curr to queue
        if (curr->left != NULL)
            q.push(curr->left);
        if (curr->right != NULL)
            q.push(curr->right);
    }
    
    return min;
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(18);
    root->right = new Node(30);
    root->left->left = new Node(5);
    root->right->left = new Node(27);
    root->right->right = new Node(33);
    root->left->left->right = new Node(11);

    cout<<minValue(root)<<endl;
    
    return 0;
}
5

የተመቻቸ አቀራረብ

የተሰጠው የሁለትዮሽ ዛፍ ሁለትዮሽ ፍለጋ ዛፍ ነው። የሁለትዮሽ ፍለጋ ዛፍ ከአንድ ኖድ ያነሱ ሁሉም አንጓዎች በግራ ንዑስ-ዛፉ ውስጥ የሚገኙበት እና ከዚህ ኖድ የሚበልጡ ሁሉም አንጓዎች በቀኝ ንዑስ ዛፍ ውስጥ የሚገኙበት ልዩ ንብረት አለው ፡፡
ይህንን ንብረት በመጠቀም አነስተኛ እሴት ያለው መስቀለኛ መንገድ በዛፉ ውስጥ እንደ ግራው መስቀለኛ ክፍል ይገኛል ማለት እንችላለን ፡፡

  1. ሥሩ ከንቱ ከሆነ ዝቅተኛው የለም ፣ ወሰን የለውም ይመለሱ።
  2. ሌላ ጊዜ ቴም እንደ መነሻ ያስጀምሩ ፡፡ የቴምፕ ግራ አንጓ የማይረባ ሆኖ ሳለ ደረጃ 3 ን ይድገሙ።
  3. ከቴምፕ ግራንት እኩል ያድርጉ ፡፡
  4. በዚህ ጊዜ ቴምፕ ወደ ግራው መስቀለኛ መንገድ ይጠቁማል ፣ ማለትም ዝቅተኛው እሴት ካለው መስቀለኛ መንገድ ነው ፡፡ የቴምፕ ውሂብን ይመልሱ።

የጊዜ ውስብስብነት = ኦ (ሸ)
የቦታ ውስብስብነት = ኦ (1)
የት የተሰጠው የሁለትዮሽ ፍለጋ ዛፍ ቁመት ሲሆን ፣ በጣም በከፋ ሁኔታ h ከ n ጋር እኩል ይሆናል (የአንጓዎች ብዛት)።

መስቀለኛውን በአነስተኛ እሴት ለማግኘት የጃቫ ቪ ኮድ

public class FindTheNodeWithMinimumValueInABinarySearchTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

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

    private static int minValue(Node root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        // initialize temp as root
        Node temp = root;
        // go to the left most node
        while (temp.left != null) {
            temp = temp.left;
        }

        // return value of left most node
        return temp.data;
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(18);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.right.left = new Node(27);
        root.right.right = new Node(33);
        root.left.left.right = new Node(11);

        System.out.println(minValue(root));
    }
}
5

መስቀለኛውን በአነስተኛ እሴት ለማግኘት C + + ኮድ

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

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

int minValue(Node *root) {
    if (root == NULL) {
        return INT_MAX;
    }
    
    // initialize temp as root
    Node *temp = root;
    // go to the left most node
    while (temp->left != NULL) {
        temp = temp->left;
    }
    
    // return value of left most node
    return temp->data;
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(18);
    root->right = new Node(30);
    root->left->left = new Node(5);
    root->right->left = new Node(27);
    root->right->right = new Node(33);
    root->left->left->right = new Node(11);

    cout<<minValue(root)<<endl;
    
    return 0;
}
5

ማጣቀሻዎች