En este artículo, primero se analiza el recuento de posibles BST (árboles de búsqueda binarios), luego se analiza la construcción de todos los BST posibles.
¿Cuántos BST estructuralmente únicos para claves de 1..N?
For example, for N = 2, there are 2 unique BSTs
1 2
\ /
2 1
For N = 3, there are 5 possible BSTs
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Sabemos que todos los Nodes en el subárbol izquierdo son más pequeños que la raíz y en el subárbol derecho son más grandes que la raíz, por lo que si tenemos un i-ésimo número como raíz, todos los números del 1 al i-1 estarán en el subárbol izquierdo y i+1 a N será en el subárbol derecho. Si 1 a i-1 puede formar x árboles diferentes e i+1 a N puede formar desde y árboles diferentes, entonces tendremos x*y árboles en total cuando i-ésimo número sea la raíz y también tenemos N opciones para la raíz, así que simplemente podemos iterar de 1 a N para la raíz y otro bucle para el subárbol izquierdo y derecho. Si miramos más de cerca, podemos notar que la cuenta es básicamente el número catalán n’th . Hemos discutido diferentes enfoques para encontrar el n’ésimo número catalán aquí .
¿Cómo construir todos los BST para las claves 1..N?
La idea es mantener una lista de raíces de todos los BST. Construya recursivamente todos los subárboles izquierdo y derecho posibles. Cree un árbol para cada par de subárboles izquierdo y derecho y agregue el árbol a la lista. A continuación se detalla el algoritmo.
- Inicializa la lista de BST como vacía.
- Para cada número i donde i varía de 1 a N, haga lo siguiente
- Cree un nuevo Node con la clave como ‘i’, deje que este Node sea ‘Node’
- Construya recursivamente una lista de todos los subárboles izquierdos.
- Construya recursivamente una lista de todos los subárboles correctos.
- Iterar para todos los subárboles izquierdos
- Para el subárbol izquierdo actual, iterar para todos los subárboles derechos
- Agregue los subárboles izquierdo y derecho actuales a ‘Node’ y agregue
- Node’ a la lista.
A continuación se muestra la implementación de la idea anterior.
C++
// A C++ program to construct all unique BSTs for keys from 1 to n
#include <bits/stdc++.h>
using namespace std;
// node structure
struct node
{
int key;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = new node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to do preorder traversal of BST
void preorder(struct node *root)
{
if (root != NULL)
{
cout << root->key << " ";
preorder(root->left);
preorder(root->right);
}
}
// function for constructing trees
vector<struct node *> constructTrees(int start, int end)
{
vector<struct node *> list;
/* if start > end then subtree will be empty so returning NULL
in the list */
if (start > end)
{
list.push_back(NULL);
return list;
}
/* iterating through all values from start to end for constructing\
left and right subtree recursively */
for (int i = start; i <= end; i++)
{
/* constructing left subtree */
vector<struct node *> leftSubtree = constructTrees(start, i - 1);
/* constructing right subtree */
vector<struct node *> rightSubtree = constructTrees(i + 1, end);
/* now looping through all left and right subtrees and connecting
them to ith root below */
for (int j = 0; j < leftSubtree.size(); j++)
{
struct node* left = leftSubtree[j];
for (int k = 0; k < rightSubtree.size(); k++)
{
struct node * right = rightSubtree[k];
struct node * node = newNode(i);// making value i as root
node->left = left; // connect left subtree
node->right = right; // connect right subtree
list.push_back(node); // add this tree to list
}
}
}
return list;
}
// Driver Program to test above functions
int main()
{
// Construct all possible BSTs
vector<struct node *> totalTreesFrom1toN = constructTrees(1, 3);
/* Printing preorder traversal of all constructed BSTs */
cout << "Preorder traversals of all constructed BSTs are \n";
for (int i = 0; i < totalTreesFrom1toN.size(); i++)
{
preorder(totalTreesFrom1toN[i]);
cout << endl;
}
return 0;
}
Java
// A Java program to construct all unique BSTs for keys from 1 to n
import java.util.ArrayList;
public class Main {
// function for constructing trees
static ArrayList<Node> constructTrees(int start, int end)
{
ArrayList<Node> list=new ArrayList<>();
/* if start > end then subtree will be empty so returning NULL
in the list */
if (start > end)
{
list.add(null);
return list;
}
/* iterating through all values from start to end for constructing\
left and right subtree recursively */
for (int i = start; i <= end; i++)
{
/* constructing left subtree */
ArrayList<Node> leftSubtree = constructTrees(start, i - 1);
/* constructing right subtree */
ArrayList<Node> rightSubtree = constructTrees(i + 1, end);
/* now looping through all left and right subtrees and connecting
them to ith root below */
for (int j = 0; j < leftSubtree.size(); j++)
{
Node left = leftSubtree.get(j);
for (int k = 0; k < rightSubtree.size(); k++)
{
Node right = rightSubtree.get(k);
Node node = new Node(i); // making value i as root
node.left = left; // connect left subtree
node.right = right; // connect right subtree
list.add(node); // add this tree to list
}
}
}
return list;
}
// A utility function to do preorder traversal of BST
static void preorder(Node root)
{
if (root != null)
{
System.out.print(root.key+" ") ;
preorder(root.left);
preorder(root.right);
}
}
public static void main(String args[])
{
ArrayList<Node> totalTreesFrom1toN = constructTrees(1, 3);
/* Printing preorder traversal of all constructed BSTs */
System.out.println("Preorder traversals of all constructed BSTs are ");
for (int i = 0; i < totalTreesFrom1toN.size(); i++)
{
preorder(totalTreesFrom1toN.get(i));
System.out.println();
}
}
}
// node structure
class Node
{
int key;
Node left, right;
Node(int data)
{
this.key=data;
left=right=null;
}
};
//This code is contributed by Gaurav Tiwari
Python3
# Python3 program to construct all unique
# BSTs for keys from 1 to n
# Binary Tree Node
""" A utility function to create a
new BST node """
class newNode:
# Construct to create a newNode
def __init__(self, item):
self.key=item
self.left = None
self.right = None
# A utility function to do preorder
# traversal of BST
def preorder(root) :
if (root != None) :
print(root.key, end = " " )
preorder(root.left)
preorder(root.right)
# function for constructing trees
def constructTrees(start, end):
list = []
""" if start > end then subtree will be
empty so returning None in the list """
if (start > end) :
list.append(None)
return list
""" iterating through all values from
start to end for constructing
left and right subtree recursively """
for i in range(start, end + 1):
""" constructing left subtree """
leftSubtree = constructTrees(start, i - 1)
""" constructing right subtree """
rightSubtree = constructTrees(i + 1, end)
""" now looping through all left and
right subtrees and connecting
them to ith root below """
for j in range(len(leftSubtree)) :
left = leftSubtree[j]
for k in range(len(rightSubtree)):
right = rightSubtree[k]
node = newNode(i) # making value i as root
node.left = left # connect left subtree
node.right = right # connect right subtree
list.append(node) # add this tree to list
return list
# Driver Code
if __name__ == '__main__':
# Construct all possible BSTs
totalTreesFrom1toN = constructTrees(1, 3)
""" Printing preorder traversal of
all constructed BSTs """
print("Preorder traversals of all",
"constructed BSTs are")
for i in range(len(totalTreesFrom1toN)):
preorder(totalTreesFrom1toN[i])
print()
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to construct all
// unique BSTs for keys from 1 to n
using System.Collections;
using System;
class GFG
{
// function for constructing trees
static ArrayList constructTrees(int start, int end)
{
ArrayList list = new ArrayList();
/* if start > end then subtree will
be empty so returning NULL
in the list */
if (start > end)
{
list.Add(null);
return list;
}
/* iterating through all values from
start to end for constructing\
left and right subtree recursively */
for (int i = start; i <= end; i++)
{
/* constructing left subtree */
ArrayList leftSubtree = constructTrees(start, i - 1);
/* constructing right subtree */
ArrayList rightSubtree = constructTrees(i + 1, end);
/* now looping through all left and
right subtrees and connecting
them to ith root below */
for (int j = 0; j < leftSubtree.Count; j++)
{
Node left = (Node)leftSubtree[j];
for (int k = 0; k < rightSubtree.Count; k++)
{
Node right = (Node)rightSubtree[k];
// making value i as root
Node node = new Node(i);
// connect left subtree
node.left = left;
// connect right subtree
node.right = right;
// Add this tree to list
list.Add(node);
}
}
}
return list;
}
// A utility function to do
// preorder traversal of BST
static void preorder(Node root)
{
if (root != null)
{
Console.Write(root.key+" ") ;
preorder(root.left);
preorder(root.right);
}
}
// Driver code
public static void Main(String []args)
{
ArrayList totalTreesFrom1toN = constructTrees(1, 3);
/* Printing preorder traversal
of all constructed BSTs */
Console.WriteLine("Preorder traversals of all" +
"constructed BSTs are ");
for (int i = 0; i < totalTreesFrom1toN.Count; i++)
{
preorder((Node)totalTreesFrom1toN[i]);
Console.WriteLine();
}
}
// node structure
public class Node
{
public int key;
public Node left, right;
public Node(int data)
{
this.key=data;
left=right=null;
}
};
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// node structure
class Node
{
constructor(data)
{
this.key = data;
this.left = null;
this.right = null;
}
};
// Javascript program to construct all
// unique BSTs for keys from 1 to n
// function for constructing trees
function constructTrees(start, end)
{
var list = [];
/* if start > end then subtree will
be empty so returning NULL
in the list */
if (start > end)
{
list.push(null);
return list;
}
/* iterating through all values from
start to end for constructing\
left and right subtree recursively */
for (var i = start; i <= end; i++)
{
/* constructing left subtree */
var leftSubtree = constructTrees(start, i - 1);
/* constructing right subtree */
var rightSubtree = constructTrees(i + 1, end);
/* now looping through all left and
right subtrees and connecting
them to ith root below */
for (var j = 0; j < leftSubtree.length; j++)
{
var left = leftSubtree[j];
for (var k = 0; k < rightSubtree.length; k++)
{
var right = rightSubtree[k];
// making value i as root
var node = new Node(i);
// connect left subtree
node.left = left;
// connect right subtree
node.right = right;
// push this tree to list
list.push(node);
}
}
}
return list;
}
// A utility function to do
// preorder traversal of BST
function preorder(root)
{
if (root != null)
{
document.write(root.key+" ") ;
preorder(root.left);
preorder(root.right);
}
}
// Driver code
var totalTreesFrom1toN = constructTrees(1, 3);
/* Printing preorder traversal
of all constructed BSTs */
document.write("Preorder traversals of all" +
"constructed BSTs are<br>");
for (var i = 0; i < totalTreesFrom1toN.length; i++)
{
preorder(totalTreesFrom1toN[i]);
document.write("<br>");
}
</script>
Producción
Preorder traversals of all constructed BSTs are 1 2 3 1 3 2 2 1 3 3 1 2 3 2 1
Este artículo es una contribución de Utkarsh Trivedi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA