tree - 树的高度 - PROLOG

Question

我尝试在 Prolog 中编写一个谓词来查找树的高度。

我的树是这样表示的:

             A
           /    \
          B      C
         / \    / \
        D   E  F   G

[a,[b,[d,e],c[f,g]]]([根，[子级]])

我的谓词是:

height(Tr,0) :- 
   atomic(Tr).
height([L|R],N) :- 
   height(L,N1),
   height(R,N2), 
   N is max(N1,N2)+1. 

但是我的代码不起作用。当我写:

height([a,[b,[d,e],c,[f,g]]],N).

N 等于 8。

请问我可以帮忙吗？

注意:根的高度从 0 开始。

Answer 1

它有助于找到正确的抽象。

给定一个使用这些约定表示的二叉树:

• 空树由原子nil表示。
• 非空树由结构tree/3表示，其中
  • 第一个参数是节点的有效负载，
  • 第二个参数是左子树(负载整理小于当前节点负载的节点)，
  • 第三个参数是右子树(有效负载整理大于当前节点的节点)

解决方案非常简单:

tree_depth( nil         , 0 ) .   % the depth of an empty tree is 0.
tree_depth( tree(_,L,R) , D ) :-  % the depth of a non-empty tree is computed thus:
  tree_depth(L,L1) ,              % - compute the depth of the left subtree
  tree_depth(R,R1) ,              % - compute the depth of the right subtree
  D is 1 + max(L1,R1)             % - the overall depth is 1 more than the maximum depth in both subtrees.
  .                               %

计算每个节点可以有任意数量的子节点的n 叉树的深度并不复杂。我们将这样表示我们的n叉树:

• 空树再次由原子nil表示。
• 非空树由结构tree/2表示，其中
  • 第一个参数是节点的有效负载
  • 第二个参数是一个包含节点子树的列表(其中任何一个都可能nil)。

解决方案也很简单:

tree_depth( nil       , 0 ) .   % the depth of the empty tree is 0.
tree_depth( tree(_,C) , D ) :-  % the depth of a non-empty tree is computed thus:
  subtree_depth( C , 0 , T ) ,  % - compute the depth of the subtrees of the current node
  D is 1+T                      % - add 1 to that
  .                             %

subtree_depth( []     , D , D ) .   % child subtrees exhausted? unify the accumulator with the result
subtree_depth( [X|Xs] , T , D ) :-  % otherwise...
  tree_depth(X,X1) ,                % - compute the depth of the current subtree
  T1 is max(T,X1) ,                 % - set the accumulator the max value
  subtree_depth( Xs , T1 , D )      % - recurse down on the tail.
  .