tree - Prolog中的有序树遍历

Question

我是 Prolog 新手，我正在尝试编写一个有序树遍历，其中给出了一系列事实，例如:

leftSubtree(9, 7).
leftSubtree(7, 1).
leftSubtree(1, -2).
leftSubtree(11, 9).
leftSubtree(16, 13).
leftSubtree(3, 2).
rightSubtree(9, 11).
rightSubtree(7, 6).
rightSubtree(1, 3).
rightSubtree(11, 16).
rightSubtree(16, 19).

我可以使用 inOrder(9,X)。按顺序打印出一棵树。我尝试使用以下有效的代码，但希望有更简单的东西。任何提示或帮助将不胜感激。

inOrder(Root, X):-
   \+ leftSubtree(Root,Left),
   \+ rightSubtree(Root,Left) ->
   X = [Root];
   leftSubtree(Root,Left), 
   rightSubtree(Root,Right)->
   inOrder(Left, LeftNode),
   inOrder(Right, RightNode),
   append(LeftNode,[Root|RightNode],X);
   leftSubtree(Root,Left), 
   inOrder(Left, LeftNode),
   append(LeftNode,[Root],X);
   rightSubtree(Root,Right)->
   inOrder(Right, RightNode),
   append([Root],RightNode,X).

Answer 1

您的代码可以得到简化，避免负面测试，并使用 Prolog 的一些自反性。

inOrder(Root, [Left, Root, Right]) :-
  inOrder(leftSubtree, Root, Left),
  inOrder(rightSubtree, Root, Right).

inOrder(BranchToExplore, Root, Subtree) :-
   call(BranchToExplore, Root, Branch)
   ->  inOrder(Branch, Subtree)
   ;   Subtree = [].

这将恢复树的结构，作为嵌套的三元列表，然后一次调用 flatten/2 就足以使其扁平，如下所示您原来的要求。

?- inOrder(8, Tree), flatten(Tree, L).
Tree = [[[[[], -2, []], 1, [[[], 2, []], 3, []]], 5, [[], 6, []]], 8, [[[], 9, [[], 10|...]], 11, [[[], 13|...], 16, [...|...]]]],
L = [-2, 1, 2, 3, 5, 6, 8, 9, 10|...].

如果您的 Prolog 没有 call/N，您可以使用 univ 构建一个可调用术语:

inOrder(BranchToExplore, Root, Subtree) :-
  ( Callable =.. [BranchToExplore, Root, Branch], call(Callable) )
  ->  inOrder(Branch, Subtree)
  ;   Subtree = [].

如果我们交换 Left 和 Root，我们就会得到更有用的 preOrder 表示形式:preOrder(Root, [Root, Left, Right]) :- ...。

在 preOrder 中拥有树的结构对于进一步的处理很有用:一个“准备就绪”并且在 SWI-Prolog 中有用的实现，它是 XML，其中树表示为元素(标签、属性、子树)，并且可以由 library(xpath) 处理。更改 inOrder/2 和 inOrder/3 来恢复 XML 可能是一个有用的练习。