How to replace a matched node in a binary tree with prolog? Properties of tree: it is not a binary search tree, but every element is unique, so replace operation will effect one element in tree at maximum.
initial tree definition:
tree('Q',
tree('P',
tree('R',
empty,
empty),
tree('S',
empty,
empty)),
tree('T',
empty,
empty))
Let's say new node to replace node 'R' with tree('new', tree('child1', empty, empty), tree('child2', empty, empty)) expected result:
tree('Q',
tree('P',
tree(tree('new',
tree('child1',
empty,
empty),
tree('child2',
empty,
empty)),
tree('S',
empty,
empty)
)),
tree('T',
empty,
empty))
Current status of the code:
:- 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).
I've changed a bit the syntax of your tree, since it was too much verbose for my taste. Maybe you could consider using a supported tree format, like XML (coded as element/3), that would give you much power in pattern matching, via library(xpath). Anyway
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).
yields
?- 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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments