insert(I， []， [I，[]，[]]).如何插入二叉树?

Question

要向堆中添加新元素，必须:

1. 创建包含此元素值的节点
2. 在最后一层的第一个空的地方打这个结，尽可能远的左边(创建一个如有必要，可设置新关卡)。我们总是得到一个完整的二叉树，但不一定是堆。

我写了以下代码:

insert(I, [], [I, [], [] ] ).
insert(I, [R, G, D], N):-
depth(G, P1), depth(D, P2), P1=<P2, insert(I, G, N1), mix3(R, N1, D, N)
;  depth(G, P1), depth(D, P2), P1>P2, insert(I, D, N2), mix3(R, G, N2, N).

depth([], 0).
depth([_, Y, Z], H):-depth(Y, H1), depth(Z, H2), max(H1, H2, H3), H is 1+H3.
mix([], L2, L2).
mix([H|T], L2, [H|R]):-mix(T, L2, R).
mix3([], L1, L2, N):-mix(L1, L2, N).
mix3([H|L], L1, L2, [H|N]):-mix3(L, L1, L2, N).

查询执行时间:

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

我得到:false.

为什么?

Answer 1

你的代码的主要问题是:

• 不构建插入后的新树。
• 它不保证树的最后一层的叶子在左边分组。

解决第一个问题，你可以这样修改你的代码:

insert(Item, [], [Item,[],[]]).
insert(Item, [Root, Left, Right], NewTree):-
depth(Left, Dl),
depth(Right, Dr),
(   Dl =< Dr
->  insert(Item, Left, NewLeft),
NewTree = [Root, NewLeft, Right]
;   insert(Item, Right, NewRight),
NewTree = [Root, Left, NewRight] ).
depth([], 0).
depth([_, Left, Right], Depth):-
depth(Left, Dl),
depth(Right, Dr),
Depth is 1 + max(Dl, Dr).
show(Tree) :-
show(Tree, 0).
show([], _) :- !.
show([Root, Left, Right], Depth) :-
NewDepth is Depth + 1,
show(Right, NewDepth),
tab(3*Depth),
writeln(Root),
show(Left, NewDepth).
tree([19,
[18,
[12, [], []],
[15, [], []]],
[17,
[10, [], []],
[16, [], []]]]).

使用修改后的代码版本插入的一些例子(注意，在第二种情况下，叶子3并没有尽可能地向左):

?- tree(Tree), insert(2, Tree, NewTree), show(NewTree).
16
17
10
19
15
18
12
2
...
?- tree(T1), insert(2, T1, T2), insert(3, T2, T3), show(T3).
16
17
10
3
19
15
18
12
2
...

如果叶子位于树的最后一层，则不需要在左侧分组，一个简单的解决方案是:

simple_insert(Item, [], [Item, [], []]) :- !.
simple_insert(Item, [Root, Left, Right], [Root, Right, NewLeft]) :-
simple_insert(Item, Left, NewLeft).

下面是一些使用简单代码插入的示例:

?- foldl(simple_insert, [1,2,3,4,5,6,7], [], T), show(T).
7
3
5
1
6
2
4
...
?- tree(Tree), simple_insert(2, Tree, NewTree), show(NewTree).
2
12
18
15
19
16
17
10
...
?- tree(T1), simple_insert(2, T1, T2), simple_insert(3, T2, T3), show(T3).
3
10
17
16
19
2
12
18
15
...

解决第二个问题，你应该记得高度为H的完整树必须有2^H - 1个节点。因此，当且仅当左侧是完整树且右侧的大小小于左侧的大小时，您应该在右侧插入新项。

% quasi-complete tree insertion
qc_insert(Item, [], [Item, [], []]) :- !.
qc_insert(Item, [Root, Left, Right], NewTree) :-
height(Left, Hl),
size(Left, Sl),
size(Right, Sr),
(   (Sl =:= 2^Hl-1,  % Left is complete and
Sr < Sl)        % Right has less items than Left
->  qc_insert(Item, Right, NewRight), 
NewTree = [Root, Left, NewRight]
;   qc_insert(Item, Left, NewLeft), 
NewTree = [Root, NewLeft, Right] ).
height([], 0).
height([_,L,R], H):-
height(L, Hl),
height(R, Hr),
H is 1 + max(Hl, Hr).
size([], 0).
size([_,Left,Right], S) :-
size(Left, Sl),
size(Right, Sr),
S is 1 + Sl + Sr.

使用正确代码插入的示例:

?- foldl(qc_insert,[1,2,3,4,5],[],T), show(T).
3
1
5
2
4
...
?- tree(Tree), qc_insert(2, Tree, NewTree), show(NewTree).
16
17
10
19
15
18
12
2
...
?- tree(T1), qc_insert(2, T1, T2), qc_insert(3, T2, T3), show(T3).
16
17
10
19
15
18
3
12
2
...

最后一个观察是使用术语表示树更好，而不是列表。因此，例如，树[1, [2, [], []], []]应该表示为t(1, t(2, nil, nil), nil)。

Answer 2

除了程序中的错字(mix3(R, G, N2, G, N))之外，还有一个深度错误:您想将新元素插入中较小的子树。因此，您需要从最小值计算子树的深度。

你用的是哪个prolog ?min/3似乎不是SWI prolog中的内置谓词，所以我使用min/2代替。

这是我的解决方案。我不使用混合谓词。

insert(I, [], [I, [], [] ]):- !.
insert(I, [R, G, D], N):-
depth(G, P1), 
depth(D, P2), 
(   P1=<P2
->  insert(I, G, NN),
N = [R, NN, D]
;   insert(I, D, NN),
N = [R, G, NN]
).
depth([], 0).
depth([_, Y, Z], H):-
depth(Y, H1), 
depth(Z, H2), 
H is 1+min(H1, H2).

切割(!)是不必要的。这些是测试用例(一个查询的输出树是下一个查询的输入树):

?- insert(1, [], N).
N = [1, [], []].
?- insert(21, [1, [], []], N).
N = [1, [21, [], []], []].
?- insert(22, [1, [21, [], []], []], N).
N = [1, [21, [], []], [22, [], []]].
?- insert(31, [1, [21, [], []], [22, [], []]], N).
N = [1, [21, [31, [], []], []], [22, [], []]].
?- insert(32, [1, [21, [31, [], []], []], [22, [], []]], N).
N = [1, [21, [31, [], []], [32, [], []]], [22, [], []]].
?- insert(33, [1, [21, [31, [], []], [32, [], []]], [22, [], []]], N).
N = [1, [21, [31, [], []], [32, [], []]], [22, [33, [], []], []]].
?- insert(34, [1, [21, [31, [], []], [32, [], []]], [22, [33, [], []], []]], N).
N = [1, [21, [31, [], []], [32, [], []]], [22, [33, [], []], [34, [], []]]]
?- insert(41, [1, [21, [31, [], []], [32, [], []]], [22, [33, [], []], [34, [], []]]], N).
N = [1, [21, [31, [41, [], []], []], [32, [], []]], [22, [33, [], []], [34, [], []]]].

似乎有效。