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

Question

如何用prolog替换二叉树中的匹配节点？树的属性：它不是二叉查找树，但每个元素都是唯一的，所以替换操作最多会影响树中的一个元素。

初始树的定义：

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

比方说，新的节点与树（ '新'，树（ 'child1' 来代替节点 'R'，空，空），树（ '的child2'，空，空）） 预期的结果：

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（编码为元素/ 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. 

Answer 2

保存到一个文件，并readi如果你有一个Prolog术语，你可以从一个文件中读取它，并使用ISO Prolog read_term和write_term将它写入文件。

在 't.txt' 一个文件，你可以有：

tree(b, tree(a, empty, empty), tree(c, empty, empty)). 

，然后从顶层：

?- open('t.txt', read, File), read_term(File, Tree, []), close(File). 
File = <stream>(0x1a38450), 
Tree = tree(b, tree(a, empty, empty), tree(c, empty, empty)). 

这是你的Prolog实现的人工全押。我正在使用SWI-Prolog进行演示。

那么，你的树以任何特定的方式组织？它没有说，但假设它是一个二叉搜索树，在文件tree.pl：

% insert(T0, E, T1) 
% Adding E to the binary search tree T0 results in T1. 
insert(empty, E, tree(E, empty, empty)). 
insert(tree(X, Left, Right), E, tree(X, Left1, Right)) :- 
    E @< X, 
    insert(Left, E, Left1). 
insert(tree(X, Left, Right), E, tree(X, Left, Right1)) :- 
    E @> X, 
    insert(Right, E, Right1). 

然后，

?- [tree]. 
true. 

?- open('t.txt', read, File), 
    read_term(File, Tree, []), 
    insert(Tree, x, T1), 
    close(File). 
File = <stream>(0x1a20e80), 
Tree = tree(b, tree(a, empty, empty), tree(c, empty, empty)), 
T1 = tree(b, tree(a, empty, empty), tree(c, empty, tree(x, empty, empty))). 

...等等。