Рубрики

Программа для проверки, является ли двоичное дерево BST или нет

Бинарное дерево поиска (BST) — это структура данных двоичного дерева на основе узлов, которая имеет следующие свойства.
• Левое поддерево узла содержит только узлы, ключи которых меньше ключа узла.
• Правое поддерево узла содержит только узлы с ключами, которые больше ключа узла.
• Левое и правое поддеревья также должны быть деревьями двоичного поиска.

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

МЕТОД 1 (простой, но неправильный)
Ниже приводится простая программа. Для каждого узла проверьте, меньше ли его левый узел, чем узел, а правый узел больше, чем узел.

int isBST(struct node* node) 

  if (node == NULL) 

    return 1; 

      

  / * ложь, если слева больше, чем узел * /

  if (node->left != NULL && node->left->data > node->data) 

    return 0; 

      

  / * ложь, если право <, чем узел * /

  if (node->right != NULL && node->right->data < node->data) 

    return 0; 

    

  / * false если рекурсивно, левый или правый не BST * /

  if (!isBST(node->left) || !isBST(node->right)) 

    return 0; 

      

  / * прохождение всего этого, это BST * /

  return 1; 

}

Этот подход неверен, так как он вернет true для нижнего двоичного дерева (и нижнее дерево не является BST, потому что 4 находится в левом поддереве 3)

МЕТОД 2 (правильный, но не эффективный)
Для каждого узла проверьте, является ли максимальное значение в левом поддереве меньше, чем узел, и минимальное значение в правом поддереве больше, чем узел.

/ * Возвращает true, если двоичное дерево является двоичным деревом поиска * / 

int isBST(struct node* node) 

  if (node == NULL) 

    return(true); 

      

  / * ложь, если левый максимум> чем у нас * /

  if (node->left!=NULL && maxValue(node->left) > node->data) 

    return(false); 

      

  / * ложь, если минус права <= чем у нас * /

  if (node->right!=NULL && minValue(node->right) < node->data) 

    return(false); 

    

  / * false если рекурсивно, левый или правый не BST * /

  if (!isBST(node->left) || !isBST(node->right)) 

    return(false); 

      

  / * прохождение всего этого, это BST * /

  return(true); 

Предполагается, что у вас есть вспомогательные функции minValue () и maxValue (), которые возвращают значение min или max int из непустого дерева

МЕТОД 3 (правильный и эффективный) :
Метод 2, описанный выше, работает медленно, так как он пересекает некоторые части дерева много раз. Лучшее решение смотрит на каждый узел только один раз. Хитрость заключается в том, чтобы написать вспомогательную вспомогательную функцию isBSTUtil (struct node * node, int min, int max), которая перемещается по дереву, отслеживая сужающиеся минимальные и максимальные допустимые значения по ходу, просматривая каждый узел только один раз. Начальные значения для min и max должны быть INT_MIN и INT_MAX — они сужаются оттуда.

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

C ++

#include<bits/stdc++.h>
#include<iostream>

using namespace std;

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

class node 

    public:

    int data; 

    node* left; 

    node* right; 

      

    / * Конструктор, который выделяет

    новый узел с заданными данными

    и NULL левый и правый указатели. * /

    node(int data)

    {

        this->data = data;

        this->left = NULL;

        this->right = NULL;

    }

};

  

int isBSTUtil(node* node, int min, int max); 

  
/ * Возвращает true, если данный
дерево - это двоичное дерево поиска
(эффективная версия). * /

int isBST(node* node) 

    return(isBSTUtil(node, INT_MIN, INT_MAX)); 

  
/ * Возвращает true, если данный
дерево BST и его значения
являются> = мин и <= макс. * /

int isBSTUtil(node* node, int min, int max) 

    / * пустое дерево BST * /

    if (node==NULL) 

        return 1; 

              

    / * false, если этот узел нарушает

    ограничение min / max * /

    if (node->data < min || node->data > max) 

        return 0; 

      

    / * в противном случае проверяем поддеревья рекурсивно,

    ужесточение минимального или максимального ограничения * /

    return

        isBSTUtil(node->left, min, node->data-1) && // Разрешить только разные значения

        isBSTUtil(node->right, node->data+1, max); // Разрешить только разные значения

  

  
/ * Код водителя * /

int main() 

    node *root = new node(4); 

    root->left = new node(2); 

    root->right = new node(5); 

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

    root->left->right = new node(3); 

      

    if(isBST(root)) 

        cout<<"Is BST"

    else

        cout<<"Not a BST"

          

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

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

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

  

int isBSTUtil(struct node* node, int min, int max);

  
/ * Возвращает true, если данное дерево является двоичным деревом поиска

 (эффективная версия). * / 

int isBST(struct node* node) 

  return(isBSTUtil(node, INT_MIN, INT_MAX)); 

  
/ * Возвращает true, если данное дерево является BST и его

   Значения> = мин и <= макс. * / 

int isBSTUtil(struct node* node, int min, int max) 

  / * пустое дерево BST * /

  if (node==NULL) 

     return 1;

        

  / * false, если этот узел нарушает ограничение min / max * /  

  if (node->data < min || node->data > max) 

     return 0; 

  

  / * в противном случае проверяем поддеревья рекурсивно,

   ужесточение минимального или максимального ограничения * /

  return 

    isBSTUtil(node->left, min, node->data-1) &&  // Разрешить только разные значения

    isBSTUtil(node->right, node->data+1, max);  // Разрешить только разные значения

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

struct node* newNode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  

  return(node);

}

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

int main()

{

  struct node *root = newNode(4);

  root->left        = newNode(2);

  root->right       = newNode(5);

  root->left->left  = newNode(1);

  root->left->right = newNode(3); 

  

  if(isBST(root))

    printf("Is BST");

  else

    printf("Not a BST");

      

  getchar();

  return 0;

}  

Джава

// Реализация Java для проверки, задано ли двоичное дерево
// это BST или нет

  
/ * Класс, содержащий левого и правого потомка текущего

 значение узла и ключа * /

class Node

{

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    // Корень бинарного дерева

    Node root;

  

    / * может дать минимальное и максимальное значение в соответствии с вашим кодом или

    Можно написать функцию, чтобы найти минимальное и максимальное значение дерева. * /

  

    / * возвращает true, если данное дерево поиска является двоичным

     дерево поиска (эффективная версия) * /

    boolean isBST()  {

        return isBSTUtil(root, Integer.MIN_VALUE,

                               Integer.MAX_VALUE);

    }

  

    / * Возвращает true, если данное дерево является BST и его

      Значения> = мин и <= макс. * /

    boolean isBSTUtil(Node node, int min, int max)

    {

        / * пустое дерево BST * /

        if (node == null)

            return true;

  

        / * false, если этот узел нарушает ограничения min / max * /

        if (node.data < min || node.data > max)

            return false;

  

        / * рекурсивно проверять поддеревья

        ужесточение мин / макс ограничений * /

        // Разрешить только разные значения

        return (isBSTUtil(node.left, min, node.data-1) &&

                isBSTUtil(node.right, node.data+1, max));

    }

  

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

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(4);

        tree.root.left = new Node(2);

        tree.root.right = new Node(5);

        tree.root.left.left = new Node(1);

        tree.root.left.right = new Node(3);

  

        if (tree.isBST())

            System.out.println("IS BST");

        else

            System.out.println("Not a BST");

    }

}

питон

# Python программа для проверки, является ли двоичное дерево BST или нет

  

INT_MAX = 4294967296

INT_MIN = -4294967296

  
# Узел двоичного дерева

class Node:

  

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  

  
# Возвращает true, если данное дерево является двоичным деревом поиска
# (эффективная версия)

def isBST(node):

    return (isBSTUtil(node, INT_MIN, INT_MAX))

  
# Retusn true, если данное дерево является BST и его значения
#> = мин и <= макс

def isBSTUtil(node, mini, maxi):

      

    # Пустое дерево BST

    if node is None:

        return True

  

    # False, если этот узел нарушает ограничение min / max

    if node.data < mini or node.data > maxi:

        return False

  

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

    # ужесточение минимального или максимального ограничения

    return (isBSTUtil(node.left, mini, node.data -1) and

          isBSTUtil(node.right, node.data+1, maxi))

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

