检查树是否是 prolog 中的 avl-tree. 错误

Question

我的程序无法正常工作。当我尝试测试它时，我遇到了一个错误。

我的测试示例：

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.

Answer 1

您的示例代码肯定沿着正确的轨道前进，但有一些异常。

让我们从二叉树的简单表示开始：

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