Cuente el número de árboles de búsqueda binarios presentes en un árbol binario

Posted on by Rudeus Greyrat

Dado un árbol binario, la tarea es contar el número de árboles binarios de búsqueda presentes en él.

Ejemplos: 
 

Aporte: 

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

Salida: 4
Aquí cada Node hoja representa un árbol de búsqueda binaria y hay un total de 4 Nodes.
Aporte:

      11
     /  \
    8    10
   /    /  \
  5    9    8
 / \
4   6

Salida: 6 
Sub-árbol enraizado bajo el Node 5 es un BST

   5
  / \
 4   6

Otro BST que tenemos está enraizado bajo el Node 8

        8    
       /    
      5    
     / \
    4   6

Por lo tanto, están presentes un total de 6 BST (incluidos los Nodes de hoja).

Enfoque: un árbol binario es un árbol de búsqueda binario si lo siguiente es cierto para cada Node x. 
 

  1. El valor más grande en el subárbol izquierdo (de x) es más pequeño que el valor de x.
  2. El valor más pequeño en el subárbol derecho (de x) es mayor que el valor de x.

Atravieso un árbol de manera de abajo hacia arriba. Para cada Node atravesado, almacenamos la información del máximo y mínimo de ese subárbol, una variable isBST para almacenar si es un BST y la variable num_BST para almacenar el número de árboles de búsqueda binarios arraigados en el Node actual.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to count number of Binary search trees
// in a given Binary Tree
#include <bits/stdc++.h>
using namespace std;
 
// Binary tree node
struct Node {
    struct Node* left;
    struct Node* right;
    int data;
 
    Node(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
 
// Information stored in every
// node during bottom up traversal
struct Info {
 
    // Stores the number of BSTs present
    int num_BST;
 
    // Max Value in the subtree
    int max;
 
    // Min value in the subtree
    int min;
 
    // If subtree is BST
    bool isBST;
};
 
// Returns information about subtree such as
// number of BST's it has
Info NumberOfBST(struct Node* root)
{
    // Base case
    if (root == NULL)
        return { 0, INT_MIN, INT_MAX, true };
 
    // If leaf node then return from function and store
    // information about the leaf node
    if (root->left == NULL && root->right == NULL)
        return { 1, root->data, root->data, true };
 
    // Store information about the left subtree
    Info L = NumberOfBST(root->left);
 
    // Store information about the right subtree
    Info R = NumberOfBST(root->right);
 
    // Create a node that has to be returned
    Info bst;
    bst.min = min(root->data, (min(L.min, R.min)));
    bst.max = max(root->data, (max(L.max, R.max)));
 
    // If whole tree rooted under the
    // current root is BST
    if (L.isBST && R.isBST && root->data > L.max && root->data < R.min) {
 
        // Update the number of BSTs
        bst.isBST = true;
        bst.num_BST = 1 + L.num_BST + R.num_BST;
    }
 
    // If the whole tree is not a BST,
    // update the number of BSTs
    else {
        bst.isBST = false;
        bst.num_BST = L.num_BST + R.num_BST;
    }
 
    return bst;
}
 
// Driver code
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

// Java program to count
// number of Binary search
// trees in a given Binary Tree
import java.util.*;
 
class GFG {
 
    // Binary tree node
    static class Node {
        Node left;
        Node right;
        int data;
 
        Node(int data)
        {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    };
 
    // Information stored in every
    // node during bottom up traversal
    static class Info {
 
        // Stores the number of BSTs present
        int num_BST;
 
        // Max Value in the subtree
        int max;
 
        // Min value in the subtree
        int min;
 
        // If subtree is BST
        boolean isBST;
 
        Info(int a, int b, int c, boolean d)
        {
            num_BST = a;
            max = b;
            min = c;
            isBST = d;
        }
        Info()
        {
        }
    };
 
    // Returns information about subtree such as
    // number of BST's it has
    static Info NumberOfBST(Node root)
    {
        // Base case
        if (root == null)
            return new Info(0, Integer.MIN_VALUE,
                            Integer.MAX_VALUE, true);
 
        // If leaf node then return
        // from function and store
        // information about the leaf node
        if (root.left == null && root.right == null)
            return new Info(1, root.data, root.data, true);
 
        // Store information about the left subtree
        Info L = NumberOfBST(root.left);
 
        // Store information about the right subtree
        Info R = NumberOfBST(root.right);
 
        // Create a node that has to be returned
        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)));
 
        // If whole tree rooted under the
        // current root is BST
        if (L.isBST && R.isBST && root.data > L.max && root.data < R.min) {
 
            // Update the number of BSTs
            bst.isBST = true;
            bst.num_BST = 1 + L.num_BST + R.num_BST;
        }
 
        // If the whole tree is not a BST,
        // update the number of BSTs
        else {
            bst.isBST = false;
            bst.num_BST = L.num_BST + R.num_BST;
        }
 
        return bst;
    }
 
