How to add a leaves to a tree in Prolog

0
votes

I am studying binary tree in Prolog and I have some problem to add leaves to a specific b-tree.

I have the following predicates that add a single leaf to a b-tree:

addLeaf(nil, X, t(nil, X, nil)).

addLeaf(t(Left, X, Right), X, t(Left, X, Right)).

addLeaf(t(Left, Root, Right), X, t(Left1, Root, Right)) :- 
    gt(Root, X), addLeaf(Left, X, Left1).

addLeaf(t(Left, Root, Right), X, t(Left, Root, Right1)) :-
    gt(X, Root), addLeaf(Right, X, Right1).

gt(Element1, Element2) :- Element1 @> Element2.

This is pretty simple and I think that I have not problem with it.

My problem is related about to use it to perform query that add more then a single leaf to a bin tree,

For example if, in the Prolog shell, I perform the following statement:

[debug]  ?- addLeaf(nil, 6, Tree).
Tree = t(nil, 6, nil).

the original tree is nil (there is no tree), so add a new leaf is equivalent to create a new tree (called Tree) that have the element 6 as root.

Now my problem is: "I have create a new tree, that corresponds to the Tree variable, what have I to do to add others leaves to this tree?"

Because, if now I try to perform the following statement:

[debug]  ?- addLeaf(Tree, 6, NewTree).
Tree = nil,
NewTree = t(nil, 6, nil)

I obtain that Tree = nill (also if I had just created it in the previous statement. Evidently the Tree variable (in the two statement) are independent of each other, evidently the variables are independent of each other.

So I try to perform:

[debug]  ?- addLeaf(nil, 6, Tree), addLeaf(Tree, 8, NewTree).
Tree = t(nil, 6, nil),
NewTree = t(nil, 6, t(nil, 8, nil)).

and it work fine adding the 8 element as the right child of 6 (according to the b-tree rules)

But, I am asking if, in the Prolog shell, is it possible do something this:

create new tree.
add a leaf.
add another leaf.
add another leaf.
...
...

without declare all the operation in an unique statement, some idea about it?

2
prolog
have a look at assert. - User
you are missing the functor t in the 3rd arg of the 3rd clause of addLeaf. - Will Ness
Tnx, I have correct the typo error in this rule - AndreaNobili

2 Answers

1
votes

You can reuse top-level bindings in SWI Prolog:

6 ?- X = a(_).

X = a(_G236) 

7 ?- Z = $X.

Z = a(_G269)
1
votes
?- addLeaf(nil, 6, Tree).
Tree = t(nil, 6, nil).

?- addLeaf($Tree, 7, NewTree).
NewTree = t(nil, 6, t(nil, 7, nil)).

?- addLeaf($NewTree, 4, NewTree2).
NewTree2 = (t(nil, 4, nil), 6, t(nil, 7, nil)) .

this sample uses top level variables (a feature of SWI-Prolog). Judging from NewTree2, it seems you have a typo in your code.