1

如果树是 AVL 树或不使用 prolog，我正在尝试实现测试。

我做了一个高度测试，适用于我迄今为止所做的测试，但我的平衡测试仍然不强。

这是我到目前为止的工作：

avl('Branch'(LeftBranch,RightBranch)) :-
  height(LeftBranch,H1),
  height(RightBranch,H2),
  abs(H1-H2) =< 1.

我基于旧的 stackoverflow 代码中的代码。但它并不适用于所有情况。将包括我的身高代码。在某个地方我犯了一个错误，我确定在哪里可以找到它。

height(leaf(_),1).
height('Branch'(LeftBranch,RightBranch,H) :-
  height(LeftBranch,H1),
  height(RightBranch,H2),
  H is max(H1,H2)+1.

为什么我的代码不评估某些树？

Prolog - 平衡树与否

这是我基于平衡树测试的线程，我确实尝试过他在评论中发布的树，但我失败了，有什么想法吗？

4

2 回答 2

1

代码看起来还不错，也许缩进数据并使用与注释中相同的函子可以提供帮助：

t :- avl(b(l(1),
           b(l(2),
             b(l(3),
               b(l(4),
                 l(5)
                )
              )
            )
          ),
         b(l(6),
            b(l(7),
              b(l(8),
                b(l(9),
                  l(10)
                 )
             )
          )
        )
    ).

avl(LeftBranch,RightBranch) :-
  height(LeftBranch,H1),
  height(RightBranch,H2),
  abs(H1-H2) =< 1.

height(l(_),1).
height(b(LeftBranch,RightBranch),H) :-
  height(LeftBranch,H1),
  height(RightBranch,H2),
  H is max(H1,H2)+1.

手动格式化很麻烦。如果您使用 SWI-Prolog，IDE 将为您完成，只需在每个逗号后放置一个换行符。

测试：

?- t.
true.
于 2012-08-30T00:16:35.850 回答
1

AVL 树的每个分支首先应该是 AVL 树本身。只有当这是真的，你才应该比较高度。

chac 答案中的树显然是不平衡的，但您的代码认为它可以。它不是。

然后，错别字。如果您使用短名称，则不太可能发生。

avl_height(b(L,R),H) :-
  avl_height(L,h(H1)), 
  avl_height(R,h(H2)), 
  abs(H1-H2) =< 1, !,
  H3 is 1 + max(H1,H2), H=h(H3).

avl_height(b(_,_),not).

avl_height(l(_),h(1)).
于 2012-08-30T07:20:48.707 回答