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

Нашел этот вопрос в интервью. Представление обхода двоичного дерева. Распечатайте все возможные бинарные деревья из него.

Первоначальная мысль:

Если говорят, что в массиве всего 2 элемента. Скажем 2,1. Тогда два возможных дерева:

Если 3 элемента Say, 2,1,4. Тогда у нас есть 5 возможных деревьев.

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

Итак, в основном, если у нас есть n элементов, то у нас есть n-1 ветки (childs,/or). Мы можем расположить эти n-1 ветки в любом порядке. При n = 3, n-1 = 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;
    }

}

Ответ 1

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

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

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

Ответ 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";
}