prolog - Prolog でのツリーポストオーダートラバーサル

Question

ツリートラバーサルとは、ツリーデータ構造の各ノードを体系的に訪問するプロセスを指します。postorder次の画像の走査

戻りますA, C, E, D, B, H, I, G, F (left, right, root)。PREORDERトラバーサルの Prolog コードは次のとおりです。

preorder(tree(X,L,R),Xs) :-
    preorder(L,Ls),
    preorder(R,Rs),
    append([X|Ls],Rs,Xs).

preorder(void,[]).

postorder トラバーサルを実装するために上記のコードを変更したいと思います。

score 5 · Accepted Answer

皆さん、リストを記述するときは DCG の使用を検討してください。たとえば、次のようになります。

preorder(void) --> [].
preorder(tree(X, L, R)) -->
        [X],
        preorder(L),
        preorder(R).

使用法：

?- phrase(preorder(Tree), List).

[X] をシーケンスのどこに配置するかを決めるだけで、さまざまな順序が得られます。

score 0 · Accepted Answer

ポストオーダーの場合、左のブランチをトラバースしてノード値のリストを取得しLeft、次に右のブランチをトラバースしてノード値のリストを取得し、Right最後に左、右、およびの連結を返す必要がありnode valueます。

したがって、コードを変更すると、結果のリストをインスタンス化する方法を再配置することになります。

postorder(tree(X, L, R), Xs):-
  postorder(L, Ls),
  postorder(R, Rs),
  append(Ls, Rs, Xs1),
  append(Xs1, [X], Xs).
postorder(void, []).

ただし、このコードは末尾再帰ではないという意味で最適ではないことに注意してください。アキュムレータを使用して実装することを検討する必要があります。

prolog - Prolog でのツリー ポストオーダー トラバーサル