爲單元測試隨機生成樹

Question

我想爲我的代碼的單元測試隨機生成樹（而不是BST）。我嘗試了很多方法，但是在生成3到4棵樹後出現異常，或者代碼進入了無限循環。我正在使用隨機數的邊和節點值。
我也嘗試過使用隨機數字填充隊列的隊列方法，然後使隊列中的隊列中的現有項目隨機選擇舊節點，然後連接此新節點。

有人知道如何以更好更簡潔的方式在C＃中執行此操作嗎？

編輯

public class Tree 
{ 
    public Node Root { get; private set; } 
    public readonly Dictionary<long, Node> Nodes = new Dictionary<long, Node>(); 
    public readonly Dictionary<string, long> SumDictionary = new Dictionary<string, long>(); 

    public readonly Dictionary<long, long> FDictionary = new Dictionary<long, long> 
    { 
     {0, 1}, 
     {1, 1} 
    }; 


    public long Query(long n) 
    { 
     long s = 0; 
     Dfs(); 

     for (int i = 1; i <= n; i++) 
     { 
      for (int j = i; j <= n; j++) 
      { 
       var lvalue = GetLValue(i, j); 

       if (i != j) 
       { 
        lvalue *= 2; 
       } 

       s += lvalue; 

       if (s >= Mod) 
       { 
        s %= Mod; 
       } 

      } 
     } 

     return s; 
    } 

    private long GetLValue(int a, int b) 
    { 
     var key = string.Format("{0}-{1}", a, b); 

     if (SumDictionary.ContainsKey(key)) 
     { 
      return Fvalue(SumDictionary[key]); 
     } 

     var aKey = string.Format("{0}-{1}", 1, a); 
     var bKey = string.Format("{0}-{1}", 1, b); 

     var sumA = SumDictionary[aKey]; 
     var sumB = SumDictionary[bKey]; 

     var lca = Lca(a, b); 

     if (lca != a && lca != b) 
     { 
      return Fvalue(sumA + sumB - SumDictionary[string.Format("{0}-{1}", lca, lca)]); 
     } 


     long bigSum, smallSum; 

     if (sumA > sumB) 
     { 
      bigSum = sumA; 
      smallSum = sumB; 
     } 
     else 
     { 
      bigSum = sumB; 
      smallSum = sumA; 
     } 

     var sumAtoB = bigSum - (smallSum - Nodes[smallSum].Value); 

     return Fvalue(sumAtoB); 
    } 

    public void AddNode(long a, long b) 
    { 
     Node nodea, nodeb; 
     if (Nodes.ContainsKey(a)) 
     { 
      nodea = Nodes[a]; 
     } 
     else 
     { 
      nodea = new Node { Value = a }; 
      Nodes.Add(a, nodea); 
     } 

     if (Nodes.ContainsKey(b)) 
     { 
      nodeb = Nodes[b]; 
     } 
     else 
     { 
      nodeb = new Node { Value = b }; 
      Nodes.Add(b, nodeb); 
     } 

     nodea.ReachableNodes.Add(b, nodeb); 
     nodeb.ReachableNodes.Add(a, nodea); 

     if (Root == null) 
     { 
      Root = nodea; 
     } 
    } 

    public long? Lca(int a, int b) 
    { 
     bool found = false; 
     return TraverseForLca(Root, null, a, b, ref found); 
    } 

    private long? TraverseForLca(Node node, Node prev, long a, long b, ref bool found) 
    { 
     if (node == null) 
     { 
      return null; 
     } 

     if (node.Value == a) 
     { 
      return a; 
     } 

     if (node.Value == b) 
     { 
      return b; 
     } 


     long? f = null; 

     foreach (KeyValuePair<long, Node> reachableNode in node.ReachableNodes) 
     { 
      var n = reachableNode.Value; 

      if (prev != null && n.Value == prev.Value) 
      { 
       continue; 
      } 

      long? lca = TraverseForLca(n, node, a, b, ref found); 

      if (found) 
      { 
       return lca; 
      } 

      if (lca != null && f == null) 
      { 
       f = lca; 
      } 
      else if (lca != null) 
      { 
       found = true; 
       return node.Value; 
      } 
     } 

     return f; 
    } 

