生成二叉樹的所有可能的子樹

Question

我有一棵二叉樹，我想從中生成所有可能的子樹。 例子：

1 
/\ 
2  3 
    /\ 
    4 5 

可能的輸出將是：

1, 2, 3, 4, 5. 
(1,2) (1,3) 
(1,3,4) (1,3,5) 

這可能嗎？我需要一個算法來生成輸出？

Answer 1

讓我們的我張貼在僞答案：

首先讓我告訴你我是如何實現三：

Node{ 
Node rightNode; 
Node leftNode; 
String value; 
} 

並在此之後是algoritm：

Algoritm{ 
    String[] posibleThrees; 

    String getPosibleThrees(Node root){ 
     getPosibleThree(root, ""); 
     return posibleThrees; 
    } 

    void getPosibleThree(Node node, String nodesBefore){ 
     posibleThrees[] = nodesBefore; //adding nodes before 

     if (node.rightNode != null){ 
      getPosibleThree(node.rightNode, nodesBefore+" "+node.value); 
     } 

     if (node.leftNode != null) { 
      getPosibleThree(node.leftNode, nodesBefore+" "+node.value); 
     } 
    } 
} 

Answer 2

系統發育有做這個很多。

程序，如phyml解決這個問題：

考慮：

• 演化的模型（可能是基因突變如何等）
• 現有的幾個物種的基因序列（從中找到每對之間的進化距離矩陣）

查找：最大似然進化樹。

從猜測開始，搜索樹空間，根據您的模型尋找具有更高可能性的排列。當你達到當地最低標準時停下來。再次嘗試一些不同的起始樹，希望找到全局最小值。

大量的代碼可以遍歷可能的樹，已經爲系統發育學書寫了，所以如果你需要這樣的東西，這是尋找想法的好地方。

---

我自己all SPR庫（和示例前端）可以給你一切可能的樹到達一個子樹修剪/再移植，對於給定的起始樹。它只有沒有樹重新排列，並沒有散佈可能性計算的代碼。我很久以前寫過它，一些在2004年，一些在2007年，但它仍然可能比非程序員編寫的典型的系統發育軟件更具可讀性。

我完成了它，我認爲一些代碼可能已經進入procov。我認爲當我開始編寫它時，有procov使用這個庫是我的想法。

它沒有打磨，代碼有點混亂，我基本上是在編寫API時編寫的。使用它的人可能需要定製它。我整理了一些最令人困惑的部分，因爲我似乎從未承諾過我8年前的最後幾項變化。

無論如何，對於給定的樹，可能存在理論上最大數量的SPR，其中許多會產生重複的樹。

• 給定一個在此範圍內的數字，spr.c: spr_sprnum(struct spr_tree *tree, int coded_sprnum)將其解碼爲SPR，並嘗試應用它。

• spr.c: int spr_next_spr(struct spr_tree *tree)嘗試編號的SPR，直到它找到合法的或返回到開頭。

它記得它剛剛做了哪個SPR，所以它首先撤消了最後一個SPR，然後做了新的SPR。

要按隨機順序遍歷所有SPR，我的代碼會找到一個linear congruential generator，它將生成1到N的所有數字，然後重複一次。查找LCG參數需要找到適當的素數，所以在這裏有一個簡單的Eratosthenes篩lcg.c

brontler是一個演示前端，可以在命令行或文件中採用Newick格式的樹。例如

./brontler '(((a,b),c),(d,e))' 
tree: taxa: 5, nodes: 9, possible SPRs <= 72 
1: tree 1.45: (c,(((a,b),d),e)); 
2: tree 1.10: (a,((b,c),(d,e))); 
3: tree 1.59: (c,(d,((a,b),e))); 
4: tree 1.29: (((a,c),b),(d,e)); 
5: tree 1.60: ((b,c),(d,(a,e))); 
6: tree 1.61: ((a,c),(d,(e,b))); 
7: tree 1.69: (((a,(b,e)),c),d); 
8: tree 1.53: ((((d,a),b),c),e); 
9: tree 1.46: ((b,c),((a,d),e)); 
10: tree 1.54: (e,((a,(d,b)),c)); 
11: tree 1.68: (d,(((a,e),b),c)); 
12: tree 1.47: ((a,c),((d,b),e)); 
tree iteration 1 gave 12 new trees 

在調試-d 1或更高版本時，您將在輸出中看到內部節點的名稱。它們是大寫單個字母，在樹被解析時按順序分配。 （因爲我只是增加了一個char變量，所以我會變得很奇怪......）

這是GPLv2，如果有人有很好的理由並且要求的很好，我可能會把它變成LGPL。這不是一個複雜的算法或設計，所以如果你不想直接使用代碼，不用擔心重新實現它的一部分。