递归创建一个数学表达式二叉树

Question

下午所有，

我已经实现了在C＃中简单的二进制树，我打算使用它来递归创建数学表达式树。但是我遇到了问题，因为我必须做递归调用已经有好几年了，我正在努力想知道为什么以下只适用于深度为2的二叉树而不是深度较大的树。

当然，如果递归是正确的，它应该能够构建深度为n的树。下面是代码：

Node<T> f; 
Node<T> t; 
Node<T> subRoot; 
Node<T> root; 

////Only works with trees of depth 2. 

private Node<T> Tree(List<T> prefixBank, int maxDepth) 
{ 
    if (prefixBank.Count != 0) 
    { 
     if (maxDepth == 0) 
     { 
      t = new Node<T>(prefixBank[0]); 
      subRoot.Add(t); 

      prefixBank.Remove(prefixBank[0]); 
     } 
     else 
     { 
      if (root == null) 
      { 
       root = new Node<T>(prefixBank[0]); 
       prefixBank.Remove(prefixBank[0]); 
       Tree(prefixBank, maxDepth - 1); 
      } 

      f = new Node<T>(prefixBank[0]); 

      if (isOperator(f)) 
      { 
       root.Add(f); 
       prefixBank.Remove(prefixBank[0]); 
       subRoot = f; 
      } 

      for (int i = 0; i < 2; i++) 
      { 
       Tree(prefixBank, maxDepth - 1); 
      } 
     } 
    } 
return f; 
} 

上述函数使用形成前缀数学表达式（例如* + 3 4 - 5 6）字符的列表。烦人，我创建了前缀表达式递归地使用此代码：

string prefixExpression = String.Empty; 

private string generateExpression(Random rand, GenerationMethod generationMethod, int maxDepth) 
{ 
    if ((maxDepth == 0) || ((generationMethod == GenerationMethod.Grow) && (rand.NextDouble() < randomRate))) 
    { 
     operand.GenerateValue(Type.Terminal, rand); 
     prefixExpression += " " + operand.Value; 
    } 
    else 
    { 
     operator.GenerateValue(Type.Function, rand); 
     prefixExpression += " " + operator.GeneValue; 

     //2 is the arity of the function right an arity checker function so that unary operators can be utilised 
     for (int i = 0; i < 2; i++) 
     { 
      generateExpression(rand, generationMethod, maxDepth - 1); 
     }; 
    } 
    return prefixExpression; 
} 

我试图创造我所生成的字符串以同样的方式树，但不能让它在任何常识的方式工作。我正在使用binary tree class found on MSDN的稍微修改版本。我修改它有一个自动添加到左侧或右侧子树的添加功能，所以我不必指定Root.Left.Left.Left等，就像这个例子创建树一样。

如果任何机构可以帮助我纠正我的递归树创建代码，使它适用于n深度的树，我真的很感激它。对于C＃来说，我相对较新，所以如果上面的内容稍微粗略一点，我很抱歉。

Answer 1

在进行像这样的递归调用时，您不应该依赖全局变量（并且一般而言，变量的范围应该尽可能窄，似乎没有任何理由使得f和t成为类级变量）。你的代码对我来说没有什么意义，但我猜想主要的问题是你将每个节点直接添加到根目录。我会做这样的：

public Node<T> Tree(Queue<T> prefixBank) 
{ 
    var node = new Node<T>(prefixBank.Dequeue()); 

    if (isOperator(node)) 
    { 
     for (int i = 0; i < 2; i++) 
     { 
      node.Add(Tree(prefixBank)); 
     } 
    } 

    return node; 
} 

我看不出有任何理由，maxDepth那里，但如果你真的想要的话，它应该是微不足道的实施。

此外，有一个继承层次结构的节点（如NumberNode,OperatorNode）可能是有意义的，但这取决于你想要对它们做什么。

编辑：@Eric，不多。我可以使用IEnumerator<T>而不是Queue<T>（现在我认为它可能是更好的选择）。而且我必须将结果的创建推迟到最后，这也意味着我必须修改isOperator()以处理T而不是Node<T>。

public Node<T> Tree(IEnumerable<T> prefixBank) 
{ 
    return Tree(prefixBank.GetEnumerator()); 
} 

public Node<T> Tree(IEnumerator<T> enumerator) 
{ 
    enumerator.MoveNext(); 
    var value = enumerator.Current; 

    var children = new List<Node<T>>(2); 

    if (isOperator(value)) 
    { 
     for (int i = 0; i < 2; i++) 
     { 
      children.Add(Tree(enumerator)); 
     } 
    } 

    return new Node<T>(value, children); 
}