Рубрики

Проверьте, может ли данный массив представлять уровень порядка обхода дерева двоичного поиска

Дан массив размером n . Проблема состоит в том, чтобы проверить, может ли данный массив представлять уровень обхода дерева двоичного поиска или нет.

Примеры:

Input : arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10}
Output : Yes
For the given arr[] the Binary Search Tree is:
         7        
       /    \       
      4     12      
     / \    /     
    3   6  8    
   /   /    \
  1   5     10

Input : arr[] = {11, 6, 13, 5, 12, 10}
Output : No
The given arr[] do not represent the level
order traversal of a BST.

Идея состоит в том, чтобы использовать структуру данных очереди. Каждый элемент очереди имеет структуру, скажем, NodeDetails, в которой хранятся детали узла дерева. Детали — это данные узла, а две переменные min и max, где min хранит нижний предел для значений узлов, которые могут быть частью левого поддерева, а max хранит верхний предел для значений узлов, которые могут быть частью правого поддерева. для указанного узла в структурной переменной NodeDetails . Для первого значения массива arr [0] создайте структуру NodeDetails, имеющую arr [0] в качестве данных узла и min = INT_MIN и max = INT_MAX. Добавьте эту структурную переменную в очередь. Этот узел будет корнем дерева. Перейдите ко 2-му элементу в arr [] и затем выполните следующие шаги:

  1. Pop NodeDetails из очереди в темп .
  2. Проверьте, может ли текущий элемент массива быть левым потомком узла в temp с помощью значений min и temp.data . Если это возможно, то создайте новую структуру NodeDetails для этого нового значения элемента массива с его правильными значениями 'min' и 'max' и поместите его в очередь и перейдите к следующему элементу в arr [].
  3. Проверьте, может ли текущий элемент массива быть правым потомком узла в temp с помощью значений max и temp.data . Если это возможно, то создайте новую структуру NodeDetails для этого нового значения элемента массива с его правильными значениями 'min' и 'max' и поместите его в очередь и перейдите к следующему элементу в arr [].
  4. Повторяйте шаги 1, 2 и 3 до тех пор, пока в arr [] не останется больше элементов или в очереди больше нет элементов.

Наконец, если все элементы массива были пройдены, то массив представляет собой обход уровня BST, иначе NOT.

C ++

// реализация C ++, чтобы проверить, является ли данный массив
// может представлять обход уровня двоичного
// Дерево поиска
#include <bits/stdc++.h>

  

using namespace std;

  
// для хранения деталей узла типа
// данные узла, 'min' и 'max' для получения
// диапазон значений где левый узел и
// правый ребенок должен лгать

struct NodeDetails

{

    int data;

    int min, max;

};

  
// функция для проверки наличия данного массива
// может представлять собой обход уровня заказа
// бинарного дерева поиска

bool levelOrderIsOfBST(int arr[], int n)

{

    // если дерево пусто

    if (n == 0)

        return true;

      

    // очередь для хранения NodeDetails

    queue<NodeDetails> q;

      

    // индексная переменная для доступа к элементам массива

    int i=0;

      

    // детали узла для

    // корень BST

    NodeDetails newNode;

    newNode.data = arr[i++];

    newNode.min = INT_MIN;

    newNode.max = INT_MAX;

    q.push(newNode);

      

    // пока нет больше элементов

    // в arr [] или очередь не пуста

    while (i != n && !q.empty())        

    {

        // извлекаем NodeDetails из

        // узел из очереди

        NodeDetails temp = q.front();

        q.pop();

          

        // проверяем, есть ли еще элементы

        // в arr [] и arr [i] можно оставить дочерний

        // из temp.data или нет

        if (i < n && (arr[i] < temp.data && 

                     arr[i] > temp.min))

        {

            // Создать NodeDetails для newNode

            /// и добавить его в очередь

            newNode.data = arr[i++];

            newNode.min = temp.min;

            newNode.max = temp.data;

            q.push(newNode);                

        }

          

        // проверяем, есть ли еще элементы

        // в arr [] и arr [i] может быть правый ребенок

        // из temp.data или нет

        if (i < n && (arr[i] > temp.data && 

                      arr[i] < temp.max))

        {

            // Создать NodeDetails для newNode

            /// и добавить его в очередь

            newNode.data = arr[i++];

            newNode.min = temp.data;

            newNode.max = temp.max;

            q.push(newNode);            

        }        

    }

      

    // данный массив представляет уровень

    // порядок прохождения BST

    if (i == n)

        return true;

          

    // данный массив не представляет

    // уровень прохождения порядка BST

    return false;        

}

  
// Программа драйвера для тестирования выше

