隨機樹（遞歸）

Question

我已經樹遞歸地從下面的類構造：

public class Node 
{ 
    public byte Symbol { get; set; } 
    public int Frequency { get; set; } 
    public Node Right { get; set; } 
    public Node Left { get; set; } 
} 

如何洗牌那棵樹？

Answer 1

這可能不是最有效的方式，但你可以如下做到這一點：

1. 拼合樹放入節點列表中。
2. 隨機播放該列表中的節點的數據內容，不改變左或右的引用。

所以，扁平化樹：

static IEnumerable<Node> FlattenTree(Node root) 
{ 
    if (root != null) 
    { 
     yield return root; 

     foreach (var node in FlattenTree(root.Left)) 
      yield return node; 

     foreach (var node in FlattenTree(root.Right)) 
      yield return node; 
    } 
} 

然後寫一個Fisher-Yates shuffler洗牌節點的內容列表：

static void Shuffle(List<Node> nodes, Random rng) 
{ 
    // Fisher-Yates shuffle. 

    for (int n = nodes.Count; n > 1;) 
    { 
     int k = rng.Next(n); 
     --n; 
     Swap(nodes[n], nodes[k]); 
    } 
} 

static void Swap(Node a, Node b) 
{ 
    byte tempSymbol = a.Symbol; 
    a.Symbol = b.Symbol; 
    b.Symbol = tempSymbol; 

    int tempFrequency = a.Frequency; 
    a.Frequency = b.Frequency; 
    b.Frequency = tempFrequency; 
} 

最後拼合樹成一個列表，並然後洗牌節點的內容在列表：

static void ShuffleTree(Node root, Random rng) 
{ 
    var allNodes = FlattenTree(root).ToList(); 
    Shuffle(allNodes, rng); 
} 

這需要足夠的空間，使在樹中的所有節點引用的副本，平整樹和O（N）隨機播放時，當它爲O（N）複雜度（所以它是O（N）的整體）。

請注意，你需要一個Random進入ShuffleTree（）。如果多次調用它，只需創建一個Random對象並將其傳遞給每個調用，以避免因頻繁創建新Random而導致多個實例使用相同種子的問題。

Answer 2

如果它僅僅是一棵樹，沒有別的。我將遍歷樹並將每個節點添加到以隨機值爲關鍵字的字典中。然後，通過按順序添加值來對它進行排序並構建新樹。

很顯然，你可能還必須在x和y之間生成一個隨機int，它指定了一個節點可以擁有多少個子節點，如果它不是二叉樹，而是通過你的代碼示例，它是。

//Traverse the tree and put it in input 
Random random = new Random((int)DateTime.Now.Millisecond); 
List<Node> sortedList = input.OrderBy(x => random.Next()).ToList(); 

• 從排序列表獲取第一個項目，並把它在工作列表
• 環通工作清單
• 獲取從排序列表中的下一個2項。 （如果還有剩餘的話）
• 將其添加到工作清單項
• 刪除當前工作清單項。
• 添加2個節點的工作列表
• 我們繼續下去，直到工作列表爲空。

這顯然會創建一個樹所有分支或多或少相同長度