如何解析樹型數據結構？

Question

我有一個樹數據結構，由節點組成，需要解析到表達式樹中。我的節點看上去像這樣（簡化）：

public class Node 
    { 
     public Node Left { get; set; } 
     public Node Right { get; set; } 
     public Operation OperationType { get; set; } 
     public object Value { get; set; } 
    } 

什麼是找到樹的底部和工作向後建立表達式樹中的最佳/正確方法是什麼？你先解析左邊還是右邊？

Answer 1

我不認爲你首先穿過哪個方向很重要。然而，在一個從左到右的語言占主導地位的世界裏，如果你先離開，有人會更直觀地理解你的代碼。

Answer 2

如果你想先到達樹的底部，那麼你可以按'順序'或者'後序'搜索。 「按序」搜索將首先找到底部最左側的節點，然後是該節點的父節點，然後是父節點的右側子節點。 '後序'搜索將在訪問父節點之前'訪問'左側子節點和右側子節點。

考慮表達式'x + y'。一個有序的搜索將產生：

'x', '+', 'y' 

而訂單後，搜索將產生：

'x', 'y', '+' 

Answer 3

如前所述，它其實並不重要，你先走。但最常用的算法是tree traversal。如果這棵樹被組織，我認爲，中序將建議的方式：

（維基百科）要在序遍歷一個非空的二叉樹，在每個節點遞歸執行以下操作：

1. 特拉弗斯左子樹。
2. 訪問根目錄。
3. 遍歷右側子樹。

（這也被稱爲對稱遍歷。）