Question

Just a simple binary tree and i want to find the the largest node.
example tree: t(t(t(nil,1,nil),2,t(nil,3,nil)),4,t(t(t(nil,8,nil),5,nil),6,t(nil,7,nil)))

int L(t,max) {
if(t=null) return max;
if(max<t.root) max = t.root;
LN(t,max);
RN(t,max);
return max;
}
L(tree,tree.root);

I just cant wrap my head around applying it to prolog. Here i display each node. Which i get, but i dont understand how to save the max value and keep it recursively.

tree(nil).
tree(t(L,Root,R)) :- 
    tree(L),
    tree(R), 
    write(Root).

edit: It checks all the leaf nodes, but ignores the t(nil,8,nil)

tree(nil,0).
tree(t(nil,Q,nil),Q) :- !.
tree(t(nil,Q,_),Q).
tree(t(_,Q,nil),Q).
tree(t(L,_,R),Max) :- 
    tree(L, LValue),
    tree(R, RValue), 
    max(LValue,RValue,Max).
Was it helpful?

Solution

Is this another homework assignment?

In any case, I'll try to let you do the thinking since you seem to be learning Prolog. Not to mention the fact that I don't actually have Prolog running on my computer, so I couldn't be sure my suggested solution would actually work.

The fact that the 5 is the only node with only one subnode (i.e. the 8 it's ignoring) should tell you something. All the other nodes are either leaf nodes or have two subnodes.

What exactly is it that you think these two rules do?

tree(t(nil,Q,_),Q).
tree(t(_,Q,nil),Q).
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top