imprimiendo todos los árboles binarios de inorder transversal

Question

Encontré esta pregunta en una entrevista. Dado inorder transversal de un árbol binario. Imprime todos los árboles binarios posibles de él.

pensamiento inicial:

Si decimos que tenemos sólo 2 elementos de la matriz. Digamos 2,1. Entonces dos árboles son posibles

   2 
       \ 
       1  
    1 
/
    2 

Si 3 elementos Say, 2,1,4. Entonces tenemos 5 árboles posibles.

2    1   4   2   4 
    \   /\  /   \  /
    1   2 4  1    4  2 
    \     /   /  \ 
    4     2    1   1 

Así que, básicamente si tenemos n elementos, entonces tenemos n-1 ramas (hijos,/o). Podemos organizar estas ramas n-1 en cualquier orden. Para n = 3, n-1 = 2. Entonces, tenemos 2 ramas. Podemos organizar las 2 ramas de las siguientes maneras:

/ \   \   /  /\ 
/  \  /   \ 

intento inicial:

struct node *findTree(int *A,int l,int h) 
{ 
    node *root = NULL; 
    if(h < l) 
      return NULL; 
    for(int i=l;i<h;i++) 
    { 
      root = newNode(A[i]); 
      root->left = findTree(A,l,i-1); 
      root->right = findTree(A,i+1,h); 
      printTree(root); 
      cout<<endl; 
    } 

} 

Answer 1

me gustaría escribir una función para la construcción de los árboles y otro para imprimirlos.

La construcción de los árboles es la siguiente:

#include <vector> 
#include <iostream> 
#include <boost/foreach.hpp> 

struct Tree { 
    int value; 
    Tree* left; 
    Tree* right; 

    Tree(int value, Tree* left, Tree* right) : 
     value(value), left(left), right(right) {} 
}; 

typedef std::vector<Tree*> Seq; 

Seq all_trees(const std::vector<int>& xs, int from, int to) 
{ 
    Seq result; 
    if (from >= to) result.push_back(0); 
    else { 
     for (int i = from; i < to; i++) { 
      const Seq left = all_trees(xs, from, i); 
      const Seq right = all_trees(xs, i + 1, to); 
      BOOST_FOREACH(Tree* tl, left) { 
       BOOST_FOREACH(Tree* tr, right) { 
        result.push_back(new Tree(xs[i], tl, tr)); 
       } 
      } 
     } 
    } 
    return result; 
} 

Seq all_trees(const std::vector<int>& xs) 
{ 
    return all_trees(xs, 0, (int)xs.size()); 
} 

Observe que en valor de la raíz hay varios árboles que se construyen a partir de los valores a la izquierda y la derecha del valor de la raíz. Todas las combinaciones de estos árboles izquierdos y derechos están incluidos.

Escribiendo el bonito-impresora se deja como ejercicio (una aburrida), pero podemos probar que la función de hecho construye el número esperado de árboles:

int main() 
{ 
    const std::vector<int> xs(3, 0); // 3 values gives 5 trees. 
    const Seq result = all_trees(xs); 
    std::cout << "Number of trees: " << result.size() << "\n"; 
} 

Answer 2

Este problema se rompe bastante bien en subproblemas . Dado un recorrido inorden, después de elegir una raíz sabemos que todo lo anterior es el subárbol izquierdo y todo lo demás es el subárbol correcto (posiblemente esté vacío).

Así que para enumerar todos los árboles posibles, solo tratamos todos los valores posibles de la raíz y de forma recursiva a resolver para los & subárboles derecha e izquierda (el número de estos árboles crece muy rápidamente sin embargo!)

Antonakos código, siempre que espectáculos cómo hacer esto, aunque esa solución puede usar más memoria de la deseable. Esto se puede solucionar agregando más estado a la recursión, por lo que no tiene que guardar las listas de las respuestas para el & izquierdo y combinarlas al final; en su lugar, anida estos procesos e imprime cada árbol tal como se encuentra.