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

Question

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

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

Если у нас есть только два элемента в массиве. Скажем 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,/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; 
    } 

} 

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

Answer 2

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

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

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