root = Node(4)

root.left = Node(2)

root.right = Node(5)

root.left.left = Node(1)

root.left.right = Node(3)

  

if (isBST(root)):

    print "Is BST"

else:

    print "Not a BST"

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

  
// реализация C #, чтобы проверить, задано ли двоичное дерево
// это BST или нет

  
/ * Класс, содержащий левого и правого потомка текущего

 значение узла и ключа * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    // Корень бинарного дерева

    public Node root;

  

    / * может дать минимальное и максимальное значение в соответствии с вашим кодом или

    Можно написать функцию, чтобы найти минимальное и максимальное значение дерева. * /

  

    / * возвращает true, если данное дерево поиска является двоичным

     дерево поиска (эффективная версия) * /

    public virtual bool BST

    {

        get

        {

            return isBSTUtil(root, int.MinValue, int.MaxValue);

        }

    }

  

    / * Возвращает true, если данное дерево является BST и его

      Значения> = мин и <= макс. * /

    public virtual bool isBSTUtil(Node node, int min, int max)

    {

        / * пустое дерево BST * /

        if (node == null)

        {

            return true;

        }

  

        / * false, если этот узел нарушает ограничения min / max * /

        if (node.data < min || node.data > max)

        {

            return false;

        }

  

        / * рекурсивно проверять поддеревья

        ужесточение мин / макс ограничений * /

        // Разрешить только разные значения

        return (isBSTUtil(node.left, min, node.data - 1) && isBSTUtil(node.right, node.data + 1, max));

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(4);

        tree.root.left = new Node(2);

        tree.root.right = new Node(5);

        tree.root.left.left = new Node(1);

        tree.root.left.right = new Node(3);

  

        if (tree.BST)

        {

            Console.WriteLine("IS BST");

        }

        else

        {

            Console.WriteLine("Not a BST");

        }

    }

}

  

  // Этот код предоставлен Shrikant13


Выход:

IS BST

Сложность времени: O (n)
Вспомогательное пространство: O (1), если размер стека вызова функции не учитывается, в противном случае O (n)

Упрощенный метод 3
Мы можем упростить метод 2, используя указатели NULL вместо значений INT_MIN и INT_MAX.

C ++

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

using namespace std;

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

   левый ребенок и указатель на правый ребенок * /

struct Node

{

    int data;

    struct Node* left, *right;

};

  
// Возвращает true, если данное дерево BST.

bool isBST(Node* root, Node* l=NULL, Node* r=NULL)

{

    // Базовое условие

    if (root == NULL)

        return true;

  

    // если левый узел существует, проверьте, есть ли у него

    // правильные данные или нет, т.е. данные левого узла

    // должно быть меньше данных root

    if (l != NULL and root->data <= l->data)

        return false;

  

    // если правый узел существует, проверьте, есть ли у него

    // правильные данные или нет, т.е. данные правого узла

    // должно быть больше данных root

    if (r != NULL and root->data >= r->data)

        return false;

  

    // рекурсивно проверяем каждый узел.

    return isBST(root->left, l, root) and

           isBST(root->right, root, r);

}

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

struct Node* newNode(int data)

{

    struct Node* node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return (node);

}

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

int main()

{

    struct Node *root = newNode(3);

    root->left        = newNode(2);

    root->right       = newNode(5);

    root->left->left  = newNode(1);

    root->left->right = newNode(4);

  

    if (isBST(root,NULL,NULL))

        cout << "Is BST";

    else

        cout << "Not a BST";

  

    return 0;

}

Джава

// Java-программа для проверки, является ли данное дерево BST.

class Sol

{

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

static class Node 

    int data; 

    Node left, right; 

}; 

  
// Возвращает true, если данное дерево BST.

