Рубрики

Подсчитайте количество деревьев двоичного поиска, присутствующих в двоичном дереве

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

Примеры:

Input:

Output: 7
Here each node represents a binary search tree and there are total 7 nodes.

Input:

Output: 6
Sub-tree rooted under node 5 is a BST

Another BST we have is rooted under the node 8

Thus total 6 BSTs are present (including the leaf nodes).

Подход: Двоичное дерево — это Двоичное дерево поиска, если для каждого узла x верно следующее.

  1. Наибольшее значение в левом поддереве (x) меньше значения x.
  2. Наименьшее значение в правом поддереве (x) больше значения x.

Мы проходим дерево снизу вверх. Для каждого пройденного узла мы храним информацию о максимуме и минимуме этого поддерева, переменную isBST для хранения, если это BST, и переменную num_BST для хранения номера дерева двоичного поиска, укорененного под текущим узлом.

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

C ++

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

using namespace std;

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

struct Node {

    struct Node* left;

    struct Node* right;

    int data;

  

    Node(int data)

    {

        this->data = data;

        this->left = NULL;

        this->right = NULL;

    }

};

  
// Информация хранится в каждом
// узел во время обхода снизу вверх

struct Info {

  

    // Хранит количество присутствующих BST

    int num_BST;

  

    // Максимальное значение в поддереве

    int max;

  

    // Минимальное значение в поддереве

    int min;

  

    // Если поддерево BST

    bool isBST;

};

  
// Возвращает информацию о поддереве, такую как
// количество BST

Info NumberOfBST(struct Node* root)

{

    // Базовый вариант

    if (root == NULL)

        return { 0, INT_MIN, INT_MAX, true };

  

    // Если конечный узел, то возвращаемся из функции и храним

    // информация о листовом узле

    if (root->left == NULL && root->right == NULL)

        return { 1, root->data, root->data, true };

  

    // Сохраняем информацию о левом поддереве

    Info L = NumberOfBST(root->left);

  

    // Сохраняем информацию о правильном поддереве

    Info R = NumberOfBST(root->right);

  

    // Создать узел, который должен быть возвращен

    Info bst;

    bst.min = min(root->data, (min(L.min, R.min)));

    bst.max = max(root->data, (max(L.max, R.max)));

  

    // Если все дерево укоренено под

    // текущий корень BST

    if (L.isBST && R.isBST && root->data > L.max && root->data < R.min) {

  

        // Обновляем количество BST

        bst.isBST = true;

        bst.num_BST = 1 + L.num_BST + R.num_BST;

    }

  

    // Если все дерево не BST,

    // обновляем количество BST

    else {

        bst.isBST = false;

        bst.num_BST = L.num_BST + R.num_BST;

    }

  

    return bst;

}

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

int main()

{

    struct Node* root = new Node(5);

    root->left = new Node(9);

    root->right = new Node(3);

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

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

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

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

  

    cout << NumberOfBST(root).num_BST;

  

    return 0;

}

Джава

// Java-программа для подсчета
// номер двоичного поиска
// деревья в данном двоичном дереве

import java.util.*;

  

class GFG {

  

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

    static class Node {

        Node left;

        Node right;

        int data;

  

        Node(int data)

        {

            this.data = data;

            this.left = null;

            this.right = null;

        }

    };

  

    // Информация хранится в каждом

    // узел во время обхода снизу вверх

    static class Info {

  

        // Хранит количество присутствующих BST

        int num_BST;

  

        // Максимальное значение в поддереве

        int max;

  

        // Минимальное значение в поддереве

        int min;

  

        // Если поддерево BST

        boolean isBST;

  

        Info(int a, int b, int c, boolean d)

        {

            num_BST = a;

            max = b;

            min = c;

            isBST = d;

        }

        Info()

        {

        }

    };

  

    // Возвращает информацию о поддереве, такую как

    // количество BST

    static Info NumberOfBST(Node root)

    {

        // Базовый вариант

        if (root == null)

            return new Info(0, Integer.MIN_VALUE,

                            Integer.MAX_VALUE, true);

  

        // Если конечный узел, то возвращаем

        // из функции и магазина

        // информация о листовом узле

        if (root.left == null && root.right == null)

            return new Info(1, root.data, root.data, true);

  

        // Сохраняем информацию о левом поддереве

        Info L = NumberOfBST(root.left);

  

        // Сохраняем информацию о правильном поддереве

        Info R = NumberOfBST(root.right);

  

        // Создать узел, который должен быть возвращен

        Info bst = new Info();

        bst.min = Math.min(root.data, (Math.min(L.min, R.min)));

        bst.max = Math.max(root.data, (Math.max(L.max, R.max)));

  

        // Если все дерево укоренено под

        // текущий корень BST

        if (L.isBST && R.isBST && root.data > L.max && root.data < R.min) {

  

            // Обновляем количество BST

            bst.isBST = true;

            bst.num_BST = 1 + L.num_BST + R.num_BST;

        }

  

        // Если все дерево не BST,

        // обновляем количество BST

        else {

            bst.isBST = false;

            bst.num_BST = L.num_BST + R.num_BST;

        }

  

        return bst;

    }

  

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

    public static void main(String args[])

    {

        Node root = new Node(5);

        root.left = new Node(9);

        root.right = new Node(3);

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

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

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

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

  

        System.out.print(NumberOfBST(root).num_BST);

    }

}

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

python3

# Python программа для подсчета количества бинарных поисков
# деревьев в данном двоичном дереве

INT_MIN = -2**31

INT_MAX = 2**31

class newNode(): 

  

    def __init__(self, data): 

        self.data = data

        self.left = None

        self.right = None

          

          
# Возвращает информацию о поддереве, такую как
количество BST

def NumberOfBST(root):

  

    # Базовый вариант

    if (root == None):

        return 0, INT_MIN, INT_MAX, True

  

    # Если конечный узел, тогда вернитесь из функции и сохраните

    # информация о листовом узле

    if (root.left == None and root.right == None):

        return 1, root.data, root.data, True

  

    # Хранить информацию о левом поддереве

    L = NumberOfBST(root.left) 

  

    # Хранить информацию о правильном поддереве

    R = NumberOfBST(root.right) 

  

    # Создать узел, который должен быть возвращен

    bst = [0]*4

    bst[2] = min(root.data, (min(L[2], R[2])))

    bst[1] = max(root.data, (max(L[1], R[1])))

  

    # Если все дерево укоренено под

    # текущий корень BST

    if (L[3] and R[3] and root.data > L[1] and root.data < R[2]):

          

  

        # Обновить количество BST

        bst[3] = True

        bst[0] = 1 + L[0] + R[0

          

    # Если все дерево не BST,

    # обновить количество BST

    else:

        bst[3] = False

        bst[0] = L[0] + R[0

  

    return bst

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

if __name__ == '__main__':

    root = newNode(5

    root.left = newNode(9

    root.right = newNode(3

    root.left.left = newNode(6

    root.right.right = newNode(4

    root.left.left.left = newNode(8

    root.left.left.right = newNode(7

  

    print(NumberOfBST(root)[0])

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

C #

using System;

  
// C # программа для подсчета
// номер двоичного поиска
// деревья в данном двоичном дереве

  

public class GFG {

  

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

    public class Node {

        public Node left;

        public Node right;

        public int data;

  

        public Node(int data)

        {

            this.data = data;

            this.left = null;

            this.right = null;

        }

    }

  

    // Информация хранится в каждом

    // узел во время обхода снизу вверх

    public class Info {

  

        // Хранит количество присутствующих BST

        public int num_BST;

  

        // Максимальное значение в поддереве

        public int max;

  

        // Минимальное значение в поддереве

        public int min;

  

        // Если поддерево BST

        public bool isBST;

  

        public Info(int a, int b, int c, bool d)

        {

            num_BST = a;

            max = b;

            min = c;

            isBST = d;

        }

        public Info()

        {

        }

    }

  

    // Возвращает информацию о поддереве, такую как

    // количество BST

    static Info NumberOfBST(Node root)

    {

        // Базовый вариант

        if (root == null)

            return new Info(0, Int32.MinValue,

                            Int32.MaxValue, true);

  

        // Если конечный узел, то возвращаем

        // из функции и магазина

        // информация о листовом узле

        if (root.left == null && root.right == null)

            return new Info(1, root.data, root.data, true);

  

        // Сохраняем информацию о левом поддереве

        Info L = NumberOfBST(root.left);

  

        // Сохраняем информацию о правильном поддереве

        Info R = NumberOfBST(root.right);

  

        // Создать узел, который должен быть возвращен

        Info bst = new Info();

        bst.min = Math.Min(root.data, (Math.Min(L.min, R.min)));

        bst.max = Math.Max(root.data, (Math.Max(L.max, R.max)));

  

        // Если все дерево укоренено под

        // текущий корень BST

        if (L.isBST && R.isBST && root.data > L.max && root.data < R.min) {

  

            // Обновляем количество BST

            bst.isBST = true;

            bst.num_BST = 1 + L.num_BST + R.num_BST;

        }

  

        // Если все дерево не BST,

        // обновляем количество BST

        else {

            bst.isBST = false;

            bst.num_BST = L.num_BST + R.num_BST;

        }

  

        return bst;

    }

  

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

    public static void Main(string[] args)

    {

        Node root = new Node(5);

        root.left = new Node(9);

        root.right = new Node(3);

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

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

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

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

  

        Console.Write(NumberOfBST(root).num_BST);

    }

}

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

Выход:

    1
   /  \
  2    3
 / \  / \
4   5 6  7 

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

Подсчитайте количество деревьев двоичного поиска, присутствующих в двоичном дереве

0.00 (0%) 0 votes