inorder traversalからのすべてのバイナリツリーを印刷します

Question

インタビューでこの質問に出てきました。 2進ツリーのinorderトラバーサルを指定します。バイナリツリーをすべて印刷します。

最初の考え：

たとえば、配列に2つの要素しかないとします。 2・1と言う。 次に、2本の可能な木3つの要素が言えば、

   2 
       \ 
       1  
    1 
/
    2 

ある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

私はそれらを印刷するための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について解きますこれを行う方法ですが、その解決策は望ましい以上に多くのメモリを使用するかもしれません。これは再帰に状態を追加することで対処できるので、左側の&の回答のリストを保存して最後に結合する必要はありません。代わりにこれらのプロセスを入れ子にし、各ツリーを見つかったものとして印刷します。