1

我的程序工作不正常。当我尝试对其进行测试时，我遇到了错误。

我的测试示例：

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

1 回答 1

0

您的示例代码绝对是正确的，但有一些异常情况。

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

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

如果任何节点的两个子子树的高度最多相差 1，则二叉树是 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-26T01:01:05.597 回答