Рубрики

Проверьте, является ли двоичное дерево BST: простой и эффективный подход

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

Двоичное дерево поиска (BST) — это структура данных двоичного дерева на основе узлов, которая имеет следующие свойства.

  • Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла.
  • Правое поддерево узла содержит только узлы с ключами, которые больше ключа узла.
  • Левое и правое поддеревья также должны быть деревьями двоичного поиска.

Из вышеуказанных свойств естественно следует, что:

  • Каждый узел (элемент в дереве) имеет отдельный ключ.
  • Мы уже обсуждали различные подходы к решению этой проблемы в предыдущей статье .

    В этой статье мы обсудим простой, но эффективный подход для решения вышеуказанной проблемы.

    Идея состоит в том, чтобы использовать обход Inorder и отслеживать значение ранее посещенного узла. Поскольку обход по порядку следования BST генерирует отсортированный массив в качестве вывода, поэтому предыдущий элемент всегда должен быть меньше или равен текущему элементу.

    Выполняя обход In-Order, мы можем отслеживать значение ранее посещенного узла, передавая целочисленную переменную, используя ссылку на рекурсивные вызовы. Если значение текущего посещенного узла меньше, чем предыдущее значение, дерево не является BST.

    Ниже приведена реализация вышеуказанного подхода:

    // C ++ программа для проверки, является ли данное дерево BST.
    #include <bits/stdc++.h>

    using namespace std;

      
    / * Узел двоичного дерева содержит данные, указатель на
    левый ребенок и указатель на правый ребенок * /

    struct Node {

        int data;

        struct Node *left, *right;

      

        Node(int data)

        {

            this->data = data;

            left = right = NULL;

        }

    };

      
    // Утилита для проверки, является ли Binary Tree BST

    bool isBSTUtil(struct Node* root, int& prev)

    {

        // проходим дерево по порядку и

        // отслеживаем предыдущий узел

        if (root) {

            if (!isBSTUtil(root->left, prev))

                return false;

      

            // Допускает только отдельные значимые узлы

            if (root->data <= prev)

                return false;

      

            // Инициализировать предыдущий к текущему

            prev = root->data;

      

            return isBSTUtil(root->right, prev);

        }

      

        return true;

    }

      
    // Функция для проверки, является ли двоичное дерево BST

    bool isBST(Node* root)

    {

        int prev = INT_MIN;

        return isBSTUtil(root, prev);

    }

      
    / * Программа драйвера для проверки вышеуказанных функций * /

    int main()

    {

        struct Node* root = new Node(5);

        root->left = new Node(2);

        root->right = new Node(15);

        root->left->left = new Node(1);

        root->left->right = new Node(4);

      

        if (isBST(root))

            cout << "Is BST";

        else

            cout << "Not a BST";

      

        return 0;

    }

    Выход:

    Is BST
    

    Сложность времени: O (N)
    Вспомогательное пространство: O (1)

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

    Проверьте, является ли двоичное дерево BST: простой и эффективный подход

    0.00 (0%) 0 votes