1

我需要实现一个谓词isBalanced/1，isBalanced(T)如果T是一棵平衡的树，则该谓词是正确的。

在这种情况下，二叉树由结构 node(left,right) 定义，其中 left 和 right 可以是另一个节点或任何 Prolog 数据项。

到目前为止我所拥有的：

height(node(L,R), Size) :-
    height(L, Left_Size),
    height(R, Right_Size),
    Size is Left_Size + Right_Size + 1 .
height(l(_),1).

isBalanced(l(_)).
isBalanced(node(B1,B2)):-
    height(B1,H1),
    height(B2,H2),
    abs(H1-H2) =< 1,
    isBalanced(B1),
    isBalanced(B2).

预期输出：

?- isBalanced(1).
true.
?- isBalanced(node(1,2)).
true.
?- isBalanced(node(1,node(1,node(1,2)))).
false.

它不起作用，任何建议将不胜感激！

4

1 回答 1

3

你如何代表你的树？在我看来

  • l(_)表示空树，并且
  • node(L,R)表示一棵非空树。

而且我怀疑您height/2有一个错误，因为您似乎已将空树的高度定义为 1（而不是 0）。

我可能会如下表示一棵二叉树：

  • nil— 空树

  • tree(D,L,R)— 一棵非空树，其中

    • D: 有效载荷数据
    • L: 左子树
    • R: 右子树

这样可以代表树

    a
   / \
  b   c   
 /   / \
d   e   f

作为

tree( a ,
  tree( b ,
    tree( d , nil , nil ) ,
    nil
  ) ,
  tree( c ,
    tree( e , nil , nil ) ,
    tree( f , nil , nil ) 
) .

叶节点（没有子树的树）看起来像

tree( data , nil , nil )

余额的确定

所以，从那个表示和定义开始工作

如果满足以下条件，则二叉树是平衡的：

  • 它的左子树是平衡的
  • 它的右子树是平衡的
  • 子树各自的高度相差不超过1

我们可以很容易地为这个问题写一个描述性的解决方案：

is_balanced( nil         ) .  % the empty tree is balanced
is_balanced( tree(_,L,R) ) :- % a non-empty tree is balanced IF ...
  is_balanced(L) ,            % - the left sub-tree is balanced
  is_balanced(R) ,            % - the right sub-tree is balanced
  tree_height(L,LH) ,         % - the height of the left sub-tree
  tree_height(R,RH) ,         % - the height of the right sub-tree
  abs( LH - RH ) < 2          % - differ by no more than 1
  .                           % Right?

我们只需要计算一棵树的高度。

高度计算

可以如下计算这样一棵树的高度：

tree_height( nil         , 0 ) .  % the depth of an empty tree is zero.
tree_height( tree(_,L,R) , H ) :- % for a non-empty tree...
  tree_height( L , LH ) ,         % - we compute the height of the left subtree
  tree_height( R , RH ) ,         % - we compute the height of the right subtree
  H is 1 + max( LH , RH )         % - the overall height is 1 more than the higher of the two values thus obtained.
  .                               % Right?

效率

有人可能会注意到

  • 似乎发生了很多树遍历，并且
  • is_balanced/2与有可疑的相似之处tree_height/2。

因此，可以通过将两者混合并即时计算深度来优化事物：

编辑：添加了包装谓词is_balanced/1：

is_balanced( T ) :- is_balanced( T, _ ) .

is_balanced( nil         , 0 ) .   % the empty tree is balanced and has a height of zero.
is_balanced( tree(_,L,R) , H ) :-  % a non-empty tree is balanced IF ...
  is_balanced( L , LH ) ,          % - its left subtree is balanced, and
  is_balanced( R , RH ) ,          % - its right subtree is balanced, and 
  abs( LH - RH) < 2 ,              % - their respective heights differ by no more than 1, and
  H is 1 + max( LH , RH )          % - the current tree's height is 1 more than the larger of the heights of the two subtrees.
  .                                % Easy! (And elegant!)
于 2015-06-05T00:57:44.407 回答