ከተሰጠ ቅድመ-ትዕዛዝ ትራንስፖርት BST ን ይገንቡ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን
የሁለትዮሽ ፍለጋ ዛፍ ሁለትዮሽ ዛፍ ክምር ዛፍ የዛፍ ተሻጋሪ

የሁለትዮሽ ፍለጋ ዛፍ (ቢኤስኤስ) የቅድመ-ትዕዛዝ መሻገሪያ ከተሰጠ ፣ BST ን ከተሰጠበት ለመገንባት አልጎሪዝም ይፃፉ መተላለፍን ቀድመው.

ምሳሌዎች

ግቤት  
ቅድመ ትዕዛዝ [] = {7, 5, 3, 6, 9}
ዉጤት

ከተሰጠ ቅድመ-ትዕዛዝ ትራንስፖርት BST ን ይገንቡ

Inorder: 3 5 6 7 9

ግቤት
ቅድመ ትዕዛዝ [] = {12, 6, 1, 35, 20}
ዉጤት

ከተሰጠ ቅድመ-ትዕዛዝ ትራንስፖርት BST ን ይገንቡ

Inorder: 1 6 12 20 35

የዋህ አቀራረብ

በቅድመ-ትዕዛዙ መተላለፍ ውስጥ የመጀመሪያው ንጥረ ነገር ሁል ጊዜ የእሱ ሥር መሆኑን ማየት እንችላለን ዛፍ እና የተቀሩት ንጥረ ነገሮች የግራ እና የቀኝ ንዑስ-ዛፍ አካል ናቸው። ዛፉ BST እንደመሆኑ መጠን ከሥሩ ያነሱ ንጥረ ነገሮች በሙሉ በግራ ንዑስ ዛፍ ውስጥ ይገኛሉ ፣ እና ከሥሩ በላይ የሆኑ ንጥረ ነገሮች በቀኝ ንዑስ ዛፍ ውስጥ ይገኛሉ ፡፡

ስለዚህ በተሰጠው ድርድር ውስጥ ተሻግረን ከሥሩ የሚበልጥ የመጀመሪያውን ንጥረ ነገር እናገኛለን ፡፡ አሁን ከዚህ ንጥረ-ነገር በፊት ያሉት ንጥረ ነገሮች (ከሥሩ በስተቀር) የግራ ንዑስ ዛፍ ቅድመ-ቅየራ ነው እና ከዚህ ንጥረ ነገር በኋላ (አካትቶታል) የቀኝ ንዑስ-ዛፍ ቅድመ-ትዕዛዝ መተላለፍ ነው።

ስለዚህ ፣ የመጀመሪያው ንጥረ ነገር የ BST ሥርን ይመሰርታል ፣ ከጠቋሚ 1 እስከ (i - 1) ያሉ ንጥረ ነገሮች የግራ ንዑስ ዛፍ ይመሰርታሉ ፣ እና ከ ‹መረጃ ጠቋሚ› እስከ ‹n - 1› ያሉት ክፍሎች የቀኝ ንዑስ-ዛፍ ይመሰርታሉ ፡፡

ፍጠር BST (ቅድመ-ትዕዛዝ ፣ ዝቅተኛ ፣ ከፍተኛ)

  1. በድርድሩ ውስጥ የመጀመሪያው ንጥረ ነገር (ቅድመ-ትዕዛዝ (ዝቅተኛ)) የ BST ሥር ነው። ዝቅተኛ ከከፍተኛው ጋር እኩል ከሆነ ተመላሽ ሥሩ ፡፡
  2. ድርድርን ከጠቋሚ ዝቅተኛ + 1 (0 ላይ የተመሠረተ ጠቋሚ ማውጫ) ወደ ላይ ያቋርጡ እና ከሥሩ የሚበልጥ የመጀመሪያውን ንጥረ ነገር ያግኙ ፣ መረጃ ጠቋሚው እኔ ይሆናል።
  3. ይህንን መረጃ ከጠቋሚ (ዝቅተኛ + 1) እስከ (i - 1) ያሉትን አባሎች ደጋግመው ይደውሉ እና የተሰራውን BST ከስር ሥሩ በስተግራ ይመድቡ ፡፡
  4. ከ ‹ኢንዴክስ i እስከ ከፍተኛ› ለሚገኙ ንጥረ ነገሮች ይህንን ዘዴ ደጋግመው ይደውሉ እና ከሥሩ በስተቀኝ የተሠራውን BST ይመድቡ ፡፡
  5. ተመለስ ሥር.

የጊዜ ውስብስብነት = ኦ (n2)
የቦታ ውስብስብነት = ሆይ (n), በድጋሜ ምክንያት
የተሰጠው የቅድመ ዝግጅት ድርድር መጠን n ነው።

የ ‹BA› ግንባታ የ‹ JAVA ›ኮድ ከተሰጠ ቅድመ-ትዕዛዝ ማስተላለፍ

public class ConstructBSTFromGivenPreorderTraversal {
    // class representing Node of BST
    static class Node {
        int data;
        Node left, right;

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

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

    private static Node createBST(int[] preOrder, int low, int high) {
        // if there is only 1 node in the tree, this is root, return it
        if (low == high) {
            return new Node(preOrder[low]);
        }

        // the first node is the root of the BST
        Node root = new Node(preOrder[low]);

        // find the index of first element greater than root
        int index = -1;
        for (int i = low + 1; i <= high; i++) {
            if (preOrder[i] > preOrder[low]) {
                index = i;
                break;
            }
        }

        // if all the elements are smaller than root, they forms the left subtree
        // and right subtree is null
        if (index == -1) {
            root.left = createBST(preOrder, low + 1, high);
            root.right = null;
        }
        // else elements from index (low + 1) to (index - 1) forms  the left subtree
        // and elements from index 'index' to high forms the right subtree
        else {
            root.left = createBST(preOrder, low + 1, index - 1);
            root.right = createBST(preOrder, index, high);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int preOrder1[] = new int[] {7, 5, 3, 6, 9};
        Node root1 = createBST(preOrder1, 0, preOrder1.length - 1);
        inorder(root1);
        System.out.println();

        // Example 2
        int preOrder2[] = new int[] {12, 6, 1, 35, 20};
        Node root2 = createBST(preOrder2, 0, preOrder2.length - 1);
        inorder(root2);
        System.out.println();
    }
}
3 5 6 7 9 
1 6 12 20 35

ከተሰጠ የፕሪደር ትራቨርቫል BST ን ለመገንባት C ++ ኮድ

#include <iostream> 
#include<vector> 
#include<queue> 
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; 
    } 
}; 

// function to print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* createBST(int *preOrder, int low, int high) {
    // if there is only 1 node in the tree, this is root, return it
    if (low == high) {
        return new Node(preOrder[low]);
    }
    
    // the first node is the root of the BST
    Node *root = new Node(preOrder[low]);
    
    // find the index of first element greater than root
    int index = -1;
    for (int i = low + 1; i <=high; i++) {
        if (preOrder[i] > preOrder[low]) {
            index = i;
            break;
        }
    }
    
    // if all the elements are smaller than root, they forms the left subtree
    // and right subtree is null
    if (index == -1) {
        root->left = createBST(preOrder, low + 1, high);
        root->right = NULL;
    }
    // else elements from index (low + 1) to (index - 1) forms  the left subtree
    // and elements from index 'index' to high forms the right subtree
    else {
        root->left = createBST(preOrder, low + 1, index - 1);
        root->right = createBST(preOrder, index, high);
    }
    
    // return root
    return root;
}

int main() {
    // Example 1
    int preOrder1[] = {7, 5, 3, 6, 9};
    Node *root1 = createBST(preOrder1, 0, (sizeof(preOrder1) / sizeof(preOrder1[0])) - 1);
    inOrder(root1);
    cout<<endl;

    // Example 2
    int preOrder2[] = {12, 6, 1, 35, 20};
    Node *root2 = createBST(preOrder2, 0, (sizeof(preOrder2) / sizeof(preOrder2[0])) - 1);
    inOrder(root2);
    cout<<endl;
    
    return 0;
}
3 5 6 7 9 
1 6 12 20 35

የተመቻቸ አቀራረብ

ከተሰጠ ቅድመ-ቅደም ተከተል ትራንስፖርት BST ን ለመገንባት ተደጋጋሚ ዘዴ

እዚህ የተሻለው ሀሳብ የክልል ብልሃትን መጠቀም ነው ፣ ማለትም ፣ ለሁሉም አንጓዎች ወሰን እናዘጋጃለን ፣ በክልሉ ውስጥ የሚመጣው መስቀለኛ መንገድ የዛፉ ሥር ይሠራል ፡፡

በመጀመሪያ ፣ ክልሉ - -የመጨረሻ (ደቂቃ) እና + infinity (ቢበዛ) ነው ፣ ስለሆነም የመጀመሪያው ሥሩ በክልሉ ውስጥ ይመጣልና ሥሩ ይሠራል ፡፡ ከዚያ ለግራ ልጅ አንድ አይነት ዘዴ እንጠራዋለን (የዘመነው ክልል ከደቂቃ እስከ ስሩ እሴት ነው) እና ለትክክለኛው ልጅ (የዘመነ ክልል ከሥሩ እሴት እስከ ከፍተኛ ነው) ፡፡