    // Driver code
    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);
    }
}
 
// This code is contributed by Arnab Kundu

Python3

# Python program to count number of Binary search
# trees in a given Binary Tree
INT_MIN = -2**31
INT_MAX = 2**31
class newNode():
 
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
         
         
# Returns information about subtree such as
# number of BST's it has
def NumberOfBST(root):
 
    # Base case
    if (root == None):
        return 0, INT_MIN, INT_MAX, True
 
    # If leaf node then return from function and store
    # information about the leaf node
    if (root.left == None and root.right == None):
        return 1, root.data, root.data, True
 
    # Store information about the left subtree
    L = NumberOfBST(root.left)
 
    # Store information about the right subtree
    R = NumberOfBST(root.right)
 
    # Create a node that has to be returned
    bst = [0]*4
    bst[2] = min(root.data, (min(L[2], R[2])))
    bst[1] = max(root.data, (max(L[1], R[1])))
 
    # If whole tree rooted under the
    # current root is BST
    if (L[3] and R[3] and root.data > L[1] and root.data < R[2]):
         
 
        # Update the number of BSTs
        bst[3] = True
        bst[0] = 1 + L[0] + R[0]
         
    # If the whole tree is not a BST,
    # update the number of BSTs
    else:
        bst[3] = False
        bst[0] = L[0] + R[0]
 
    return bst
         
# Driver code
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])
 
# This code is contributed by SHUBHAMSINGH10

C#

using System;
 
// C# program to count
// number of Binary search
// trees in a given Binary Tree
 
public class GFG {
 
    // Binary tree node
    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;
        }
    }
 
    // Information stored in every
    // node during bottom up traversal
    public class Info {
 
        // Stores the number of BSTs present
        public int num_BST;
 
        // Max Value in the subtree
        public int max;
 
        // Min value in the subtree
        public int min;
 
        // If subtree is 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()
        {
        }
    }
 
    // Returns information about subtree such as
    // number of BST's it has
    static Info NumberOfBST(Node root)
    {
        // Base case
        if (root == null)
            return new Info(0, Int32.MinValue,
                            Int32.MaxValue, true);
 
        // If leaf node then return
        // from function and store
        // information about the leaf node
        if (root.left == null && root.right == null)
            return new Info(1, root.data, root.data, true);
 
        // Store information about the left subtree
        Info L = NumberOfBST(root.left);
 
        // Store information about the right subtree
        Info R = NumberOfBST(root.right);
 
        // Create a node that has to be returned
        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)));
 
        // If whole tree rooted under the
        // current root is BST
        if (L.isBST && R.isBST && root.data > L.max && root.data < R.min) {
 
            // Update the number of BSTs
            bst.isBST = true;
            bst.num_BST = 1 + L.num_BST + R.num_BST;
        }
 
        // If the whole tree is not a BST,
        // update the number of BSTs
        else {
            bst.isBST = false;
            bst.num_BST = L.num_BST + R.num_BST;
        }
 
        return bst;
    }
 
    // Driver code
    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);
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
      // JavaScript program to count
      // number of Binary search
      // trees in a given Binary Tree
 
      // Binary tree node
      class Node {
        constructor(data) {
          this.data = data;
          this.left = null;
          this.right = null;
        }
      }
 
      // Information stored in every
      // node during bottom up traversal
      class Info
      {
        constructor(a, b, c, d)
        {
         
          // Stores the number of BSTs present
          this.num_BST = a;
           
          // Max Value in the subtree
          this.max = b;
           
          // Min value in the subtree
          this.min = c;
           
          // If subtree is BST
          this.isBST = d;
        }
      }
 
      // Returns information about subtree such as
      // number of BST's it has
      function NumberOfBST(root)
      {
       
        // Base case
        if (root == null) return new Info(0, -2147483648, 2147483647, true);
 
        // If leaf node then return
        // from function and store
        // information about the leaf node
        if (root.left == null && root.right == null)
          return new Info(1, root.data, root.data, true);
 
        // Store information about the left subtree
        var L = NumberOfBST(root.left);
 
        // Store information about the right subtree
        var R = NumberOfBST(root.right);
 
        // Create a node that has to be returned
        var 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));
 
        // If whole tree rooted under the
        // current root is BST
        if (L.isBST && R.isBST && root.data > L.max && root.data < R.min) {
          // Update the number of BSTs
          bst.isBST = true;
          bst.num_BST = 1 + L.num_BST + R.num_BST;
        }
 
        // If the whole tree is not a BST,
        // update the number of BSTs
        else {
          bst.isBST = false;
          bst.num_BST = L.num_BST + R.num_BST;
        }
 
        return bst;
      }
 
      // Driver code
      var 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);
 
      document.write(NumberOfBST(root).num_BST);
       
      // This code is contributed by rdtank.
    </script>
Producción: 

4

 

Publicación traducida automáticamente

Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *