Dada una array que representa el recorrido en orden, encuentre todos los árboles binarios posibles con el recorrido en orden dado e imprima sus recorridos en preorden.
Ejemplos:
Input: in[] = {3, 2};
Output: Preorder traversals of different possible Binary Trees are:
3 2
2 3
Below are different possible binary trees
3 2
\ /
2 3
Input: in[] = {4, 5, 7};
Output: Preorder traversals of different possible Binary Trees are:
4 5 7
4 7 5
5 4 7
7 4 5
7 5 4
Below are different possible binary trees
4 4 5 7 7
\ \ / \ / /
5 7 4 7 4 5
\ / \ /
7 5 5 4
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Deje que el recorrido en orden dado esté en [] . En el recorrido dado, todos los Nodes en el subárbol izquierdo de in[i] deben aparecer antes y en el subárbol derecho deben aparecer después. Entonces, cuando consideramos in[i] como raíz, todos los elementos desde in[0] hasta in[i-1] estarán en el subárbol izquierdo e in[i+1] hasta n-1 estarán en el subárbol derecho. Si in[0] a in[i-1] pueden formar x árboles diferentes e in[i+1] a in[n-1] pueden formar y árboles diferentes entonces tendremos x*yárboles totales cuando están en [i] como raíz. Así que simplemente iteramos de 0 a n-1 para root. Para cada Node en [i], encuentre recursivamente diferentes subárboles izquierdo y derecho. Si echamos un vistazo más de cerca, podemos notar que la cuenta es básicamente el n’ésimo número catalán . Hemos discutido diferentes enfoques para encontrar el n’ésimo número catalán aquí .
La idea es mantener una lista de raíces de todos los árboles binarios. 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.
1) Initialize list of Binary Trees as empty.
2) For every element in[i] where i varies from 0 to n-1,
do following
......a) Create a new node with key as 'arr[i]',
let this node be 'node'
......b) Recursively construct list of all left subtrees.
......c) Recursively construct list of all right subtrees.
3) Iterate for all left subtrees
a) For current leftsubtree, iterate for all right subtrees
Add current left and right subtrees to 'node' and add
'node' to list.
C++
// C++ program to find binary tree with given inorder
// traversal
#include <bits/stdc++.h>
using namespace std;
// Node structure
struct Node
{
int key;
struct Node *left, *right;
};
// A utility function to create a new tree 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(Node *root)
{
if (root != NULL)
{
printf("%d ", root->key);
preorder(root->left);
preorder(root->right);
}
}
// Function for constructing all possible trees with
// given inorder traversal stored in an array from
// arr[start] to arr[end]. This function returns a
// vector of trees.
vector<Node *> getTrees(int arr[], int start, int end)
{
// List to store all possible trees
vector<Node *> trees;
/* if start > end then subtree will be empty so
returning NULL in the list */
if (start > end)
{
trees.push_back(NULL);
return trees;
}
/* 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<Node *> ltrees = getTrees(arr, start, i-1);
/* Constructing right subtree */
vector<Node *> rtrees = getTrees(arr, i+1, end);
/* Now looping through all left and right subtrees
and connecting them to ith root below */
for (int j = 0; j < ltrees.size(); j++)
{
for (int k = 0; k < rtrees.size(); k++)
{
// Making arr[i] as root
Node * node = newNode(arr[i]);
// Connecting left subtree
node->left = ltrees[j];
// Connecting right subtree
node->right = rtrees[k];
// Adding this tree to list
trees.push_back(node);
}
}
}
return trees;
}
// Driver Program to test above functions
int main()
{
int in[] = {4, 5, 7};
int n = sizeof(in) / sizeof(in[0]);
vector<Node *> trees = getTrees(in, 0, n-1);
cout << "Preorder traversals of different "
<< "possible Binary Trees are \n";
for (int i = 0; i < trees.size(); i++)
{
preorder(trees[i]);
printf("\n");
}
return 0;
}
Java
// Java program to find binary tree with given inorder
// traversal
import java.util.Vector;
/* Class containing left and right child of current
node and key value*/
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = null;
right = null;
}
}
/* Class to print Level Order Traversal */
class BinaryTree {
Node root;
// A utility function to do preorder traversal of BST
void preOrder(Node node) {
if (node != null) {
System.out.print(node.data + " " );
preOrder(node.left);
preOrder(node.right);
}
}
// Function for constructing all possible trees with
// given inorder traversal stored in an array from
// arr[start] to arr[end]. This function returns a
// vector of trees.
Vector<Node> getTrees(int arr[], int start, int end) {
// List to store all possible trees
Vector<Node> trees= new Vector<Node>();
/* if start > end then subtree will be empty so
returning NULL in the list */
if (start > end) {
trees.add(null);
return trees;
}
/* 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<Node> ltrees = getTrees(arr, start, i - 1);
/* Constructing right subtree */
Vector<Node> rtrees = getTrees(arr, i + 1, end);
/* Now looping through all left and right subtrees
and connecting them to ith root below */
for (int j = 0; j < ltrees.size(); j++) {
for (int k = 0; k < rtrees.size(); k++) {
// Making arr[i] as root
Node node = new Node(arr[i]);
// Connecting left subtree
node.left = ltrees.get(j);
// Connecting right subtree
node.right = rtrees.get(k);
// Adding this tree to list
trees.add(node);
}
}
}
return trees;
}
public static void main(String args[]) {
int in[] = {4, 5, 7};
int n = in.length;
BinaryTree tree = new BinaryTree();
Vector<Node> trees = tree.getTrees(in, 0, n - 1);
System.out.println("Preorder traversal of different "+
" binary trees are:");
for (int i = 0; i < trees.size(); i++) {
tree.preOrder(trees.get(i));
System.out.println("");
}
}
}
Python3
# Python program to find binary tree with given
# inorder traversal
# Node Structure
class Node:
# Utility to create a new node
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 is not None:
print (root.key,end=" ")
preorder(root.left)
preorder(root.right)
# Function for constructing all possible trees with
# given inorder traversal stored in an array from
# arr[start] to arr[end]. This function returns a
# vector of trees.
def getTrees(arr , start , end):
# List to store all possible trees
trees = []
""" if start > end then subtree will be empty so
returning NULL in the list """
if start > end :
trees.append(None)
return trees
""" 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
ltrees = getTrees(arr , start , i-1)
# Constructing right subtree
rtrees = getTrees(arr , i+1 , end)
""" Looping through all left and right subtrees
and connecting to ith root below"""
for j in ltrees :
for k in rtrees :
# Making arr[i] as root
node = Node(arr[i])
# Connecting left subtree
node.left = j
# Connecting right subtree
node.right = k
# Adding this tree to list
trees.append(node)
return trees
# Driver program to test above function
inp = [4 , 5, 7]
n = len(inp)
trees = getTrees(inp , 0 , n-1)
print ("Preorder traversals of different possible\
Binary Trees are ")
for i in trees :
preorder(i);
print ("")
# This program is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to find binary tree
// with given inorder traversal
using System;
using System.Collections.Generic;
/* Class containing left and right
child of current node and key value*/
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = null;
right = null;
}
}
/* Class to print Level Order Traversal */
class GFG
{
public Node root;
// A utility function to do
// preorder traversal of BST
public virtual void preOrder(Node node)
{
if (node != null)
{
Console.Write(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
}
// Function for constructing all possible
// trees with given inorder traversal
// stored in an array from arr[start] to
// arr[end]. This function returns a
// vector of trees.
public virtual List<Node> getTrees(int[] arr,
int start,
int end)
{
// List to store all possible trees
List<Node> trees = new List<Node>();
/* if start > end then subtree will be
empty so returning NULL in the list */
if (start > end)
{
trees.Add(null);
return trees;
}
/* 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 */
List<Node> ltrees = getTrees(arr, start, i - 1);
/* Constructing right subtree */
List<Node> rtrees = getTrees(arr, i + 1, end);
/* Now looping through all left and
right subtrees and connecting them
to ith root below */
for (int j = 0; j < ltrees.Count; j++)
{
for (int k = 0; k < rtrees.Count; k++)
{
// Making arr[i] as root
Node node = new Node(arr[i]);
// Connecting left subtree
node.left = ltrees[j];
// Connecting right subtree
node.right = rtrees[k];
// Adding this tree to list
trees.Add(node);
}
}
}
return trees;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = new int[] {4, 5, 7};
int n = arr.Length;
GFG tree = new GFG();
List<Node> trees = tree.getTrees(arr, 0, n - 1);
Console.WriteLine("Preorder traversal of different " +
" binary trees are:");
for (int i = 0; i < trees.Count; i++)
{
tree.preOrder(trees[i]);
Console.WriteLine("");
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to find binary tree
// with given inorder traversal
/* Class containing left and right
child of current node and key value*/
class Node
{
constructor(item)
{
this.data = item;
this.left = null;
this.right = null;
}
}
/* Class to print Level Order Traversal */
var root = null;
// A utility function to do
// preorder traversal of BST
function preOrder(node)
{
if (node != null)
{
document.write(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
}
// Function for constructing all possible
// trees with given inorder traversal
// stored in an array from arr[start] to
// arr[end]. This function returns a
// vector of trees.
function getTrees(arr, start, end)
{
// List to store all possible trees
var trees = [];
/* if start > end then subtree will be
empty so returning NULL in the list */
if (start > end)
{
trees.push(null);
return trees;
}
/* 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 ltrees = getTrees(arr, start, i - 1);
/* Constructing right subtree */
var rtrees = getTrees(arr, i + 1, end);
/* Now looping through all left and
right subtrees and connecting them
to ith root below */
for (var j = 0; j < ltrees.length; j++)
{
for (var k = 0; k < rtrees.length; k++)
{
// Making arr[i] as root
var node = new Node(arr[i]);
// Connecting left subtree
node.left = ltrees[j];
// Connecting right subtree
node.right = rtrees[k];
// Adding this tree to list
trees.push(node);
}
}
}
return trees;
}
// Driver Code
var arr = [4, 5, 7];
var n = arr.length;
var trees = getTrees(arr, 0, n - 1);
document.write("Preorder traversal of different " +
" binary trees are:<br>");
for(var i = 0; i < trees.length; i++)
{
preOrder(trees[i]);
document.write("<br>");
}
// This code is contributed by rrrtnx.
</script>
Producción:
Preorder traversals of different possible Binary Trees are 4 5 7 4 7 5 5 4 7 7 4 5 7 5 4
Gracias a Utkarsh por sugerir la solución anterior.
Este problema es similar al problema discutido aquí .
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