Dado un número entero N , la tarea es imprimir todos los árboles binarios completos posibles con N Nodes. El valor en los Nodes no contribuye a ser un criterio para diferentes árboles binarios completos, excepto NULL, así que tómelos como 0.
Un árbol binario completo es un árbol binario en el que cada Node tiene exactamente 0 o 2 hijos.
Ejemplos:
Entrada: N = 7
Salida: [[0, 0, 0, nulo, nulo, 0, 0, nulo, nulo, 0, 0, nulo, nulo, nulo, nulo],
[0, 0, 0, nulo, nulo , 0, 0, 0, 0, nulo, nulo, nulo, nulo, nulo, nulo],
[0, 0, 0, 0, 0, nulo, nulo, nulo, nulo, 0, 0, nulo, nulo, nulo , nulo],
[0, 0, 0, 0, 0, nulo, nulo, 0, 0, nulo, nulo, nulo, nulo, nulo, nulo],
[0, 0, 0, 0, 0, 0, 0 , nulo, nulo, nulo, nulo, nulo, nulo, nulo, nulo]]
Explicación: Los posibles árboles binarios completos son –
0 | 0 | 0 | 0 | 0
/ \ | / \ | / \ | / \ | / \
0 0 | 0 0 | 0 0 | 0 0 | 0 0
/ \ | / \ | / \ | / \ | / \ / \
0 0 | 0 0 | 0 0 | 0 0 | 0 0 0 0
/ \ | / \ | / \ | / \ |
0 0 | 0 0 | 0 0 | 0 0 |Entrada: N = 5
Salida: [[0, 0, 0, nulo, nulo, 0, 0, nulo, nulo, nulo, nulo],
[0, 0, 0, 0, 0, nulo, nulo, nulo, nulo , nulo, nulo]]Entrada: N = 9
Salida: [[0,0,0,null,null,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0, nulo, nulo, 0,0,0,0], [0,0,0, nulo, nulo, 0,0,0,0,0,0], [0,0,0, nulo, nulo, 0, 0,0,0,null,null,null,null,0,0],[0,0,0,null,null,0,0,0,0,null,null,0,0],[0, 0,0,0,0,0,0,null,null,null,null,null,null,0,0],[0,0,0,0,0,0,0,null,null,null, nulo,0,0],[0,0,0,0,0,0,0,nulo,nulo,0,0],[0,0,0,0,0,0,0,0,0] ,[0,0,0,0,0,null,null,null,null,0,0,null,null,0,0],[0,0,0,0,0,null,null,null, nulo,0,0,0,0],[0,0,0,0,0,nulo,nulo,0,0,0,0],[0,0,0,0,0,nulo,nulo, 0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0,null,null,0,0]]
Enfoque: la forma más sencilla de resolver el problema es utilizar la recursividad utilizando el concepto de memoización y verificar para cada subárbol si hay un número impar de Nodes o no porque un árbol binario completo tiene Nodes impares. Siga los pasos a continuación para resolver el problema:
- Inicialice un hashMap , digamos hm que almacena todo el árbol binario completo .
- Cree una función, diga allPossibleBFT con el parámetro como N realizando los siguientes pasos:
- Cree una lista, digamos una lista que contenga los Nodes de clase.
- Si N = 1 , agregue Nodes (0, NULL, NULL) en la lista.
- Ahora verifique si N es impar, luego itere en el rango [0, N-1] usando la variable x y realice los siguientes pasos:
- Inicialice una variable, digamos y como N – 1 – x .
- Llame recursivamente a la función allPossibleBFT con x como parámetro y asígnela al Node left .
- Llame recursivamente a la función allPossibleBFT con y como parámetro dentro de la llamada anterior y asígnela al Node right .
- Ahora cree un nuevo Node con parámetros como (0, NULL, NULL).
- Asigne Node.left como izquierda y Node.right como derecha .
- Agregar Node a la lista.
- Después de realizar los pasos anteriores, inserte la lista en el hashMap hm .
- Después de realizar todos los pasos, imprima los árboles binarios completos que se encuentran en la lista.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Class for creating node and
// its left and right child
struct Node {
Node* left;
Node* right;
int data;
Node(int data, Node* left, Node* right)
{
this->data = data;
this->left = left;
this->right = right;
}
};
// Function to traverse the tree and add all
// the left and right child in the list al
void display(Node* node, vector<int> &al)
{
// If node = null then terminate the function
if (node == nullptr) {
return;
}
// If there is left child of Node node
// then insert it into the list al
if (node->left != nullptr) {
al.push_back(node->left->data);
}
// Otherwise insert null in the list
else {
al.push_back(INT_MIN);
}
// Similarly, if there is right child
// of Node node then insert it into
// the list al
if (node->right != nullptr) {
al.push_back(node->right->data);
}
// Otherwise insert null
else {
al.push_back(INT_MIN);
}
// Recursively call the function
// for left child and right child
// of the Node node
display(node->left, al);
display(node->right, al);
}
// Save tree for all n before recursion.
map<int, vector<Node*>> hm;
vector<Node*> allPossibleFBT(int n)
{
// Check whether tree exists for given n value or not.
if (hm.find(n) == hm.end())
{
// Create a list containing nodes
vector<Node*> list;
// If N=1, Only one tree can exist
// i.e. tree with root.
if (n == 1) {
list.push_back(new Node(0, nullptr, nullptr));
}
// Check if N is odd because binary full
// tree has N nodes
else if (n % 2 == 1) {
// Iterate through all the nodes that
// can be in the left subtree
for (int x = 0; x < n; x++) {
// Remaining Nodes belongs to the
// right subtree of the node
int y = n - 1 - x;
// Iterate through all left Full Binary Tree
// by recursively calling the function
vector<Node*> xallPossibleFBT = allPossibleFBT(x);
vector<Node*> yallPossibleFBT = allPossibleFBT(y);
for(int Left = 0; Left < xallPossibleFBT.size(); Left++) {
// Iterate through all the right Full
// Binary tree by recursively calling
// the function
for(int Right = 0; Right < yallPossibleFBT.size(); Right++) {
// Create a new node
Node* node = new Node(0, nullptr, nullptr);
// Modify the left node
node->left = xallPossibleFBT[Left];
// Modify the right node
node->right = yallPossibleFBT[Right];
// Add the node in the list
list.push_back(node);
}
}
}
}
//Insert tree in Dictionary.
hm.insert({n, list});
}
return hm[n];
}
int main()
{
// You can take n as input from user
// Here we take n as 7 for example purpose
int n = 7;
// Function Call
vector<Node*> list = allPossibleFBT(n);
// Print all possible binary full trees
for(int root = 0; root < list.size(); root++) {
vector<int> al;
al.push_back((list[root])->data);
display(list[root], al);
cout << "[";
for(int i = 0; i < al.size(); i++)
{
if(i != al.size() - 1)
{
if(al[i]==INT_MIN)
cout << "null, ";
else
cout << al[i] << ", ";
}
else{
if(al[i]==INT_MIN)
cout << "null]";
else
cout << al[i] << "]";
}
}
cout << endl;
}
return 0;
}
// This code is contributed by decode2207.
Java
// JAVA program for the above approach
import java.util.*;
import java.io.*;
class GFG {
// Class for creating node and
// its left and right child
public static class Node {
int data;
Node left;
Node right;
Node(int data, Node left, Node right)
{
this.data = data;
this.left = left;
this.right = right;
}
}
// Function to traverse the tree and add all
// the left and right child in the list al
public static void display(Node node, List<Integer> al)
{
// If node = null then terminate the function
if (node == null) {
return;
}
// If there is left child of Node node
// then insert it into the list al
if (node.left != null) {
al.add(node.left.data);
}
// Otherwise insert null in the list
else {
al.add(null);
}
// Similarly, if there is right child
// of Node node then insert it into
// the list al
if (node.right != null) {
al.add(node.right.data);
}
// Otherwise insert null
else {
al.add(null);
}
// Recursively call the function
// for left child and right child
// of the Node node
display(node.left, al);
display(node.right, al);
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int n = 7;
// Function Call
List<Node> list = allPossibleFBT(n);
// Print all possible binary full trees
for (Node root: list) {
List<Integer> al = new ArrayList<>();
al.add(root.data);
display(root, al);
System.out.println(al);
}
}
// Save tree for all n before recursion.
static HashMap<Integer, List<Node> > hm = new HashMap<>();
public static List<Node> allPossibleFBT(int n)
{
// Check whether tree exists for given n value or not.
if (!hm.containsKey(n)) {
// Create a list containing nodes
List<Node> list = new LinkedList<>();
// If N=1, Only one tree can exist
// i.e. tree with root.
if (n == 1) {
list.add(new Node(0, null, null));
}
// Check if N is odd because binary full
// tree has N nodes
else if (n % 2 == 1) {
// Iterate through all the nodes that
// can be in the left subtree
for (int x = 0; x < n; x++) {
// Remaining Nodes belongs to the
// right subtree of the node
int y = n - 1 - x;
// Iterate through all left Full Binary Tree
// by recursively calling the function
for (Node left: allPossibleFBT(x)) {
// Iterate through all the right Full
// Binary tree by recursively calling
// the function
for (Node right: allPossibleFBT(y)) {
// Create a new node
Node node = new Node(0, null, null);
// Modify the left node
node.left = left;
// Modify the right node
node.right = right;
// Add the node in the list
list.add(node);
}
}
}
}
//Insert tree in HashMap.
hm.put(n, list);
}
return hm.get(n);
}
}
Python3
# Python3 program for the above approach
import sys
# Class for creating node and
# its left and right child
class Node:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
# Function to traverse the tree and add all
# the left and right child in the list al
def display(node, al):
# If node = null then terminate the function
if (node == None):
return
# If there is left child of Node node
# then insert it into the list al
if (node.left != None):
al.append(node.left.data)
# Otherwise insert null in the list
else:
al.append(-sys.maxsize)
# Similarly, if there is right child
# of Node node then insert it into
# the list al
if (node.right != None):
al.append(node.right.data)
# Otherwise insert null
else:
al.append(-sys.maxsize)
# Recursively call the function
# for left child and right child
# of the Node node
display(node.left, al)
display(node.right, al)
# Save tree for all n before recursion.
hm = {}
def allPossibleFBT(n):
# Check whether tree exists for given n value or not.
if n not in hm:
# Create a list containing nodes
List = []
# If N=1, Only one tree can exist
# i.e. tree with root.
if (n == 1):
List.append(Node(0, None, None))
# Check if N is odd because binary full
# tree has N nodes
elif (n % 2 == 1):
# Iterate through all the nodes that
# can be in the left subtree
for x in range(n):
# Remaining Nodes belongs to the
# right subtree of the node
y = n - 1 - x
# Iterate through all left Full Binary Tree
# by recursively calling the function
xallPossibleFBT = allPossibleFBT(x)
yallPossibleFBT = allPossibleFBT(y)
for Left in range(len(xallPossibleFBT)):
# Iterate through all the right Full
# Binary tree by recursively calling
# the function
for Right in range(len(yallPossibleFBT)):
# Create a new node
node = Node(0, None, None)
# Modify the left node
node.left = xallPossibleFBT[Left]
# Modify the right node
node.right = yallPossibleFBT[Right]
# Add the node in the list
List.append(node)
#Insert tree in Dictionary.
hm[n] = List
return hm[n]
# Given Input
n = 7
# Function Call
List = allPossibleFBT(n)
# Print all possible binary full trees
for root in range(len(List)):
al = []
al.append(List[root].data)
display(List[root], al)
print("[", end = "")
for i in range(len(al)):
if(i != len(al) - 1):
if(al[i]==-sys.maxsize):
print("null, ", end = "")
else:
print(al[i], end = ", ")
else:
if(al[i]==-sys.maxsize):
print("null]", end = "")
else:
print(al[i], end = "]")
print()
# This code is contributed by mukesh07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Class for creating node and
// its left and right child
public class Node {
public int data;
public Node left;
public Node right;
public Node(int data, Node left, Node right)
{
this.data = data;
this.left = left;
this.right = right;
}
}
// Function to traverse the tree and add all
// the left and right child in the list al
public static void display(Node node, List<int> al)
{
// If node = null then terminate the function
if (node == null) {
return;
}
// If there is left child of Node node
// then insert it into the list al
if (node.left != null) {
al.Add(node.left.data);
}
// Otherwise insert null in the list
else {
al.Add(int.MinValue);
}
// Similarly, if there is right child
// of Node node then insert it into
// the list al
if (node.right != null) {
al.Add(node.right.data);
}
// Otherwise insert null
else {
al.Add(int.MinValue);
}
// Recursively call the function
// for left child and right child
// of the Node node
display(node.left, al);
display(node.right, al);
}
// Driver Code
public static void Main(String[] args)
{
// Given Input
int n = 7;
// Function Call
List<Node> list = allPossibleFBT(n);
// Print all possible binary full trees
foreach (Node root in list) {
List<int> al = new List<int>();
al.Add(root.data);
display(root, al);
foreach (int i in al){
if(i==int.MinValue)
Console.Write("null, ");
else
Console.Write(i+", ");
}
Console.WriteLine();
}
}
// Save tree for all n before recursion.
static Dictionary<int, List<Node> > hm = new Dictionary<int, List<Node> >();
public static List<Node> allPossibleFBT(int n)
{
// Check whether tree exists for given n value or not.
if (!hm.ContainsKey(n)) {
// Create a list containing nodes
List<Node> list = new List<Node>();
// If N=1, Only one tree can exist
// i.e. tree with root.
if (n == 1) {
list.Add(new Node(0, null, null));
}
// Check if N is odd because binary full
// tree has N nodes
else if (n % 2 == 1) {
// Iterate through all the nodes that
// can be in the left subtree
for (int x = 0; x < n; x++) {
// Remaining Nodes belongs to the
// right subtree of the node
int y = n - 1 - x;
// Iterate through all left Full Binary Tree
// by recursively calling the function
foreach (Node left in allPossibleFBT(x)) {
// Iterate through all the right Full
// Binary tree by recursively calling
// the function
foreach (Node right in allPossibleFBT(y)) {
// Create a new node
Node node = new Node(0, null, null);
// Modify the left node
node.left = left;
// Modify the right node
node.right = right;
// Add the node in the list
list.Add(node);
}
}
}
}
//Insert tree in Dictionary.
hm.Add(n, list);
}
return hm[n];
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Class for creating node and
// its left and right child
class Node
{
constructor(data, left, right) {
this.left = left;
this.right = right;
this.data = data;
}
}
// Function to traverse the tree and add all
// the left and right child in the list al
function display(node, al)
{
// If node = null then terminate the function
if (node == null) {
return;
}
// If there is left child of Node node
// then insert it into the list al
if (node.left != null) {
al.push(node.left.data);
}
// Otherwise insert null in the list
else {
al.push(Number.MIN_VALUE);
}
// Similarly, if there is right child
// of Node node then insert it into
// the list al
if (node.right != null) {
al.push(node.right.data);
}
// Otherwise insert null
else {
al.push(Number.MIN_VALUE);
}
// Recursively call the function
// for left child and right child
// of the Node node
display(node.left, al);
display(node.right, al);
}
// Save tree for all n before recursion.
let hm = new Map();
function allPossibleFBT(n)
{
// Check whether tree exists for given n value or not.
if (!hm.has(n)) {
// Create a list containing nodes
let list = [];
// If N=1, Only one tree can exist
// i.e. tree with root.
if (n == 1) {
list.push(new Node(0, null, null));
}
// Check if N is odd because binary full
// tree has N nodes
else if (n % 2 == 1) {
// Iterate through all the nodes that
// can be in the left subtree
for (let x = 0; x < n; x++) {
// Remaining Nodes belongs to the
// right subtree of the node
let y = n - 1 - x;
// Iterate through all left Full Binary Tree
// by recursively calling the function
let xallPossibleFBT = allPossibleFBT(x);
let yallPossibleFBT = allPossibleFBT(y);
for(let Left = 0; Left < xallPossibleFBT.length; Left++) {
// Iterate through all the right Full
// Binary tree by recursively calling
// the function
for(let Right = 0; Right < yallPossibleFBT.length; Right++) {
// Create a new node
let node = new Node(0, null, null);
// Modify the left node
node.left = xallPossibleFBT[Left];
// Modify the right node
node.right = yallPossibleFBT[Right];
// Add the node in the list
list.push(node);
}
}
}
}
//Insert tree in Dictionary.
hm.set(n, list);
}
return hm.get(n);
}
// Given Input
let n = 7;
// Function Call
let list = allPossibleFBT(n);
// Print all possible binary full trees
for(let root = 0; root < list.length; root++) {
let al = [];
al.push(list[root].data);
display(list[root], al);
document.write("[");
for(let i = 0; i < al.length; i++){
if(i != al.length - 1)
{
if(al[i]==Number.MIN_VALUE)
document.write("null, ");
else
document.write(al[i]+ ", ");
}
else{
if(al[i]==Number.MIN_VALUE)
document.write("null]");
else
document.write(al[i]+ "]");
}
}
document.write("</br>");
}
// This code is contributed by divyeshrabadiya07.
</script>
Producción
[0, 0, 0, null, null, 0, 0, null, null, 0, 0, null, null, null, null] [0, 0, 0, null, null, 0, 0, 0, 0, null, null, null, null, null, null] [0, 0, 0, 0, 0, null, null, null, null, 0, 0, null, null, null, null] [0, 0, 0, 0, 0, null, null, 0, 0, null, null, null, null, null, null] [0, 0, 0, 0, 0, 0, 0, null, null, null, null, null, null, null, null]
Complejidad de tiempo: O(2 N )
Complejidad de espacio: O(2 N )