遞歸創建一個數學表達式二叉樹

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); 
}