    public void Dfs() 
    { 
     TravelForDfs(Root, null, 0); 
    } 

    private void TravelForDfs(Node node, Node prev, long recSum) 
    { 
     if (node == null) 
     { 
      return; 
     } 

     var key = string.Format("{0}-{1}", prev != null ? prev.Value : node.Value, node.Value); 
     var iKey = string.Format("{0}-{1}", node.Value, node.Value); 
     var weight = node.Weight; 

     if (weight >= Mod) 
     { 
      weight %= Mod; 
     } 


     if (!SumDictionary.ContainsKey(iKey)) 
     { 
      SumDictionary.Add(iKey, weight); 
     } 

     weight = recSum + node.Weight; 

     if (weight >= Mod) 
     { 
      weight %= Mod; 
     } 

     foreach (KeyValuePair<long, Node> reachableNode in node.ReachableNodes) 
     { 
      var n = reachableNode.Value; 

      if (prev != null && n.Value == prev.Value) 
      { 
       if (!SumDictionary.ContainsKey(key)) 
       { 
        SumDictionary.Add(key, weight); 
       } 

       continue; 
      } 

      if (!SumDictionary.ContainsKey(key)) 
      { 
       SumDictionary.Add(key, weight); 
      } 

      TravelForDfs(n, node, weight); 
     } 
    } 

    public long Fvalue(long n) 
    { 
     if (n == 1 || n == 0) 
     { 
      return 1; 
     } 

     long a, b; 

     if (FDictionary.ContainsKey(n - 1)) 
     { 
      a = FDictionary[n - 1]; 
     } 
     else 
     { 
      a = Fvalue(n - 1); 

      if (!FDictionary.ContainsKey(n - 1)) 
      { 
       FDictionary.Add(n - 1, a); 
      } 

     } 

     if (FDictionary.ContainsKey(n - 2)) 
     { 
      b = FDictionary[n - 2]; 
     } 
     else 
     { 
      b = Fvalue(n - 2); 

      if (!FDictionary.ContainsKey(n - 2)) 
      { 
       FDictionary.Add(n - 2, b); 
      } 

     } 


     if (!FDictionary.ContainsKey(n)) 
     { 
      FDictionary.Add(n, a + b); 
     } 


     var s = a + b; 
     if (s >= Mod) 
     { 
      s %= Mod; 
     } 

     return s; 

    } 

} 

Answer 1

它應該只是產生一個樹

這是否樹滿足您的要求？

public class TreeNode<T> 
{ 
    public T Value { get; set; } 
    public List<TreeNode<T>> Childs { get; } 

    public TreeNode() 
    { 
     Childs = new List<TreeNode<T>>(); 
    } 
} 

public class TreeGenerator 
{ 
    private readonly int maxChilds; 
    private readonly Random rnd = new Random(); 

    public TreeGenerator(int maxChilds) 
    { 
     this.maxChilds = maxChilds; 
    } 

    public TreeNode<T> CreateTree<T>(int maxDepth, Func<T> valueGenerator) 
    { 
     var node = new TreeNode<T>(); 
     node.Value = valueGenerator(); 
     if (maxDepth > 0) 
     { 
      var childsCount = rnd.Next(maxChilds); 
      for (var i = 0; i < childsCount; ++i) 
       node.Childs.Add(CreateTree(maxDepth - 1, valueGenerator)); 
     } 
     return node; 
    } 

    public static void Demo() 
    { 
     var rnd = new Random(); 
     var generator = new TreeGenerator(3 /* max childs count*/); 
     var tree = generator.CreateTree(4 /*max depth*/,() => rnd.Next() /*node value*/); 
    } 
}