prolog - 替换二叉树的匹配位置的树节点

Question

如何用 prolog 替换二叉树中的匹配节点？树的性质:它不是二叉搜索树，但每个元素都是唯一的，因此替换操作最多只会影响树中的一个元素。

初始树定义:

tree('Q',
     tree('P',
          tree('R',
               empty,
               empty),
          tree('S',
               empty,
               empty)), 
     tree('T',
          empty,
          empty))

假设用新节点替换节点“R”为tree('new',tree('child1',empty,empty),tree('child2',empty,empty)) 预期结果:

tree('Q',
     tree('P',
          tree(tree('new',
               tree('child1',
                    empty,
                    empty), 
               tree('child2',
                    empty,
                    empty)),
          tree('S',
                empty,
                empty)
               )),
     tree('T',
          empty,
          empty))

代码的当前状态:

:- dynamic([tree/1]).

run:-
 retractall(tree(_)),
 assertz(tree(tree('Q', tree('P', tree('R', empty, empty), tree('S', empty, empty)), tree('T', empty, empty)))),
 retract(tree(T)),
 insert('newElement', T, NewTree),
 assertz(tree(NewTree)),
 tree(T),write(T),!.


insert(NewItem,empty,tree(NewItem,empty,empty)):- !.

insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):-
   true, %match function needs to be here
   !,insert(NewItem,Left,NewLeft).

insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):-
    insert(NewItem,Right,NewRight).

Answer 1

我对你的树的语法做了一些更改，因为它对我来说太冗长了。 也许您可以考虑使用受支持的树格式，例如 XML(编码为 element/3)， 通过库(xpath)，这将为您提供模式匹配的强大功能。无论如何

replace_tree(Old, New, Old, New).

replace_tree(Old, New, t(Key, L, R), t(Key, L1, R1)) :-
    replace_tree(Old, New, L, L1),
    replace_tree(Old, New, R, R1).

% base case of the recursive data structure
replace_tree(_Old, _New, t, t).

产量

?- T=t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(3,t,t))),t), replace_tree(t(3,X,Y),t(new,X,Y),T,O).
T = t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(3, t, t))), t),
X = t(4, t, t),
Y = t(5, t, t),
O = t(1, t(2, t(new, t(4, t, t), t(5, t, t)), t(6, t, t(3, t, t))), t) ;
T = t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(3, t, t))), t),
X = Y, Y = t,
O = t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(new, t, t))), t) ;
T = O, O = t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(3, t, t))), t) ;
false.