ፍጠር BST (ደቂቃ ፣ ከፍተኛ)

  1. በ currIndex (በዓለም አቀፍ ደረጃ የተገለጸ) የንጥል እሴት በደቂቃ እና በከፍተኛው መካከል ከሆነ (ሁለቱም አልተካተቱም) ፣ ከዚያ ስር ይመሰርታል። ማህደረ ትውስታን ይመድቡ እና ስር የተሰየመ አዲስ መስቀለኛ መንገድ ይፍጠሩ። ሌላ ወደ ደረጃ 4 ይዝለሉ ፡፡
  2. የ currIndex ን ጭማሪ እና እንደገና ይህንን ዘዴ የግራ ንዑስ-ዛፍ ለመፍጠር ፣ BST ን ለመገንባት (ደቂቃ ፣ የስር እሴት)።
  3. ትክክለኛውን ንዑስ ደረጃን ለመመስረት ይህንን ዘዴ በተደጋጋሚ ይደውሉ BST (የስር እሴት ፣ ከፍተኛ)።
  4. ተመለስ ሥር.

የጊዜ ውስብስብነት = ሆይ (n)
የቦታ ውስብስብነት = ሆይ (n)
የ n የቅድመ-ትዕዛዝ ድርድር መጠን የት ነው?

የ ‹BA› ግንባታ የ‹ JAVA ›ኮድ ከተሰጠ ቅድመ-ትዕዛዝ ማስተላለፍ

public class ConstructBSTFromGivenPreorderTraversal {
    // class representing Node of BST
    static class Node {
        int data;
        Node left, right;

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

    // globally defined currIndex integer
    private static int currIndex = 0;

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

    private static Node createBST(int[] preOrder, int min, int max) {
        if (currIndex >= preOrder.length) {
            return null;
        }

        Node root = null;

        // if current element is in between min and max
        if (preOrder[currIndex] > min && preOrder[currIndex] < max) {
            // allocate memory for it
            root = new Node(preOrder[currIndex]);
            // increment currIndex
            currIndex++;
            // make left of root as createBST(min, root's data)
            root.left = createBST(preOrder, min, root.data);
            // make right of root as createBST(root's data, max)
            root.right = createBST(preOrder, root.data, max);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int preOrder1[] = new int[] {7, 5, 3, 6, 9};
        currIndex = 0;
        Node root1 = createBST(preOrder1, Integer.MIN_VALUE, Integer.MAX_VALUE);
        inorder(root1);
        System.out.println();

        // Example 2
        int preOrder2[] = new int[] {12, 6, 1, 35, 20};
        currIndex = 0;
        Node root2 = createBST(preOrder2, Integer.MIN_VALUE, Integer.MAX_VALUE);
        inorder(root2);
        System.out.println();
    }
}
3 5 6 7 9 
1 6 12 20 35

ከተሰጠ የፕሪደር ትራቨርቫል BST ን ለመገንባት 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; 
    } 
}; 

// globally defined currIndex integer
int currIndex = 0;

// function to print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* createBST(int *preOrder, int min, int max, int n) {
    if (currIndex >= n) {
        return NULL;
    }
    
    Node *root = NULL;
    
    // if current element is in between min and max
    if (preOrder[currIndex] > min && preOrder[currIndex] < max) {
        // allocate memory for it
        root = new Node(preOrder[currIndex]);
        // increment currIndex
        currIndex++;
        // make left of root as createBST(min, root's data)
        root->left = createBST(preOrder, min, root->data, n);
        // make right of root as createBST(root's data, max)
        root->right = createBST(preOrder, root->data, max, n);
    }
    
    // return root
    return root;
}

