BST را از سطح Level Order Traversal خود بسازید  


سطح دشواری ساده
اغلب در آمازون سیب GE بهداشت و درمان MetLife مایکروسافت UHG Optum Yelp
درخت جستجوی دودویی درخت باینری عرض اول جستجو درخت عبور از درخت

با توجه به پیمایش سفارش سطح از یک درخت جستجوی دودویی ، یک الگوریتم برای ساخت درخت جستجوی دودویی یا BST از سطح مرتب سازی داده شده ITS بنویسید.

مثال  

ورودی
levelOrder [] = {18 ، 12 ، 20 ، 8 ، 15 ، 25 ، 5 ، 9 ، 22 ، 31}
تولید

BST را از سطح Level Order Traversal خود بسازیدسنجاق

سفارش: 5 8 9 12 15 18 20 22 25 31

ورودی
سطح سطح [] = {4 ، 2 ، 5 ، 1 ، 3 ، 6}
تولید

BST را از سطح Level Order Traversal خود بسازیدسنجاق

به ترتیب: 1 2 3 4 5 6

الگوریتم ساخت BST از پیمایش مرتبه سطح  

اولین عنصر در پیمایش مرتبه سطح همیشه ریشه جستجوی دودویی را تشکیل می دهد درخت. مقدار بعدی بسته به مقدار آن ممکن است گره سمت چپ یا گره راست را تشکیل دهد.

اگر گره بعدی کوچکتر از ریشه باشد ، در سمت چپ ریشه وارد می شود ، در غیر این صورت در سمت راست قرار می گیرد.
ایده به شرح زیر است ، اگر ریشه BST تهی است ، عنصر فعلی کوچکتر از ریشه است ، سپس آن را در موقعیت مناسب در زیر درخت سمت چپ ریشه قرار دهید ، در غیر این صورت موقعیت نامناسب را در زیر درخت راست قرار دهید ریشه

  1. ریشه BST را به صورت null آغاز کنید. اگر هیچ عنصری در سطح عبور از سطح وجود ندارد ، ریشه را برگردانید.
  2. برای هر عنصر در آرایه levelOrder ، مراحل 3 ، 4 و 5 را تکرار کنید.
  3. اگر ریشه تهی است ، عنصر فعلی را به عنوان ریشه ایجاد کنید.
  4. در غیر این صورت اگر عنصر فعلی کمتر از root باشد ، به مرحله 3 بروید ، ریشه root می شود. چپ می شود و عنصر ثابت می ماند.
  5. اگر عنصر فعلی از ریشه بیشتر باشد ، به مرحله 3 بروید ، ریشه ریشه می شود. درست است و عنصر ثابت می ماند.
  6. ریشه را برگردانید.
همچنین مشاهده کنید
یک روش جالب برای تولید اعداد دودویی از 1 تا n

کد JAVA برای ساخت BST از پیمایش سفارش سطح  

public class ConstructBSTFromItsGivenLevelOrderTraversal {
    // 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 in order traversal 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 attachNode(Node root, int value) {
        // if root is null, make the current element as root
        if (root == null) {
            root = new Node(value);
            return root;
        }

        // if element is less than root
        if (value < root.data) {
            // attach it to left subtree
            root.left = attachNode(root.left, value);
        } else {
            // attach it to right subtree
            root.right = attachNode(root.right, value);
        }

        // return root
        return root;
    }

    private static Node formBST(int[] levelOrder) {
        // initialize root as null
        Node root = null;

        // for each element attach the node to required position in the BST
        for (int i = 0; i < levelOrder.length; i++) {
            // Step 3 to 5
            root = attachNode(root, levelOrder[i]);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int levelOrder1[] = new int[] {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
        Node root1 = formBST(levelOrder1);
        inorder(root1);
        System.out.println();

        // Example 2
        int levelOrder2[] = new int[] {4, 2, 5, 1, 3, 6};
        Node root2 = formBST(levelOrder2);
        inorder(root2);
        System.out.println();
    }
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

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* attachNode(Node *root, int value) {
    // if root is null, make the current element as root
    if (root == NULL) {
        root = new Node(value);
        return root;
    }
    
    // if element is less than root
    if (value < root->data) {
        // attach it to left subtree
        root->left = attachNode(root->left, value);
    } else {
        // attach it to right subtree
        root->right = attachNode(root->right, value);
    }
    
    // return root
    return root;
}

Node* formBST(int *levelOrder, int n) {
    // initialize root as null
    Node *root = NULL;
    
    // for each element attach the node to required position in the BST
    for (int i = 0; i < n; i++) {
        // Step 3 to 5
        root = attachNode(root, levelOrder[i]);
    }
    
    // return root
    return root;
}

int main() { 
    // Example 1
    int levelOrder1[] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
    Node *root1 = formBST(levelOrder1, sizeof(levelOrder1) / sizeof(levelOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int levelOrder2[] = {4, 2, 5, 1, 3, 6};
    Node *root2 = formBST(levelOrder2, sizeof(levelOrder2) / sizeof(levelOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0; 
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

تحلیل پیچیدگی  

پیچیدگی زمان = بر2)
پیچیدگی فضا = O (N)، به دلیل بازگشت
كه n تعداد كل عناصر در تراز سطح است صف.

همچنین مشاهده کنید
جستجوی باینری و جستجوی درخت

مرجع1     مرجع 2