subtree program in Prolog

0
votes

I'm trying to write a program for subtree(S,T) where S is a subtree of T.

This is my program, unfortunately it doesn't work and I don't know why. I'm very much a newbie in Prolog, so be gentle please.

subtree(T,T).
subtree(S,tree(X,left,right)) :-
   subtree(S,left).
subtree(S,tree(X,left,right)) :-
   subtree(S,right).
subtree(tree(X,void,void),tree(X,left,right)).
subtree(tree(X,S_left,S_right),tree(X_left,right)) :-
   subtree(S_left,X_left),
   subtree(S_right,X_right).

The first two rules are for finding subtrees that range to the leafs of the tree. The last two rules are supposed to find subtrees that do not range to the leafs.

If I e.g. call 

subtree(tree(one,void,void),tree(one,tree(two,void,void),tree(three,void,void))).

Prolog returns false and I don't know why, doesn't this rule:

subtree(tree(X,void,void),tree(X,left,right)).

capture exactly that query?

1
prolog
subtree(tree(one,void,void),tree(one,tree(two,void,void),tree(three,void,void))). fails because tree(one, void, void) is not a subtree of tree(one,tree(two,void,void),tree(three,void,void)). And what do the atoms left and right mean? Are they the values for leaf nodes? I would expect a leaf node to look like, tree(X, void, void) where X is the value of the node. You don't have a consistent definition of what a tree structure looks like. Can you sort that out first and explain what a valid tree looks like? Once that's nailed down, it will be easier to create a correct predicate. - lurker
Thanks for your comment. For the first part: ok that makes sense, but how can I then e.g. specify that a node, which is not a leaf, is a subtree of a tree, if that node is in the tree? left and right are supposed to be trees. A tree in prolog has the form (node,left,right), where left and right are tree structures themselves. Now a tree of the form (node,void,void) is a leaf. I did not know that before, I mistakingly assumed that any node in a tree can be specified that way. So I still don't know how to write the subtree predicate so that single nodes in the tree are recognized as subtrees. - eager2learn
Let's get the definition and representation of a tree sorted out before discussing the algorithm of finding subtrees. Your comment says a tree is of the form (node, left, right) where left and right are tree structures. But your problem/question shows atoms left and right which are not trees but atoms. So it's unclear what you're trying to express as a tree structure. For example, what does the clause, subtree(S,tree(X,left,right)) :- subtree(S,left). mean? What does the term tree(X, left, right) mean in your definition of tree versus tree(X, void, void)? Atoms can't have values. - lurker
Perhaps you're getting variables and atoms mixed up? Did you intend left and right to be variables? If so, they need to start with a capital letter. - lurker
Yes that seems to have been the problem. I should have looked more closely before asking here. Thanks for your help, greatly appreciated. - eager2learn

1 Answers

0
votes
all_subtree(leaf(X), leaf(X)).

all_subtree(node(Left,Right),Variable):-
  all_subtree(Left,Variable); all_subtree(Right,Variable);
  Variable = node(Left,Right).

Here's some code that might help. This code outputs ALL subtrees of a given tree (leaf and node code are used).

The base case is that two leafs contain the same value. Recursion happens with a branching factor of 2. At each call, 2 all_subtree function calls are made again, 1 on the left child of the node and 1 on the right child of the node. The "variable" stays the same, and is simply constrained as equaling the node at each iteration.

Some considerations are that this code only works for a binary tree.

Now that you have some useful code for returning all the subtrees of a given tree, you can think about modifying this code to have the behavior you desire. I'm actually not sure what exactly you want your code to do given your question.