ツリーデータ構造を解析する方法は？

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アルゴリズム。この木は、私の考え方を整理している場合、inorderを推奨することになります。

（ウィキペディアより）各ノードで再帰的に次の操作を実行し、inorderを非空のバイナリツリーを走査するには：

1. トラバースを左のサブツリー。
2. ルートにアクセスしてください。
3. 右のサブツリーを走査します。

（これは、対称トラバーサルと呼ばれている。）