從樹的根部找到節點X的路徑

Question

我想問你對我想在Prolog中編寫的程序的幫助。我想做一個函數path(X,tree,Path)，它從樹的根目錄找到節點X的路徑。基本上，我認爲會有三句話。

1. path(X, void, [])，返回空列表，因爲沒有樹
2. path(X,tree(X,void,void),[X])，返回包含樹根
3. path(X,tree(Route,Left,Right),Path)，的元素列表?????????

我相信有3個句子，我知道他們中的2個，但我不知道第三個是什麼。誰能幫我？謝謝。

Answer 1

你的第3條）應該添加在返回路徑的前面當前節點，並在分支遞歸

path(X, tree(Route, Left, Right), [Route|Path]) :- 
    path(X, Left, Path) ; path(X, Right, Path). 

注意的脫節（;）/ 2。該規則將首先嚐試左邊，並在回溯時右邊的分支。

Answer 2

你的規則只適用於這種情況：

- 路徑（3，樹（1，樹（2，無效的，無效），樹（3，無效的，無效）），X）？ X = [1,3]。 - 樹中有三個節點。

但如果我嘗試在樹中添加更多的節點，它不起作用。看下面的例子： ？ - path（7，tree（1，tree（2,4,5），tree（3,6,7）），X）。 錯誤。 答案必須是X = [1,3,7]。