Prologにおけるツリーポストオーバトラバーサル

Question

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

Sorted_binary_tree

戻りA, C, E, D, B, H, I, G, F (left, right, root)次の画像におけるpostorderトラバーサル。 PREORDERトラバーサルのためのプロローグコードは、私が後順トラバーサルを実装するために上記のコードを変更したい

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

preorder(void,[]). 

です。

Answer 1

ポストオーダーの場合は、左側のブランチをトラバースしてノード値のリスト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, []). 

注：

したがって、あなたのコードを変更することは、あなたが結果のリストをインスタンス化する方法を再配置することです。アキュムレータを使用して実装することを検討する必要があります。

Answer 2

人々、例えば、リストを記述する際DCGsの使用を検討してください：

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

使用法：

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

あなたは順番に、[X]を配置する場所を簡単に決めることにより、異なる順序を取得。