將二進制樹的中綴轉換爲後綴

Question

我正在試圖爲後綴轉換器製作一箇中綴。我已經在谷歌搜索代碼，但大多數算法都是使用堆棧或使用很多正則表達式或很難理解的，但是我想用二叉樹來實現。

這裏是我已經做了：

等級節點：

public class Node 
{ 
    private object element; 
    private Node left; 
    private Node right; 
    private Node parent; 

    public Node() 
    { 
    } 

    public Node(object x, Node r, Node l) 
    { 
     element = x; 
     right = r; 
     left = l; 
    } 

    public object GetElement() 
    { 
     return element; 
    } 

    public void SetElement(object x) 
    { 
     element = x; 
    } 

    public Node GetLeft() 
    { 
     return left; 
    } 

    public void SetLeft(Node l) 
    { 
     left = l; 
    } 

    public Node GetRight() 
    { 
     return right; 
    } 

    public void SetRight(Node r) 
    { 
     right = r; 
    } 

    public Node GetParent() 
    { 
     return parent; 
    } 

    public void SetParent(Node p) 
    { 
     parent = p; 
    } 
} 

對不起使用get/set方法，而不是簡單的自動屬性。

public class BinarySearchTree 
{ 
    //Node r: root. 
    public void Insert(Node r, Node p, object x) 
    { 
     if (r == null) 
     { 
      r = new Node(x, null, null); 
      r.SetParent(p); 
      if ((int)x < (int)p.GetElement()) 
       p.SetLeft(r); 
      else if ((int)x > (int)p.GetElement()) 
       p.SetRight(r); 
     } 
     if ((int) x < (int) r.GetElement()) 
      Insert(r.GetLeft(), r, x); 
     else if ((int) x > (int) r.GetElement()) 
      Insert(r.GetRight(), r, x); 
    } 

    public void PreOrder(Node p) 
    { 
     if (p != null) 
     { 
      Console.WriteLine(p.GetElement()); 
      PreOrder(p.GetLeft()); 
      PreOrder(p.GetRight()); 
     } 
    } 

    public void Inorder(Node p) 
    { 
     if (p != null) 
     { 
      Inorder(p.GetLeft()); 
      Console.WriteLine(p.GetElement()); 
      Inorder(p.GetRight()); 
     } 
    } 

    public void Postorder(Node p) 
    { 
     if (p != null) 
     { 
      Postorder(p.GetLeft()); 
      Postorder(p.GetRight()); 
      Console.WriteLine(p.GetElement()); 
     } 
    } 
} 

：

並具有插入，後綴，前綴和中綴方法（我也有writen搜索，deletemin等，但我們並不需要他們爲我的問題）

BST類我BST類

我的插入方法是例如數字工作：
如果我們想編寫中序，預購和後下方樹

秩序

預訂：5,3，2,4，7，6，12
後序：2,4，3，6，12，7,5
中序：2，3，4，5，6，7 ，12

這個例子主要方法：

private static void Main() 
{ 
    BinarySearchTree bst = new BinarySearchTree(); 
    Node r = new Node(5, null, null); 
    bst.Insert(r, null, 3); 
    bst.Insert(r, null, 7); 
    bst.Insert(r, null, 4); 
    bst.Insert(r, null, 12); 
    bst.Insert(r, null, 2); 
    bst.Insert(r, null, 6); 
    bst.Inorder(r); 
    Console.WriteLine(); 
    bst.Postorder(r); 
    Console.WriteLine(); 
    bst.PreOrder(r); 
} 

現在我想打一個綴到後綴轉換器，但不知道如何實現該插入方法，以及如何處理操作和操作數訂購。另一個問題是括號。
將不勝感激，如果幫我一些代碼。

一個例子樹木：

mathblog有綴到後綴轉換器，你可以檢查你的吧。
http://www.mathblog.dk/tools/infix-postfix-converter/

Answer 1

它看起來像表達式從綴轉換爲後綴符號的最簡單的方法是使用標準的基於堆棧的算法（其具有線性的時間複雜度，所以它是最佳的），然後建立一個樹（構建來自後綴表達式的樹很簡單，因爲所有操作符的順序都是正確的）。