數學表達式的二叉樹

Question

我有一個包含數學表達式的二叉樹。我使用數組來保存二進制樹在內存中。 我將運算符（如+或tan）保存爲數組中的字符串。對於每個i節點，左節點索引是2 * i + 1，右節點索引是2 * i + 2。每個節點都可以是操作數或操作符。我想將二叉樹轉換爲數學表達式，如下所示：「2 + tan（tan（10））」。如何將二叉樹轉換爲C＃中的數學表達式？

+ 
/\ 
2 tan 
/\    ===>  "2+tan(tan(10))" 
tan 
/\/\ 
10 

這是我的二叉樹代碼：

public class Tree 
{ 
    private readonly List<Node> _nodes; 

    public Tree(int size) 
    { 
     _nodes = new List<Node>(); 

     for (var i = 0; i < size; i++) 
     { 
      _nodes.Add(new Node(i, null)); 
     } 

     for (var i = 0; i < size; i++) 
     { 
      if (2*i+1 > size-1 || 2*i+2 > size-1) 
       break; 

      _nodes[i].Left = _nodes[2*i + 1]; 
      _nodes[i].Right = _nodes[2*i + 2]; 
     } 
    } 
    ... 
} 

Answer 1

你可以做到這一點遞歸 - 寫返回一個字符串，並執行這三樣東西的方法：

• 當兩個子樹null，返回節點的內容
• 當只有一個子樹是非空的時，遞歸地調用該方法，然後返回節點的內容b y括號中的遞歸調用的結果
• 當兩個子樹都爲非空值時，對左側和裂谷子樹進行遞歸調用，並返回左邊的結果，然後返回此節點的內容，然後返回正確的結果。