Пабудаваць BST з зададзенага папярэдняга абходу


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка
Двайковае дрэва пошуку Двайковае дрэва Стэк дрэва Абход дрэва

З улікам папярэдняга заказу дрэва двайковага пошуку (BST), напішыце алгарытм пабудовы BST з зададзенага абход папярэдняга заказу.

Прыкладаў

уваход  
папярэдні заказ [] = {7, 5, 3, 6, 9}
выхад

Пабудаваць BST з зададзенага папярэдняга абходу

Унутры: 3 5 6 7 9

уваход
папярэдні заказ [] = {12, 6, 1, 35, 20}
выхад

Пабудаваць BST з зададзенага папярэдняга абходу

Унутры: 1 6 12 20 35

Наіўны падыход

Мы бачым, што першы элемент у абходцы папярэдняга заказу - гэта заўсёды корань дрэва а астатнія элементы з'яўляюцца часткай левага і правага дрэва. Паколькі дрэва з'яўляецца BST, так усе элементы, меншыя за корань, прысутнічаюць у левым дрэве, а элементы, большыя за корань, у правым дрэве.

Такім чынам, мы пераходзім па дадзеным масіве і знаходзім першы элемент, большы за корань. Цяпер элементы перад гэтым элементам (за выключэннем кораня) - гэта абход левага паддрэва папярэдняга заказу, а элементы пасля гэтага элемента (уключаны) - абход правага паддрэва папярэдняга заказу.

Такім чынам, першы элемент утварае корань BST, элементы ад індэкса 1 да (i - 1) утвараюць левае паддрэва, а элементы ад індэкса i да (n - 1) - правае паддрэва.

createBST (папярэдні заказ, нізкі, высокі)

  1. Першым элементам (preOrder [low]) у масіве з'яўляецца корань BST. Калі нізкі роўны высокаму, вяртайце корань.
  2. Перавядзіце масіў ад індэкса нізкі + 1 (індэксацыя на аснове 0) да высокага і знайдзіце першы элемент, большы за корань, хай яго індэкс будзе i.
  3. Рэкурсіўна выклічце гэты метад для элементаў ад індэкса (нізкі + 1) да (i - 1) і прызначце BST, сфармаваны злева ад кораня.
  4. Рэкурсіўна выклікаць гэты метад для элементаў ад індэкса i да высокага і прызначыць BST, сфармаваны справа ад кораня.
  5. Вярнуць корань.

Складанасць часу = О (н2)
Складанасць прасторы = Аб (п), з-за рэкурсіі
дзе n - памер дадзенага масіва папярэдняга заказу.

Код JAVA для пабудовы BST з дадзенага папярэдняга абходу

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

Код C ++ для пабудовы BST з дадзенага папярэдняга абходу

#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 з зададзенага папярэдняга абходу

Аптымальнай ідэяй з'яўляецца выкарыстанне хітрасці дыяпазону, гэта значыць, мы ўсталёўваем дыяпазон для ўсіх вузлоў, вузел, які ўваходзіць у дыяпазон, утварае корань дрэва.

Першапачаткова дыяпазон складае -бесканечнасць (мін) і + бясконцасць (макс), таму ў дыяпазон уваходзіць першы корань, які ўтварае корань. Затым мы выклікаем той самы метад для левага даччынага элемента (абноўлены дыяпазон - ад мін да значэння кораня) і для правага даччынага дзіцяці (абноўлены дыяпазон ад значэння каранёвага да максімальнага).

createBST (мін, макс)

  1. Калі значэнне элемента ў currIndex (глабальна вызначана) знаходзіцца паміж min і max (абодва не ўключаны), то ён утварае корань. Вылучыце памяць і стварыце новы вузел з імем root. У іншым выпадку перайдзіце да кроку 4.
  2. Павялічце currIndex і рэкурсіўна выклічце гэты метад, каб сфармаваць левае паддрэва як, constructBST (min, значэнне кораня).
  3. Рэкурсіўна выклікаем гэты метад, каб сфармаваць правільнае паддрэва як, constructBST (значэнне кораня, макс.).
  4. Вярнуць корань.

Складанасць часу = Аб (п)
Складанасць прасторы = Аб (п)
дзе n - памер масіва папярэдняга заказу.

Код JAVA для пабудовы BST з дадзенага папярэдняга абходу

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

Код C ++ для пабудовы BST з дадзенага папярэдняга абходу

#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) і для кожнага элемента, у той час як бягучы элемент большы, чым верхняя частка стэка, выскоквае верхні і захоўваецца ў зменнай з імем temp.
  3. Калі temp роўны нулю (гэта значыць бягучы элемент быў меншым за верхнюю частку стэка), зрабіце temp верхняй часткай стэка і бягучым элементам злева ад temp і націсніце бягучы элемент у стэк.
  4. У іншым выпадку зрабіце бягучы элемент праваруч ад тэмпературы і націсніце бягучы элемент у стэк.
  5. Вярнуць корань.

Складанасць часу = Аб (п)
Складанасць прасторы = Аб (п)
дзе n - памер масіва папярэдняга заказу.

Код JAVA для пабудовы BST з дадзенага папярэдняга абходу

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

Код C ++ для пабудовы BST з дадзенага папярэдняга абходу

#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