Өгөгдсөн Preorder Traversal-ээс BST байгуулна


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны
Хоёртын хайлтын мод Хоёртын мод Stack Мод Мод хөндлөн гарах

Хоёртын хайлтын модны урьдчилсан захиалгын дагуу өгөгдсөн өгөгдлөөс BST-ийг байгуулах алгоритмыг бич. урьдчилсан захиалга.

жишээ нь

Оролт  
урьдчилсан захиалга [] = {7, 5, 3, 6, 9}
гаралтын

Өгөгдсөн Preorder Traversal-ээс BST байгуулна

Захиалга: 3 5 6 7 9

Оролт
урьдчилсан захиалга [] = {12, 6, 1, 35, 20}
гаралтын

Өгөгдсөн Preorder Traversal-ээс BST байгуулна

Захиалга: 1 6 12 20 35

Гэнэн хандлага

Урьдчилан захиалах дамжуулалтын эхний элемент нь үргэлж язгуурын үндэс болохыг бид харж болно мод үлдсэн элементүүд нь зүүн ба баруун дэд модны хэсэг юм. Мод нь BST тул root-ээс бага бүх элементүүд зүүн дэд модонд, харин root-ээс их элементүүд баруун дэд модонд байдаг.

Тиймээс бид өгөгдсөн массивыг дайран гарч, язгуураас илүү эхний элементийг олно. Одоо энэ элементийн өмнөх элементүүд (үндэсээс бусад) зүүн дэд модны урьдчилсан захиалга бөгөөд энэ элементийн дараахь элементүүд (үүнд багтсан болно) баруун дэд модны урьдчилсан захиалга юм.

Тиймээс эхний элемент нь BST-ийн үндэс, 1-ээс (i - 1) хүртэлх элементүүд зүүн дэд модыг, i-ээс (n - 1) хүртэлх элементүүд баруун дэд модыг бүрдүүлдэг.

createBST (урьдчилсан захиалга, бага, өндөр)

  1. Массив дахь эхний элемент (preOrder [low]) нь BST-ийн үндэс юм. Хэрэв бага нь өндөртэй тэнцвэл root-г буцаана.
  2. Массивыг индекс бага + 1 (0-д суурилсан индексжүүлэлт) -ээс өндөр хүртэл дайрч, эхний элементийг язгуураас их хэмжээгээр олоорой, түүний индекс нь i байг.
  3. Энэ аргыг индекс (бага + 1) -ээс (i - 1) хүртэлх элементүүдийн хувьд рекурсив байдлаар дуудаж, root-ийн зүүн талд үүссэн BST-ийг оноож өгнө.
  4. I индексээс өндөр хүртэлх элементүүдийн хувьд энэ аргыг рекурсив байдлаар дуудаж root-ийн баруун талд үүссэн BST-ийг хуваарилна.
  5. Буцах үндэс.

Цаг хугацааны нарийн төвөгтэй байдал = O (n2)
Сансрын нарийн төвөгтэй байдал = O (N), рекурсын улмаас
энд n нь өгөгдсөн урьдчилсан захиалгын массивын хэмжээ юм.

Өгөгдсөн Preorder Traversal-ээс BST барих 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

Өгөгдсөн Preorder Traversal-ээс 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

Оновчтой арга

Өгөгдсөн Preorder Traversal-ээс BST барих рекурсив арга

Энд хамгийн оновчтой санаа бол хүрээний заль мэхийг ашиглах явдал юм, өөрөөр хэлбэл бид бүх зангилаануудад хүрээ тохируулах болно, мужид орсон зангилаа нь модны үндэс болдог.

Эхэндээ муж нь хязгааргүй (мин) ба + хязгааргүй (хамгийн их) гэсэн утгатай тул эхний үндэс нь муж дотор орж үндэс үүсгэдэг. Дараа нь бид ижил аргыг зүүн хүүхдэд (шинэчлэгдсэн хүрээ нь минээс язгуурын утга хүртэл) ба баруун хүүхдэд (шинэчилсэн муж нь root-ийн утгааас макс хүртэл) дууддаг.

createBST (мин, хамгийн их)

  1. Хэрэв currIndex дээрх элементийн утга (дэлхийн хэмжээнд тодорхойлогдсон) min ба max хооронд байвал (хоёулаа ороогүй болно), энэ нь үндэс болно. Санах ойг хуваарилж root нэртэй шинэ зангилаа үүсгээрэй. Бусад 4-р алхам руу үсрэх.
  2. CurrIndex-ийг нэмэгдүүлж, рекурсив хэлбэрээр зүүн дэд модыг үүсгэхийн тулд constructBST (min, root-ийн утга) болгоно.
  3. Энэ аргыг рекурсиваар дуудаж зөв дэд модыг байгуулна уу, constructBST (root-ийн утга, max).
  4. Буцах үндэс.

Цаг хугацааны нарийн төвөгтэй байдал = O (N)
Сансрын нарийн төвөгтэй байдал = O (N)
энд n нь урьдчилсан захиалгын массивын хэмжээ юм.

Өгөгдсөн Preorder Traversal-ээс BST барих 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

Өгөгдсөн Preorder Traversal-ээс 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

Давтан арга

Энд бид a стек рекурсийг бууруулж, оновчтой хандлагыг давталтын код болгон хөрвүүлэх.

  1. Эхний зангилаа нь BST-ийн үндэс тул root-ийг эхний зангилаа болгоод стек рүү түлхэж өгнө.
  2. Урьдчилсан захиалгыг хөндлөн гаргана уу массив индекс 1-ээс (0-д суурилсан индексжүүлэлт) ба элемент бүрийн хувьд, харин одоогийн элемент нь стекийн дээд хэсгээс их байвал дээд хэсгийг гарч ирэн temp гэсэн хувьсагчид хадгална.
  3. Хэрэв түрэмгий хоосон байвал (энэ нь одоогийн элемент нь стекийн дээд хэсгээс бага байсан бол), temp-ийг стекийн дээд хэсэг, temp-ээс зүүн хэсэгт хийж, одоогийн элементийг стек рүү түлхэж өгнө.
  4. Бусад нь одоогийн элементийг түр зуурын эрх болгож, одоогийн элементийг стек рүү түлхэж өгнө.
  5. Буцах үндэс.

Цаг хугацааны нарийн төвөгтэй байдал = O (N)
Сансрын нарийн төвөгтэй байдал = O (N)
энд n нь урьдчилсан захиалгын массивын хэмжээ юм.

Өгөгдсөн Preorder Traversal-ээс BST барих 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

Өгөгдсөн Preorder Traversal-ээс 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