1

ツリーの PreOrder トラバーサルには、次の Prolog 述語があります。

preOrder(nil, []).
preOrder(node(X, nil, nil), [X]).
preOrder(node(X, L, _), [X|T]) :- preOrder(L, T).
preOrder(node(X, _, R), [X|T]) :- preOrder(R, T).

問題は、不完全なリストを返すことです。たとえば、次のようになります。

?- preOrder(node(1, node(2, node(3,nil,nil), node(4,nil,nil)), node(5,nil,nil)), L). 
L = [1,2,3]

あるべきときL=[1,2,3,4,5]。

なぜそれは短く止まるのですか？

4

2 に答える 2

1

Prolog が生成する答えを見てください。それは単一のものではありません：

| ?- preOrder(node(1,node(2,node(3,nil,nil),node(4,nil,nil)),node(5,nil,nil)),L).
L = [1,2,3] ? ;
L = [1,2,3] ? ;
L = [1,2,3] ? ;
L = [1,2,4] ? ;
L = [1,2,4] ? ;
L = [1,2,4] ? ;
L = [1,5] ? ;
L = [1,5] ? ;
L = [1,5] ? ;
no

各ルールは、他の部分とは独立して一部を記述します。しかし、それらをまとめて説明する必要があります。

これを解決する最善の方法は、DCG を使用することです

于 2014-11-26T15:12:00.953 に答える
-1

2 つの再帰句があり、それぞれがツリーの一方の側にだけ移動するため、短く停止しています。2 つ目のケースは必要ありませんが、2 つの基本ケースもあります。

したがって、2 番目の句を削除し、2 つの再帰句を 1 つの句に結合して、両方の分岐からの結果を追加します。

例えば：

preOrder(nil, []).
preOrder(node(X, L, R), [X|T]) :- 
  preOrder(L, LT), 
  append(LT, RT, T), 
  preOrder(R, RT).

トラバーサルにアキュムレータを使用することもできます。

preOrder(Tree, List):-
  preOrder(Tree, [], RList),
  reverse(RList, List).

preOrder(nil, List, List).
preOrder(node(X, L, R), List, NList) :- 
    preOrder(L, [X|List], MList), 
    preOrder(R, MList, NList).

あるコメンターが言ったように、 preOrder no のこれらの定義は、トラバーサルが与えられたツリーを生成するために正しく機能しないことに注意してください。

DCG を使用して、内部的にオープン リストを使用して可逆的な手順を定義することができます。

preOrder(nil)-->[].
preOrder(node(X, L, R))-->[X], preOrder(L), preOrder(R).

そして、次のように呼び出しますphrase/2。

?- phrase(preOrder(node(1, node(2, node(3,nil,nil), node(4,nil,nil)), node(5,nil,nil))), L).
L = [1, 2, 3, 4, 5].
于 2014-11-26T15:13:33.940 に答える