int main()

{

    int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};    

    int n = sizeof(arr) / sizeof(arr[0]);    

    if (levelOrderIsOfBST(arr, n))

        cout << "Yes";

    else

        cout << "No";        

    return 0;    

Джава

// Реализация Java для проверки наличия данного массива
// может представлять обход уровня двоичного
// Дерево поиска

import java.util.*;

  

class Solution

{

  
// для хранения деталей узла типа
// данные узла, 'min' и 'max' для получения
// диапазон значений где левый узел и
// правый ребенок должен лгать

static class NodeDetails

{

    int data;

    int min, max;

};

  
// функция для проверки наличия данного массива
// может представлять собой обход уровня заказа
// бинарного дерева поиска

static boolean levelOrderIsOfBST(int arr[], int n)

{

    // если дерево пусто

    if (n == 0)

        return true;

      

    // очередь для хранения NodeDetails

    Queue<NodeDetails> q = new LinkedList<NodeDetails>();

      

    // индексная переменная для доступа к элементам массива

    int i = 0;

      

    // детали узла для

    // корень BST

    NodeDetails newNode=new NodeDetails();

    newNode.data = arr[i++];

    newNode.min = Integer.MIN_VALUE;

    newNode.max = Integer.MAX_VALUE;

    q.add(newNode);

      

    // пока нет больше элементов

    // в arr [] или очередь не пуста

    while (i != n && q.size() > 0)     

    {

        // извлекаем NodeDetails из

        // узел из очереди

        NodeDetails temp = q.peek();

        q.remove();

        newNode = new NodeDetails();

          

        // проверяем, есть ли еще элементы

        // в arr [] и arr [i] можно оставить дочерний

        // из temp.data или нет

        if (i < n && (arr[i] < (int)temp.data && 

                    arr[i] > (int)temp.min))

        {

            // Создать NodeDetails для newNode

            /// и добавить его в очередь

            newNode.data = arr[i++];

            newNode.min = temp.min;

            newNode.max = temp.data;

            q.add(newNode);             

        }

          

        newNode=new NodeDetails();

          

        // проверяем, есть ли еще элементы

        // в arr [] и arr [i] может быть правый ребенок

        // из temp.data или нет

        if (i < n && (arr[i] > (int)temp.data && 

                    arr[i] < (int)temp.max))

        {

            // Создать NodeDetails для newNode

            /// и добавить его в очередь

            newNode.data = arr[i++];

            newNode.min = temp.data;

            newNode.max = temp.max;

            q.add(newNode);         

        }     

    }

      

    // данный массив представляет уровень

    // порядок прохождения BST

    if (i == n)

        return true;

          

    // данный массив не представляет

    // уровень прохождения порядка BST

    return false;     

}

  
// Код драйвера

public static void main(String args[])

{

    int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10}; 

    int n = arr.length; 

    if (levelOrderIsOfBST(arr, n))

        System.out.print( "Yes");

    else

        System.out.print( "No");     

      
}

  
// Этот код предоставлен Арнабом Кунду

python3

# Реализация Python3, чтобы проверить,
# данный массив может представлять уровень порядка
# Обход бинарного дерева поиска

INT_MIN, INT_MAX = float('-inf'), float('inf')

  
# Для хранения деталей узла, таких как узел
# данные, 'min' и 'max', чтобы получить
# диапазон значений, где слева от узла
# а права ребенка должны лежать

class NodeDetails: 

  

    def __init__(self, data, min, max):

        self.data = data

        self.min = min

        self.max = max

  
# функция для проверки наличия данного массива
# может представлять уровень порядка обхода
# бинарного дерева поиска

