binary-search-tree - inorder、preorder、postorder トラバーサルをいつ使用するか

Question

二分探索木で順序、前順、および後順トラバーサルを行う方法の背後にあるコードを理解しています。しかし、私はアプリケーションについて混乱しています。

それぞれいつ使うの？それぞれのトラバーサル方法が最も有効なケースを示すことは、非常に役に立ちます。

ありがとう！

Answer 1

インオーダートラバーサルは、定義された順序でアイテムを処理するだけです。たとえば、単語または名前のリストのBSTがある場合、順序トラバーサルはそれらを順番に出力します。

プレオーダーおよびポストオーダートラバーサルは、ほとんどの場合、二分探索木以外のツリーに適用されます。たとえば、のような式を評価するにはA + B * C、次のようなツリーを作成できます。

式を評価するには、ポストオーダーでツリーを走査し、各サブツリーの値に各演算子を適用します。

たとえば、Lispのような言語で出力を生成したい場合は、プレオーダートラバーサルをほぼ同じ目的で使用できます。そのため、式は。として出力され(add A (mul B C))ます。