在prolog中檢查樹是否是avl-tree。錯誤

我的程序無法正常工作。當我嘗試測試它時，我有一個錯誤。在prolog中檢查樹是否是avl-tree。錯誤

我用於測試示例：

if_avl_tree(t(t(t(nil/0, 3, nil/0)/1, 7, t(t(nil/0, 9, nil/0)/1, 11, nil/0)/2)/3, 16, t(nil/0, 25, t(nil/0, 40, nil/0)/1)/2)/4).

這是我的代碼：

if_avl_tree(t(_,_,_)/_) :- T=t(_,_,_)/_ , is_binTree(T), if_avl_tree(T, _), !. 
if_avl_tree(nil/0, 0). 
if_avl_tree(t(nil/0,_, nil/0), 1). 
if_avl_tree(t(L,_,R)/H, Hh) :- if_avl_tree(L, H1), 
           if_avl_tree(R, H2), abs(H1 - H2) =< 1, !,                      
           H3 is 1 + max(H1,H2), H3=:=Hh. 

is_binTree(nil/0) :- !. 
is_binTree(t(L,_,R)/_):- is_binTree(L), is_binTree(R).

這是我的錯誤：

ERROR: Arguments are not sufficiently instantiated 
ERROR: In: 
ERROR: [10] 1=:=_6218 
ERROR: [8] if_avl_tree(t(...,16,...)/4) at e:/prolog/tasks/lab06tomashchuk.pl:50 
ERROR: [7] <user> 
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization. 
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.

來源

2017-03-25 Philimon_kf

'=：=/2'評估表達式參數並測試相等性。所以它要求表達式是可評估的。如果由於未綁定的變量而無法評估任何一個，它會告訴您參數沒有充分實例化。在你的術語'H3 =：= Hh'中，'H3'或'Hh'沒有被綁定。這個聲明的目的是什麼？只是將'H3'分配給'Hh'？如果是這樣，那沒有必要。在這種情況下，刪除該語句並在謂詞子句的頭部使用'H3'而不是'Hh'。 – lurker

爲什麼你有所有這些削減（'！'）？不要使用剪切手。當你不需要它們時，將它們用於修剪其他有效解決方案的特定目的。但如果你不確定，就從沒有它們開始。 – lurker

爲什麼'無/ 0'？單是不夠？ – false

你的示例代碼，絕對是沿着正確的軌道，但有一些失敗。

讓我們先從一個二叉樹的簡單表示：

btree(Value, Left, Right)

這是非常自我解釋。如果沒有子樹，則可以使用原子nil。

如果我們想驗證結構是否是二叉樹，我們可以這樣來做：

is_binary_tree(nil). % Allow for a nil tree with no values 
is_binary_tree(btree(_, Left, Right)) :- 
    is_binary_tree(Left), 
    is_binary_tree(Right).

二叉樹爲AVL如果任何節點的兩個子子樹的高度，在不同的最多的一個。如果您的二叉樹表示已經擁有每棵樹的高度爲樹表示，像這樣的一部分：

btree(Value, Left, Right)/Height

然後，它必須假定當樹內容或結構改變時Height維持。如果它們沒有被改變，那麼關於它是否是AVL樹的決定不需要和額外的高度參數被攜帶。高度已預先計算和維護，所以他們只需要檢查：

is_AVL_tree(nil/0). 
is_AVL_tree(btree(_, Left, Right)/_) :- 
    Left = btree(_, _, _)/HeightLeft, 
    Right = btree(_, _, _)/HeightRight, 
    abs(HeightLeft - HeightRight) =< 1, 
    is_AVL_tree(Left), 
    is_AVL_tree(Right).

你並不需要一個單獨的基本情況爲它是由上述兩種規則照顧的1的高度。

如果您沒有通過維護樹來預先確定高度作爲該術語中的一個參數，那麼我們需要沿着高度作爲參數來計算它們。 t不需要作爲樹表示的一部分。這將是多餘的，並使規則不必要地混亂。

is_AVL_tree(nil, 0). 
is_AVL_tree(btree(_, Left, Right), Height) :- 
    is_AVL_tree(Left, HeightLeft), 
    is_AVL_tree(Right, HeightRight), 
    abs(HeightLeft - HeightRight) =< 1, 
    Height is 1 + max(HeightLeft, HeightRight).

來源

2017-03-26 01:01:05 lurker

在prolog中檢查樹是否是avl-tree。錯誤

回答

相關問題