洗牌树(递归)

本文关键字：递归 | 更新日期: 2023-09-27 17:53:28

我用下面的类递归地构造了一棵树:

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

如何洗牌那棵树?

洗牌树(递归)

这可能不是最有效的方法，但您可以这样做:

  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 shuffle来洗牌列表中节点的内容:

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的问题，因为多个实例使用相同的种子。

如果它只是一棵树，没有别的。我将遍历树并将每个节点添加到一个字典中，并以随机值作为键。然后对其排序，并通过按顺序添加值来构建新的树。

显然，你可能还需要在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();
  • 从sortedList中获取第一项并将其放入工作列表
  • 循环通过工作列表
  • 从排序列表中获取下2项。(如有剩余)
  • 将其添加到工作列表项
  • 删除当前工作列表项。
  • 将2个子节点添加到工作列表
  • 继续，直到工作列表为空。

这显然会创建一个所有分支长度大致相同的树

相关文章：