static boolean isBST(Node root, Node l, Node r) 

    // Базовое условие

    if (root == null

        return true

  

    // если левый узел существует, проверьте, есть ли у него

    // правильные данные или нет, т.е. данные левого узла

    // должно быть меньше данных root

    if (l != null && root.data <= l.data) 

        return false

  

    // если правый узел существует, проверьте, есть ли у него

    // правильные данные или нет, т.е. данные правого узла

    // должно быть больше данных root

    if (r != null && root.data >= r.data) 

        return false

  

    // рекурсивно проверяем каждый узел.

    return isBST(root.left, l, root) && 

        isBST(root.right, root, r); 

  
// Вспомогательная функция, которая выделяет новый узел с
// данные даны && null left && right указатели. /

static Node newNode(int data) 

    Node node = new Node(); 

    node.data = data; 

    node.left = node.right = null

    return (node); 

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

public static void main(String args[])

    Node root = newNode(3); 

    root.left = newNode(2); 

    root.right = newNode(5); 

    root.left.left = newNode(1); 

    root.left.right = newNode(4); 

  

    if (isBST(root,null,null)) 

        System.out.print("Is BST"); 

    else

        System.out.print("Not a BST"); 

}

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

python3

"" "Программа для проверки наличия данного двоичного файла
Дерево сбалансировано, как красно-черное дерево "" "

  
# Вспомогательная функция, которая выделяет новый
# узел с заданными данными и None
# левый и правый пиры

class newNode: 

  

    # Конструкция для создания нового узла

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

  
# Возвращает true, если данное дерево BST.

def isBST(root, l = None, r = None): 

  

    # Базовое состояние

    if (root == None) :

        return True

  

    # если левый узел существует, проверьте его

    # правильные данные или нет, т.е. данные левого узла

    # должно быть меньше данных root

    if (l != None and root.data <= l.data) :

        return False

  

    # если правый узел существует, проверьте, есть ли у него

    # правильные данные или нет, т.е. данные правого узла

    # должно быть больше данных root

    if (r != None and root.data >= r.data) :

        return False

  

    # проверять рекурсивно для каждого узла.

    return isBST(root.left, l, root) and \

        isBST(root.right, root, r) 

  

  
Код водителя

