創建所有具有獨特排列的二叉樹

我有一個相當愚蠢的問題，我發誓不是作業。對於我的生活，我不記得我是否曾經研究過一種算法來做到這一點，而我的大腦眼睛/創造力正在讓我失望。創建所有具有獨特排列的二叉樹

我有一個唯一的節點列表。我需要生成包含這些節點的二叉樹的所有獨特排列。手性，如果你想知道，很重要;在它的軸上翻轉的二叉樹（左/右）是不一樣的。

一些背景信息，如果你想知道：它是一個進化程序的種子創建算法，所以大量的小種子是好的。

編輯：唯一性

Examples: 

This: 
    1 
/\ 
2 3 

Is not the same as this: 
    1 
/\ 
3 2 

Nor is it the same as this: 

    1 
/
    3 
/
2 

Nor this: 

1 
\ 
    2 
    \ 
    3

來源

2012-07-12 user978122

通過「獨特的排列」，你的意思是結構呢？例如，將具有左子節點2（其具有另一個左子節點3）的根1的樹視爲與具有左子節點2和右子節點3的樹相同？對不起，如果我措辭有點笨拙的問題.. – Daniel 2012-07-12 10:41:32

它不會被認爲是一樣的。 – user978122 2012-07-13 20:16:32

澄清埃裏克利珀有一個相關的職位here（系列文章的真正開始）。關鍵位是這個遞歸方法LINQ：

static IEnumerable<Node> AllBinaryTrees(int size) 
{ 
    if (size == 0) 
     return new Node[] { null }; 
    return from i in Enumerable.Range(0, size) 
      from left in AllBinaryTrees(i) 
      from right in AllBinaryTrees(size - 1 - i) 
      select new Node(left, right); 
}

這得到所有可能的二叉樹結構給定尺寸的。我認爲如果你採取（a）所有節點列表的排列，和（b）Eric的所有樹結構列表，並且執行這兩個節點的「交叉乘積」（將你的置換節點賦值給結構 ~~中的節點以一致的順序從左到右~~ ），您應該獲得所需的所有樹。

E.g. 3件商品

Permutations      Tree structures 
123 132         . . . . .   
213 231        ./ ./ ./ \. \. \. 
312 321        ./  \.   ./  \. 

Result 
:  1 1 1 1 1    1 1 1 1 1  
: 2/ 2/ 2/ \3 \2 \2   3/ 3/ 3/ \2 \3 \3 
: 3/  \3   3/  \3  2/  \2   2/  \2 

:  2 2 2 2 2    2 2 2 2 2  
: 1/ 1/ 1/ \3 \1 \1   3/ 3/ 3/ \1 \3 \3 
: 3/  \3   3/  \3  1/  \1   1/  \1 

:  3 3 3 3 3    3 3 3 3 3  
: 1/ 1/ 1/ \2 \1 \1   2/ 2/ 2/ \1 \2 \2 
: 2/  \2   2/  \2  1/  \1   1/  \1

如果你不關心手性，這會更困難。

（產生你的輸入節點的排列，並Eric的結構之一分配排列，應該是相當瑣碎的，對吧？）

來源

2012-07-12 10:41:08 Rawling

有趣。將研究它。 – user978122 2012-07-13 20:21:32

創建所有具有獨特排列的二叉樹

回答

相關問題