0

式ツリーに解析する必要があるノードで構成されるツリー データ構造があります。私のノードは次のようになります(簡略化):

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

ツリーの最下部を見つけて逆方向に作業して式ツリーを構築するための最良/正しい方法は何ですか? 左または右のどちらを最初に解析しますか?

4

3 に答える 3

1

最初にツリーの最下部に到達したい場合は、「順序どおり」またはおそらく「順序後」の検索を行います。「順序どおり」の検索では、一番下の一番左のノードが最初に検索され、次にそのノードの親が検索され、次に親の右側の子が検索されます。「ポストオーダー」検索は、親ノードにアクセスする前に、左の子ノードと右の子ノードの両方に「アクセス」します。

「x + y」という式を考えてみましょう。順番に検索すると、次のようになります。

'x', '+', 'y'

一方、事後検索では次の結果が得られます。

'x', 'y', '+'
于 2009-06-15T22:41:23.543 に答える
1

前述のように、最初にどこに行くかは問題ではありません。しかし、最も一般的なツリー トラバーサルアルゴリズムです。このツリーが私が考えるように編成されている場合、inorder が推奨されます。

(ウィキペディアから) 空でない二分木を順番にトラバースするには、各ノードで次の操作を再帰的に実行します。

  1. 左のサブツリーをトラバースします。
  2. ルートにアクセスします。
  3. 右のサブツリーをトラバースします。

(これは、対称トラバーサルとも呼ばれます。)

于 2009-06-15T22:42:39.983 に答える
0

あなたが最初にどちらの方向を横断するかは重要ではないと思います。ただし、左から右への言語が支配的な世界では、最初に左に行くと、誰かがあなたのコードをより直感的に理解するでしょう。

于 2009-06-15T22:30:41.960 に答える