if __name__ == '__main__':

    root = newNode(3

    root.left = newNode(2

    root.right = newNode(5

    root.right.left = newNode(1

    root.right.right = newNode(4

    # root.right.left.left = newNode (40)

    if (isBST(root,None,None)):

        print("Is BST")

    else:

        print("Not a BST")

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

// C # программа для проверки, является ли данное дерево BST.

using System;

      

class GFG

{

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

public class Node 

    public int data; 

    public Node left, right; 

}; 

  
// Возвращает true, если данное дерево BST.

static Boolean isBST(Node root, Node l, Node r) 

    // Базовое условие

    if (root == null

        return true

  

    // если левый узел существует, проверьте, есть ли у него

    // правильные данные или нет, т.е. данные левого узла

    // должно быть меньше данных root

    if (l != null && root.data <= l.data) 

        return false

  

    // если правый узел существует, проверьте, есть ли у него

    // правильные данные или нет, т.е. данные правого узла

    // должно быть больше данных root

    if (r != null && root.data >= r.data) 

        return false

  

    // рекурсивно проверяем каждый узел.

    return isBST(root.left, l, root) && 

        isBST(root.right, root, r); 

  
// Вспомогательная функция, которая выделяет новый узел с
// данные даны && null left && right указатели. /

static Node newNode(int data) 

    Node node = new Node(); 

    node.data = data; 

    node.left = node.right = null

    return (node); 

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

public static void Main(String []args)

    Node root = newNode(3); 

    root.left = newNode(2); 

    root.right = newNode(5); 

    root.left.left = newNode(1); 

    root.left.right = newNode(4); 

  

    if (isBST(root,null,null)) 

        Console.Write("Is BST"); 

    else

        Console.Write("Not a BST"); 

}
}

  
// Этот код предоставлен 29AjayKumar

Выход :

Not a BST

Спасибо Abhinesh Garhwal за предложенное решение.

МЕТОД 4 (Использование обхода заказа)
Спасибо LJW489 за предложение этого метода.
1) Выполните обход по порядку данного дерева и сохраните результат во временном массиве.
3) Проверьте, отсортирован ли временный массив в порядке возрастания, если это так, то дерево является BST.

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

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

C ++

bool isBST(node* root) 

    static node *prev = NULL; 

      

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

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

    if (root) 

    

        if (!isBST(root->left)) 

        return false

  

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

        if (prev != NULL && 

            root->data <= prev->data) 

        return false

  

        prev = root; 

  

        return isBST(root->right); 

    

  

    return true

  
// Этот код предоставлен rathbhupendra

С

bool isBST(struct node* root)

{

    static struct node *prev = NULL;

      

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

    if (root)

    {

        if (!isBST(root->left))

          return false;

  

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

        if (prev != NULL && root->data <= prev->data)

          return false;

  

        prev = root;

  

        return isBST(root->right);

    }

  

    return true;

}

Джава

// Реализация Java для проверки, задано ли двоичное дерево
// это BST или нет

  
/ * Класс, содержащий левого и правого потомка текущего

 значение узла и ключа * /

class Node

{

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    // Корень бинарного дерева

    Node root;

  

    // Сохранить путь предыдущего узла в обходе Inorder

    Node prev;

  

    boolean isBST()  {

        prev = null;

        return isBST(root);

    }

  

    / * Возвращает true, если данное дерево поиска является двоичным

       дерево поиска (эффективная версия) * /

    boolean isBST(Node node)

    {

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

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

        if (node != null)

        {

            if (!isBST(node.left))

                return false;

  

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

            if (prev != null && node.data <= prev.data )

                return false;

            prev = node;

            return isBST(node.right);

        }

        return true;

    }

  

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

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(4);

        tree.root.left = new Node(2);

        tree.root.right = new Node(5);

        tree.root.left.left = new Node(1);

        tree.root.left.right = new Node(3);

  

        if (tree.isBST())

            System.out.println("IS BST");

        else

            System.out.println("Not a BST");

    }

}

python3

# Реализация Python для проверки
# данное двоичное дерево является BST или нет

  
# Узел двоичного дерева, содержащий данные
# поле, левый и правый указатели

class Node:

    # конструктор для создания нового узла

    def __init__(self, val):

        self.data = val

        self.left = None

        self.right = None

  
# глобальная переменная prev - отслеживать
# предыдущего узла во время заказа
# обход

prev = None

  
# функция для проверки, если дан бинарный файл
# дерево BST

def isbst(root):

      

    # prev является глобальной переменной

    global prev

    prev = None

    return isbst_rec(root)

  

  
# Вспомогательная функция для проверки бинарности
# дерево BST
# Пройдите дерево по порядку
# и отслеживать предыдущий узел
# вернуть true, если дерево является двоичным
# дерево поиска в противном случае false

def isbst_rec(root):

      

    # prev является глобальной переменной

    global prev 

  

    # если дерево пусто, вернуть true

    if root is None:

        return True

  

    if isbst_rec(root.left) is False:

        return False

  

    # если найдены данные предыдущего узла

    # больше текущего узла

    # возвращаемые данные

    if prev is not None and prev.data > root.data:

        return False

  

    # сохранить текущий узел в пред.

    prev = root

    return isbst_rec(root.right)

  

  
# код драйвера для проверки вышеуказанной функции

root = Node(4)

root.left = Node(2)

root.right = Node(5)

root.left.left = Node(1)

root.left.right = Node(3)

  

if isbst(root):

    print("is BST")

else:

    print("not a BST")

  
# Этот код предоставлен
# Швета Сингх (shweta44)

C #

// реализация C # для проверки
// данное двоичное дерево является BST или нет

using System;

  
/ * Класс, содержащий слева и
правый потомок текущего узла
и значение ключа * /

class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    // Корень бинарного дерева

    Node root;

  

    // Следить за предыдущим узлом

    // в Inorder Traversal

    Node prev;

  

    Boolean isBST()

    {

        prev = null;

        return isBST(root);

    }

  

    / * Возвращает true, если данное дерево поиска является двоичным

    дерево поиска (эффективная версия) * /

    Boolean isBST(Node node)

    {

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

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

        if (node != null)

        {

            if (!isBST(node.left))

                return false;

  

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

            if (prev != null && 

                node.data <= prev.data )

                return false;

            prev = node;

            return isBST(node.right);

        }

        return true;

    }

  

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

    public static void Main(String []args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(4);

        tree.root.left = new Node(2);

        tree.root.right = new Node(5);

        tree.root.left.left = new Node(1);

        tree.root.left.right = new Node(3);

  

        if (tree.isBST())

            Console.WriteLine("IS BST");

        else

            Console.WriteLine("Not a BST");

    }

}

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

