Prologにおけるツリープリオーダートラバーサル

Question

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

Sorted_binary_tree

戻りF、B、A、D、C、E、G、I、H（ルート、左、右）。

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

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

Answer 1

サイズのためにこれを試してみてください：（Tのバインディングを表示せずに）それを試し

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))). 

：

hereからツリーを表す事実と

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), 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することができます。

Answer 2

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

リーフ述語は、受信したアキュムレータをその逆に統一して戻します。

ルートコールには空のアキュムレータがあります。