从inorder遍历打印所有二叉树

Question

在接受采访时遇到了这个问题.给定遍历二叉树的顺序.从中打印所有可能的二叉树.

初步想法:

如果说我们在数组中只有2个元素.说2,1.然后是两棵可能的树

              2 
               \
                1     
    1
   /
   2  

如果3个元素说,2,1,4.然后我们有5棵树.

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

所以,基本上如果我们有n个元素,那么我们有n-1个分支(childs,/或).我们可以按任何顺序安排这些n-1个分支.对于n = 3,n-1 = 2.因此,我们有2个分支.我们可以通过以下方式安排2个分支:

  /     \         \           /         /\
 /       \        /           \

初步尝试:

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

我会编写一个用于构建树的函数，另一个用于打印它们。

树的构建过程如下：

#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());
}

观察到对于根值，有多个树是根据根值左侧和右侧的值构造的。包括这些左树和右树的所有组合。

编写漂亮的打印机作为一项练习（无聊的练习），但我们可以测试该函数确实构造了预期数量的树：

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";
}