prolog recursively find largest node
-
11-07-2019 - |
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).
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).