生成所有可能的二叉樹給定n葉

因此，如標題所示，任何人都知道有一個算法（如果可能，用java）來生成所有可能的二叉樹，如下面第二個鏈接的例子所示。生成所有可能的二叉樹給定n葉

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

從來就已經去過this，this，this和this，但我已盡力實現每個和他們鴕鳥政策做什麼I'm尋找或不正確解釋。如果必須首先生成所有可能的字符串，然後將它們解析爲樹類型（父子關係），而第二個不打印所有樹，則第一個將是大量計算。因爲，例如，如果我通過像上面的例子那樣指定3個內部節點來執行，它只會打印一棵樹（左邊的那棵）。通過對加泰羅尼亞語數字的研究，我知道即使對於少數節點，樹的數量也會增長很多，但對於節點數量較少而言，它是一種有用的工具。在此先感謝

來源

2016-08-17 Enixf

只是想知道：你想通過計算二叉樹中對象的可能「排列」來解決什麼問題？ – GhostCat

@GhostCat也許他試圖找到「最佳」迭代？但是再次，解決這個問題的方法只是爲了平衡這棵樹 –

@GhostCat的權利，好吧，我正在爲一款遊戲構建一個Ai，我們希望它具有所有可能性，但是在後期遊戲放棄無用的樹木。 – Enixf

我沒有檢查所有的鏈接，但在我看來，他們中的一些人有一些有用的想法。爲了回答你的問題，不，我不知道一個算法，但我不認爲設計一個算法會很困難。

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

在上述我假定InternalNodeLeaf和是的兩個TreeNode子類。你可能想要一個不同的設計。我希望你可以相應地調整代碼。

來源

2016-08-17 16:52:12

謝謝！這有助於很多！ – Enixf

生成所有可能的二叉樹給定n葉

回答

相關問題