c# - 洗牌树(递归)

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. 在不改变 Left 或 Right 引用的情况下打乱该列表中节点的数据内容。

所以，要压平树:

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 以致多个实例使用相同的种子而出现问题。