Также можно избежать использования статической переменной, используя ссылку на узел prev в качестве параметра.

C ++

// 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;

    }

};

  

  

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

{

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

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

    if (root)

    {

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

          return false;

   

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

        if (prev != NULL && root->data <= prev->data)

          return false;

   

        prev = root;

   

        return isBSTUtil(root->right, prev);

    }

   

    return true;

}

  

bool isBST(Node *root)

{

   Node *prev = NULL;

   return isBSTUtil(root, prev);

}

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

int main()

{

    struct Node *root = new Node(3);

    root->left     = new Node(2);

    root->right     = new Node(5);

    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;

}

Джава

// Java-программа для проверки, является ли данное дерево BST.

class GFG

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

static class Node

{

    int data;

    Node left, right;

      

    Node(int data)

    {

        this.data = data;

        left = right = null;

    }

};

static Node prev;

  

static boolean isBSTUtil(Node root)

{

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

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

    if (root != null)

    {

        if (!isBSTUtil(root.left))

        return false;

  

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

        if (prev != null && root.data <= prev.data)

        return false;

  

        prev = root;

  

        return isBSTUtil(root.right);

    }

    return true;

}

  

static boolean isBST(Node root)

{

    return isBSTUtil(root);

}

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

public static void main(String[] args) 

{

    Node root = new Node(3);

    root.left     = new Node(2);

    root.right     = new Node(5);

    root.left.left = new Node(1);

    root.left.right = new Node(4);

  

    if (isBST(root))

        System.out.print("Is BST");

    else

        System.out.print("Not a BST");

}
}

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

python3

# Python3 программа для проверки
# если данное дерево BST.

import math

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

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

      

def isBSTUtil(root, prev):

      

    # пройти дерево по порядку

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

    if (root != None):

        if (isBSTUtil(root.left, prev) == True):

            return False

  

        # Разрешает только отдельные значимые узлы

        if (prev != None and

            root.data <= prev.data):

            return False

  

        prev = root

        return isBSTUtil(root.right, prev)

      

    return True

  

def isBST(root):

    prev = None

    return isBSTUtil(root, prev)

  
Код водителя

if __name__ == '__main__':

    root = Node(3

    root.left = Node(2

    root.right = Node(5

    root.right.left = Node(1

    root.right.right = Node(4

    # root.right.left.left = Node (40)

      

    if (isBST(root) == None):

        print("Is BST")

    else:

        print("Not a BST")

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

C #

// C # программа для проверки, является ли данное дерево BST.

using System;

public class GFG

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

public class Node

{

    public int data;

    public Node left, right;

      

    public Node(int data)

    {

        this.data = data;

        left = right = null;

    }

};

  

static Node prev;

  

static Boolean isBSTUtil(Node root)

{

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

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

    if (root != null)

    {

        if (!isBSTUtil(root.left))

        return false;

  

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

        if (prev != null && 

            root.data <= prev.data)

        return false;

  

        prev = root;

  

        return isBSTUtil(root.right);

    }

    return true;

}

  

static Boolean isBST(Node root)

{

    return isBSTUtil(root);

}

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

public static void Main(String[] args) 

{

    Node root = new Node(3);

    root.left = new Node(2);

    root.right = new Node(5);

    root.left.left = new Node(1);

    root.left.right = new Node(4);

  

    if (isBST(root))

        Console.WriteLine("Is BST");

    else

        Console.WriteLine("Not a BST");

}
}

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

Выход :

Not a BST

Источники:
http://en.wikipedia.org/wiki/Binary_search_tree
http://cslibrary.stanford.edu/110/BinaryTrees.html

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в вышеуказанных программах / алгоритмах или другие способы решения той же проблемы.

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

Программа для проверки, является ли двоичное дерево BST или нет

0.00 (0%) 0 votes