插入（I，[]，[I，[]，[]]）。如何向二叉树插入一个值？

要将新元素添加到堆中，我们必须：

1. 创建一个包含该元素值的节点，
2. 在最后一层的第一个空位置尽可能向左打结（如有必要，创建一个新层）。我们总是得到一个完整的二叉树，但不一定是一个堆。

我写了这段代码：

insert(I, [], [I, [], [] ] ).
insert(I, [_, G, D], N):-
   depth(G, P1), depth(D, P2), P1<P2, insert(I, G, N).
insert(I, [_, G, D], N):-
   depth(G, P1), depth(D, P2), P1>P2, insert(I, D, N).

depth([], 0).
depth([_, Y, Z], H):-
   depth(Y, H1), depth(Z, H2), max(H1, H2, H3), H is 1+H3.

但是当执行这个查询时，它失败了：

?- insert(2, [19, [18, [12, [], []], [15, [], []]], [17, [10, [], []], [16, [], []]]], N).
false.

Why?

（（你没有定义max/3在你的程序中。我猜是下面的））

max(A, B, M) :-
   M is max(A,B).

Why?

首先，总是从小例子开始。就像一棵只有一个元素的树。这也失败了：

?- insert(2, [12, [], []], N).
false.

所以为什么？如果一个（纯粹的、单调的）程序失败了，那么我们需要对其进行概括。让我们像这样尝试一下：

:- op(950, fy, *).
*(_).

insert(I, [], [I, [], [] ] ).
insert(I, [_, G, D], N):-
   depth(G, P1),
   depth(D, P2),
   P1<P2,
   * insert(I, G, N).
insert(I, [_, G, D], N):-
   depth(G, P1),
   depth(D, P2),
   P1>P2,
   * insert(I, D, N).
  

因此，这些递归目标已通过添加*前面的概括显然太过分了。然而，查询仍然失败！所以这些P1<P2, P1>P2比较似乎是罪魁祸首。如果它们相同会发生什么？那么这两条规则都不适用。所以你显然忘记考虑这种情况。

但还有一个问题，让我们忽略这些比较，看看会发生什么：

insert(I, [], [I, [], [] ] ).
insert(I, [_, G, D], N):-
   depth(G, P1),
   depth(D, P2),
   * P1<P2,
   insert(I, G, N).
insert(I, [_, G, D], N):-
   depth(G, P1),
   depth(D, P2),
   * P1>P2,
   insert(I, D, N).

?- insert(2, [12, [], []], N).
   N = [2,[],[]]
;  N = [2,[],[]].
?- insert(2, [19, [18, [12, [], []], [15, [], []]], [17, [10, [], []], [16, [], []]]], N).
   N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]].
  

这可以吗？无论我们从哪棵树开始，我们总是会得到一个解决方案。因此，无论您想在哪里插入新元素，您都必须解决这个问题。

如果我在，请考虑使用clpfd /questions/tagged/clpfd via library(clpz)或其稍微过时的前身library(clpfd)代替(>)/2等等，因为这不会给你带来那么多错误。

See 这个答案 https://stackoverflow.com/a/30791637/772868了解更多针对 Prolog 的调试方法。