C# - 将元组的元组作为输入参数传递给方法

Question

我正在编写一种使用元组创建二叉搜索树的方法。我有创建树节点的 TreeNode 类。

class TreeNode
{
    public int Key{get; set;}
    public TreeNode Left{get; set;}
    public TreeNode Right{get; set;}

    public TreeNode(int key)
    {
        this.Key = key;
    }
}

我想创建以下树：

为此，我使用元组值( ( 1, 3, null), 2, ( ( null, 3, 4 ), 5, ( 6, 7, 8 ) ) )来表示元组形式的 BST。

使用元组创建 BST 的方法 TupleToBST 需要将元组的元组作为输入参数，以便我可以递归地创建 BST。

public static TreeNode TupleToBST(Tuple<Tuple, int, Tuple> tup)   //Line 36
  {
    if (tup == null)
    {
        return null;
    }
    TreeNode t = new TreeNode(tup.Item2);
    t.Left = TupleToBST(tup.Item1);
    t.right = TupleToBST(tup.Item3);
    return t;
  }

main.cs文件代码如下：

static void Main ()
{
  var tup = Tuple.Create(Tuple.Create(1,3,null),2,Tuple.Create(Tuple.Create(null,3,4),5,Tuple.Create(6,7,8)));
  TreeNode tree = TupleToBST(tup);
  Console.WriteLine(tree.Right.Right.Key);
  Console.WriteLine(tree.Right.Right.Key);
}

我收到以下错误：

main.cs(36): 错误 CS0718: `System.Tuple': 静态类不能用作泛型参数**

Answer 1

这里的问题是您需要内部元组的类型。所以代替这个：

\n

Tuple<Tuple, int, Tuple>\n

\n

它必须看起来更像这样：

\n

Tuple<Tuple<Tuple, int Tuple>, int, Tuple<Tuple, int, Tuple>>\n

\n

但现在我们只是把问题推到了另一个层次。我们可以依次定义这些类型参数，但我认为您会明白这个问题永远不会结束，而且实际上随着每个新级别的增加呈指数级增长。

\n

更糟糕的是，您不能只定义具有任意足够数量的级别的大型类型来容纳任何实际的树。相反，您必须定义类型参数以与树中的现有分支完全匹配，或者还为每个可能的大小和平衡级别组合定义重载。

\n

因此，您应该使用而不是元组TreeNode：

\n

class TreeNode<T>\n{\n    public T Key{get; set;}\n    public TreeNode<T> Left{get; set;}\n    public TreeNode<T> Right{get; set;}\n\n    public TreeNode(T key)\n    {\n        this.Key = key;\n    }\n}\n\npublic static TreeNode<T> TupleToBST<T>((TreeNode<T>, T, TreeNode<T>) tup)\n{\n    if (tup == null) return null;\n\n    // Tuple items start counting at 1, not 0\n    return new TreeNode(tup.Item2) {Left = tup.Item1, Right = tup.Item3};\n}\n

\n

但我知道这不太可能令您满意，因为目标似乎是在代码中输入单个大型表达式来创建数据。

\n\n

需要考虑的一种选择是定义从到 的隐式转换。起初我不确定编译器对处理嵌套/递归转换有何反应，但这是一个值得探索的想法。Tuple<TreeNode<T>, T, TreeNode<T>>TreeNode<T>

\n

但在我们走这条路之前，我们需要先谈谈数据。即使这确实有效，问题也有以下示例数据：

\n

( ( 1, 3, null), 2, ( ( null, 3, 4 ), 5, ( 6, 7, 8 ) ) )\n

\n

该数据将是无效的，因为只允许中心项目具有值。左侧和右侧必须始终是一个null或另一个元组/树节点，并且每个叶节点必须始终看起来像(null, value null)。相反，您需要像这样显示它：

\n

( ( (null, 1, null), 3, null), 2, ( ( null, 3, (null, 4, null) ), 5, ( (null, 6, null), 7, (null, 8, null) ) ) )\n

\n

现在我们有了有效的数据，我们可以尝试转换。令人惊讶的是 \xe2\x80\x94 \xe2\x80\x94这似乎有效：

\n

public class TreeNode<T>\n{\n    public T Key{get; set;}\n    public TreeNode<T> Left{get; set;}\n    public TreeNode<T> Right{get; set;}\n\n    public TreeNode(T key)\n    {\n        this.Key = key;\n    }\n    public static implicit operator TreeNode<T>((TreeNode<T>, T, TreeNode<T>) t) => new TreeNode<T>(t.Item2) {Left = t.Item1,  Right=t.Item3};\n}\n\npublic class Program\n{\n    public static void Main()\n    {\n        TreeNode<int> tree = ( ( (null, 1, null), 3, null), 2, ( ( null, 3, (null, 4, null) ), 5, ( (null, 6, null), 7, (null, 8, null) ) ) );\n        Console.WriteLine(tree.Left.Key);\n    }\n}\n

\n

您可以在这里亲自查看：

\n

\n

https://dotnetfiddle.net/7XaHa4
\n https://dotnetfiddle.net/ZvUPYM

\n

\n\n

更新：

\n

我又想了一下，有了这四个隐式转换定义，我们还可以让原始数据表达式起作用：

\n

(TreeNode<T>, T, TreeNode<T>)\n(T, T, TreeNode<T>)\n(TreeNode<T>, T, T)\n(T, T, T)\n

\n

还有班级：

\n

public class TreeNode<T>\n{\n    public T Key{get; set;}\n    public TreeNode<T> Left{get; set;}\n    public TreeNode<T> Right{get; set;}\n\n    public TreeNode(T key)\n    {\n        this.Key = key;\n    }\n    public static implicit operator TreeNode<T>((TreeNode<T>, T, TreeNode<T>) t) => new TreeNode<T>(t.Item2) {Left = t.Item1,  Right=t.Item3};\n    public static implicit operator TreeNode<T>((T, T, TreeNode<T>) t) => new TreeNode<T>(t.Item2) {Left = new TreeNode<T>(t.Item1),  Right=t.Item3};\n    public static implicit operator TreeNode<T>((TreeNode<T>, T, T) t) => new TreeNode<T>(t.Item2) {Left = t.Item1,  Right=new TreeNode<T>(t.Item3)};\n    public static implicit operator TreeNode<T>((T, T, T) t) => new TreeNode<T>(t.Item2) {Left = new TreeNode<T>(t.Item1),  Right=new TreeNode<T>(t.Item3)};\n}\n\n\npublic static void Main()\n{\n    TreeNode<int> tree = ( ( 1, 3, null), 2, ( ( null, 3, 4 ), 5, ( 6, 7, 8 ) ) );\n    Console.WriteLine(tree.Left.Key);\n}\n

\n

看看它与原始表达式的配合：

\n

\n

https://dotnetfiddle.net/mGN7Lf
\n https://dotnetfiddle.net/6I32WU

\n

\n\n

现在我们甚至可以（某种程度上）编写原始方法。参数的实际类型仍然是TreeNode<T>，但我们可以传入元组并取出 TreeNode ：

\n

public static TreeNode TupleToBST<T>(TreeNode<T> tup)   //Line 36\n{\n    return tup;\n}\nTreeNode<int> tree = TupleToBST<int>( ( ( 1, 3, null), 2, ( ( null, 3, 4 ), 5, ( 6, 7, 8 ) ) ));\n\n

\n

\n

https://dotnetfiddle.net/ni7jJf

\n

\n

请注意，该方法实际上并没有做任何事情...它是隐式转换和编译器完成了这里的所有工作。

\n