печать всех двоичных деревьев из обхода по порядку

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 ветви (дочерние элементы, или).Мы можем расположить эти 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

Эта проблема довольно хорошо разбивается на подзадачи.Учитывая прохождение по порядку, после выбора корня мы знаем, что все, что до этого, является левым поддеревом, а все, что после, является правым поддеревом (либо, возможно, пусто).

Итак, чтобы перечислить все возможные деревья, мы просто пробуем всевозможные значения для корня и рекурсивное решение для левого и правого поддеревьев (хотя количество таких деревьев растет довольно быстро!)

предоставил код antonakos, который показывает, как это сделать, хотя это решение может использовать больше памяти, чемжелательно.Эту проблему можно решить, добавив больше состояния в рекурсию, чтобы не было необходимости сохранять списки ответов для левого и правого каналов и объединять их в конце;вместо этого вложив эти процессы и распечатав каждое дерево, как оно найдено.

Answer 2

Я бы написал одну функцию для построения деревьев и другую для их печати. ​​

Конструкция деревьев выглядит так:

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