def levelOrderIsOfBST(arr, n): 

  

    # если дерево пусто

    if n == 0

        return True

      

    # очередь для хранения NodeDetails

    q = [] 

      

    # индексная переменная для доступа к элементам массива

    i = 0

      

    # детали узла для корня BST

    newNode = NodeDetails(arr[i], INT_MIN, INT_MAX) 

    i += 1

    q.append(newNode) 

      

    # пока нет больше элементов

    # в arr [] или очередь не пуста

    while i != n and len(q) != 0:     

      

        # извлечение NodeDetails из

        # узел из очереди

        temp = q.pop(0

          

        # проверить, есть ли еще элементы

        # в arr [] и arr [i] можно оставить

        # дочерний элемент 'temp.data' или нет

        if i < n and (arr[i] < temp.data and

                    arr[i] > temp.min): 

          

            # Создать NodeDetails для newNode

            # / и добавить его в очередь

            newNode = NodeDetails(arr[i], temp.min, temp.data)

            i += 1

            q.append(newNode)             

          

        # проверить, есть ли еще элементы

        # в arr [] и arr [i] могут быть правильными

        # дочерний элемент 'temp.data' или нет

        if i < n and (arr[i] > temp.data and

                    arr[i] < temp.max): 

          

            # Создать NodeDetails для newNode

            # / и добавить его в очередь

            newNode = NodeDetails(arr[i], temp.data, temp.max)

            i += 1

            q.append(newNode)         

                  

    # данный массив представляет уровень

    # порядок обхода BST

    if i == n: 

        return True

          

    # данный массив не представляет

    # уровень порядка обхода BST

    return False        

  
# Код драйвера

if __name__ == "__main__"

  

    arr = [7, 4, 12, 3, 6, 8, 1, 5, 10

    n = len(arr)     

    if levelOrderIsOfBST(arr, n): 

        print("Yes"

    else:

        print("No")

  
# Этот код предоставлен Rituraj Jain

C #

// реализация C #, чтобы проверить, является ли данный массив
// может представлять обход уровня двоичного
// Дерево поиска

using System;

using System.Collections.Generic;

      

class GFG

{

  
// для хранения деталей узла типа
// данные узла, 'min' и 'max' для получения
// диапазон значений где левый узел и
// правый ребенок должен лгать

public class NodeDetails

{

    public int data;

    public int min, max;

};

  
// функция для проверки наличия данного массива
// может представлять собой обход уровня заказа
// бинарного дерева поиска

static Boolean levelOrderIsOfBST(int []arr, int n)

{

    // если дерево пусто

    if (n == 0)

        return true;

      

    // очередь для хранения NodeDetails

    Queue<NodeDetails> q = new Queue<NodeDetails>();

      

    // индексная переменная для доступа к элементам массива

    int i = 0;

      

    // детали узла для

    // корень BST

    NodeDetails newNode=new NodeDetails();

    newNode.data = arr[i++];

    newNode.min = int.MinValue;

    newNode.max = int.MaxValue;

    q.Enqueue(newNode);

      

    // пока нет больше элементов

    // в arr [] или очередь не пуста

    while (i != n && q.Count > 0)     

    {

        // извлекаем NodeDetails из

        // узел из очереди

        NodeDetails temp = q.Peek();

        q.Dequeue();

        newNode = new NodeDetails();

          

        // проверяем, есть ли еще элементы

        // в arr [] и arr [i] можно оставить дочерний

        // из temp.data или нет

        if (i < n && (arr[i] < (int)temp.data && 

                    arr[i] > (int)temp.min))

        {

            // Создать NodeDetails для newNode

            /// and add it to the queue

            newNode.data = arr[i++];

            newNode.min = temp.min;

            newNode.max = temp.data;

            q.Enqueue(newNode);             

        }

          

        newNode=new NodeDetails();

          

        // проверяем, есть ли еще элементы

        // в arr [] и arr [i] может быть правый ребенок

        // из temp.data или нет

        if (i < n && (arr[i] > (int)temp.data && 

                    arr[i] < (int)temp.max))

        {

            // Создать NodeDetails для newNode

            /// and add it to the queue

            newNode.data = arr[i++];

            newNode.min = temp.data;

            newNode.max = temp.max;

            q.Enqueue(newNode);         

        }     

    }

      

    // данный массив представляет уровень

    // порядок прохождения BST

    if (i == n)

        return true;

          

    // данный массив не представляет

    // уровень прохождения порядка BST

    return false;     

}

  
// Код драйвера

public static void Main(String []args)

{

    int []arr = {7, 4, 12, 3, 6, 8, 1, 5, 10}; 

    int n = arr.Length; 

    if (levelOrderIsOfBST(arr, n))

        Console.Write( "Yes");

    else

        Console.Write( "No");     

      
}

  
// Этот код предоставлен Rajput-Ji

Выход:

Yes

Сложность времени: O (n)

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проверьте, может ли данный массив представлять уровень порядка обхода дерева двоичного поиска

0.00 (0%) 0 votes