algorithm - バイナリツリー：バイナリツリーでのプレオーダー、ポストオーダートラバーサルの利点は？

Question

二分探索木の順序を逆にすると、ノードが昇順で生成されます。しかし、プレオーダーとポストオーダーのトラバーサルは、バイナリツリーにどのような利点がありますか？

編集：私が利点とは、「プレオーダーまたはポストオーダートラバーサルを適用することが特に適している状況」です。

Answer 1

すべての二分木に数字があるわけではありません。二分木を使用して、式などのツリー構造を表すものを表すことができます。たとえば、次の2 * 3 + 4ように表すことができます。

              +
            /   \
           *     4
         /   \
        2     3

そのような式を表す場合、順序どおりのトラバーサルにより、次の「通常の」中置表記が得られます

2 * 3 + 4

しかし、ポスト オーダー トラバーサルでは、次の式の逆ポーランド記法が生成されます。

2 3 * 4 +