0

ツリートラバーサルとは、体系的な方法でツリーデータ構造内の各ノードにアクセスするプロセスを指します。次の画像のプレオーダートラバーサル

Sorted_binary_tree

F、B、A、D、C、E、G、I、H（ルート、左、右）を返します。これはPrologコードです：

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

私は返すプロローグプログラムを書きます

F、B、A、F、B、D、C、F、B、D、E、F、G、I、H

つまり、ツリーのパスです。助言がありますか？

4

2 に答える 2

0

左/右の訪問者に渡す前に、現在のノードPathToRootをconsする引数を追加します。

葉の述語は、受け取ったアキュムレータを返す前にその反転を統合します。

ルート呼び出しには空のアキュムレータがあります。

于 2012-04-11T06:38:10.077 に答える
0

サイズについてこれを試してください：

dfs_paths(tree(X, void, void), [X]) :- !.
dfs_paths(tree(X, L, _R), [X|Xs]) :-
    dfs_paths(L, Xs).
dfs_paths(tree(X, _L, R), [X|Xs]) :-
    dfs_paths(R, Xs).

ここからツリーを表すファクトを使用してテストします。

tree(T) :- T = tree(f, tree(b, tree(a,void,void), tree(d,tree(c,void,void),tree(e,void,void))), tree(g, void, tree(i, tree(h,void,void),void))).

試してみます ( のバインディングを表示せずにT):

?- tree(T), dfs_paths(T, L).
L = [f, b, a] ;
L = [f, b, d, c] ;
L = [f, b, d, e] ;
L = [f, g, i, h]

dfs_paths/2代替パスを提供するためにバックトラックすることに注意してください。それらすべてのリストを前もって知りたい場合は、次を試すことができます。

?- tree(T), findall(P, dfs_paths(T, P), Ps).
Ps = [[f, b, a], [f, b, d, c], [f, b, d, e], [f, g, i, h]].

上で書いたように用語のフラットなリストが必要な場合はflatten/2、結果を得ることができます。

于 2012-04-11T08:10:26.553 に答える