int main() {
    // Example 1
    int preOrder1[] = {7, 5, 3, 6, 9};
    currIndex = 0;
    Node *root1 = createBST(preOrder1, INT_MIN, INT_MAX, sizeof(preOrder1) / sizeof(preOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int preOrder2[] = {12, 6, 1, 35, 20};
    currIndex = 0;
    Node *root2 = createBST(preOrder2, INT_MIN, INT_MAX, sizeof(preOrder2) / sizeof(preOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0;
}
3 5 6 7 9 
1 6 12 20 35

ምሳሌያዊ ዘዴ

እዚህ እኛ አንድ እንጠቀማለን ቁልል መመለሻውን ለመቁረጥ እና ተስማሚውን አቀራረብ ወደ ተለዋዋጭ ኮድ ለመቀየር ፡፡

  1. የመጀመሪያው አንጓ የ BST ሥር ነው ፣ ስለሆነም ሥሩን እንደ መጀመሪያ አንጓ ያድርጉት እና ወደ ቁልል ይግፉት ፡፡
  2. ቅድመ-ትዕዛዙን ያቋርጡ ደርድር ከኤንዴክስ 1 (0 ላይ የተመሠረተ ኢንዴክስ) እና ለእያንዳንዱ ንጥረ ነገር ፣ የአሁኑ ንጥረ ነገር ከላይ ከሚወጣው ቁልል ይበልጣል እና ከላይ በተጠቀሰው ተለዋዋጭ ቴምፕ ውስጥ ያከማቹ ፡፡
  3. ቴምፕዩቱ ዋጋ ቢስ ከሆነ (ያ የአሁኑ ንጥረ ነገር ከተደራራቢው አናት ያነሰ ነበር) ፣ ቴምፕ እንደ ቁልል አናት እና እንደ ቴምፕስ ግራ የአሁኑን አካል ያድርጉ እና የአሁኑን ንጥረ ነገር ወደ ቁልቁል ይግፉት ፡፡
  4. ሌላውን የአሁኑን ንጥረ ነገር እንደ ቴምብር መብት አድርገው የአሁኑን ንጥረ ነገር ወደ ቁልቁል ይግፉት ፡፡
  5. ተመለስ ሥር.

የጊዜ ውስብስብነት = ሆይ (n)
የቦታ ውስብስብነት = ሆይ (n)
የ n የቅድመ-ትዕዛዝ ድርድር መጠን የት ነው?

የ ‹BA› ግንባታ የ‹ JAVA ›ኮድ ከተሰጠ ቅድመ-ትዕዛዝ ማስተላለፍ

import java.util.Stack;

public class ConstructBSTFromGivenPreorderTraversal {
    // class representing Node of a Binary Tree
    static class Node {
        int data;
        Node left, right;

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

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

    private static Node createBST(int[] preOrder) {
        // the first element is the root of BST
        Node root = new Node(preOrder[0]);
        // create a stack and push root to it
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        // traverse the array from index 1
        for (int i = 1; i < preOrder.length; i++) {
            // initialize temp as null
            Node temp = null;

            // while current element is greater than top of stack
            // remove top of stack and store it in temp
            while (!stack.isEmpty() && preOrder[i] > stack.peek().data) {
                temp = stack.pop();
            }

            // if temp is null
            if (temp == null) {
                // make temp as top of stack
                temp = stack.peek();
                // current element is left of temp
                temp.left = new Node(preOrder[i]);
                // add current element to stack
                stack.push(temp.left);
            } else {
                // current element is right of temp
                temp.right = new Node(preOrder[i]);
                // add current element to the stack
                stack.push(temp.right);
            }
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int preOrder1[] = new int[] {7, 5, 3, 6, 9};
        Node root1 = createBST(preOrder1);
        inorder(root1);
        System.out.println();

        // Example 2
        int preOrder2[] = new int[] {12, 6, 1, 35, 20};
        Node root2 = createBST(preOrder2);
        inorder(root2);
        System.out.println();
    }
}
3 5 6 7 9 
1 6 12 20 35

ከተሰጠ የፕሪደር ትራቨርቫል BST ን ለመገንባት 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; 
    } 
};

// function to print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* createBST(int *preOrder, int n) {
    // the first element is the root of BST
    Node *root = new Node(preOrder[0]);
    // create a stack and push root to it
    stack<Node*> st;
    st.push(root);
    
    // traverse the array from index 1
    for (int i = 1; i < n; i++) {
        // initialize temp as null
        Node *temp = NULL;
        
        // while current element is greater than top of stack
        // remove top of stack and store it in temp
        while (!st.empty() && preOrder[i] > st.top()->data) {
            temp = st.top();
            st.pop();
        }
        
        // if temp is null
        if (temp == NULL) {
            // make temp as top of stack
            temp = st.top();
            // current element is left of temp
            temp->left = new Node(preOrder[i]);
            // add current element to stack
            st.push(temp->left);
        } else {
            // current element is right of temp
            temp->right = new Node(preOrder[i]);
            // add current element to the stack
            st.push(temp->right);
        }
    }
    
    // return root
    return root;
}

int main() {
    // Example 1
    int preOrder1[] = {7, 5, 3, 6, 9};
    Node *root1 = createBST(preOrder1, sizeof(preOrder1) / sizeof(preOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int preOrder2[] = {12, 6, 1, 35, 20};
    Node *root2 = createBST(preOrder2, sizeof(preOrder2) / sizeof(preOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0;
}
3 5 6 7 9 
1 6 12 20 35

ማጣቀሻ1    ማጣቀሻ 2