可能なすべてのバイナリツリーを生成します。

Question

タイトルは、以下の2番目のリンクの例のように、可能な限りすべてのバイナリツリーを生成するアルゴリズムを誰もが知っていますか？

` N     N     N 
/\    /\     /\ 
N N    N N    N N 
/\ /\    /\      /\ 
N N N N   N N     N N 
       /\      /\ 
        N N      N N 

I'veはすでにthis、this、thisとthisに行ったことが、私はそれぞれを実装しようとしていると、彼らは - 私が探していたり​​、適切に説明されていない何ドント。最初にすべての可能な文字列を生成し、その後それらをツリー型（親子関係）に解析しなければならない場合、最初のものは多くの計算であり、2番目のものはすべてのツリーを出力しません。たとえば、上記の例のように3つの内部ノードを指定して実行すると、1つのツリー（左側のツリー）が表示されます。カタロニア語の数について調べてみると、少数のノードであってもツリーの数は大きく増えるが、ノード数が少ない場合は便利なツールであることがわかっている。事前に感謝します

Answer 1

私はすべてのあなたのリンクをチェックしていませんでしたが、それらのいくつかはいくつかの便利なアイデアを持っているようです。あなたの質問に答えるために、いいえ、私はアルゴリズムを知らないが、それは1つを考案することがあまりにも難しいとは思いません。上記で

List<TreeNode> allBinaryTrees(int numberOfLeaves) { 
    if (numberOfLeaves < 1) { 
     throw new IllegalArgumentException("Number of leaves must be positive"); 
    } 
    List<TreeNode> result = new ArrayList<>(); 
    if (numberOfLeaves == 1) { 
     // return a single tree consisting of a single leaf node 
     result.add(new Leaf()); 
     return result; 
    } 
    for (int sizeOfLeftSubtree = 1; sizeOfLeftSubtree < numberOfLeaves - 1; sizeOfLeftSubtree++) { 
     List<TreeNode> possibleLeftSubtrees = allBinaryTrees(sizeOfLeftSubtree); 
     List<TreeNode> possibleRightSubtrees = allBinaryTrees(numberOfLeaves - sizeOfLeftSubtree); 
     for (TreeNode lt : possibleLeftSubtrees) { 
      for (TreeNode rt : possibleRightSubtrees) { 
       // make a tree of a node with lt and rt as subtrees, 
       // and add it to the result 
       result.add(new InternalNode(lt, rt)); 
      } 
     } 
    } 
    return result; 
} 

IはInternalNodeとLeafはTreeNodeの両方のサブクラスであると仮定しています。別のデザインが必要な場合があります。私はあなたが対応してコードを調整できることを願っています。