Prolog finds the largest node recursively
Simple binary tree and I want to find 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 (zero, 7, zero)))
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 tilt my head around applying it to the prologues. Here I am showing each node. Which I get, but I don't understand how to store the maximum value and store it recursively.
tree(nil).
tree(t(L,Root,R)) :-
tree(L),
tree(R),
write(Root).
edit: checks all leaf nodes but ignores 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).
source to share
Is this another homework assignment ?
Anyway, I'll try to give you an idea, since you seem to be learning Prolog. Not to mention, I don't actually have Prolog on my computer, so I couldn't be sure that my proposed solution would actually work.
The fact that 5 is the only node with only one subnode (i.e. 8 ignoring) should tell you something. All other nodes are either leaf nodes or have two subnodes.
What exactly do you think of these two rules?
tree(t(nil,Q,_),Q).
tree(t(_,Q,nil),Q).
source to share