Wie kann ich die max Summe Unterbaum eines binären Baum in Prolog findenPrologs - max Summe Teilbaum eines binären Baums zu finden
sagen wir mal so ist der Baum:
t(t(t(nil,-5,nil),4,t(t(nil,15,nil),-20,t(nil,10,nil))),2,t(nil,-8,t(t(nil,9,nil),12,t(nil,10,nil))))
Die maximaler Summe Unterbaum dieses Baumes ist der rechte untere Baum:
t(t(nil,9,nil),12,t(nil,10,nil))
Wie kann ich dies in Prolog finden?
Man könnte schreiben:
max_sub_tree(Tree,T,N):-
sol_tree_noroot(Tree,T1,N1),
sol_tree_withroot(Tree,T2,N2),!,
max_set(T1,N1,T2,N2,T,N).
max_set(T1, N1, T2, N2, T, N) :-
(N1>N2,T=T1,N=N1;
N2>N1,T=T2,N=N2;
N2=:=N1,N=N1,(T=T1;T=T2)).
sol_tree_noroot(nil,nil,0).
sol_tree_noroot(t(L,_,R),T,N):-
max_sub_tree(L,T1,N1),max_sub_tree(R,T2,N2),!,
max_set(T1, N1, T2, N2, T, N).
sol_tree_withroot(nil,nil,0).
sol_tree_withroot(t(L,X,R),t(L1,X,R1),N3):-
sol_tree_withroot(L,T1,N1),sol_tree_withroot(R,T2,N2),
max_set2(T1,N1,T2,N2,L1,R1,N),
N3 is N+X.
max_set2(T1,N1,T2,N2,L,R,N):-
(N1>0,N2>0,N is N1+N2,L=T1,R=T2;
N1>=0,N2<0,N is N1 ,R=nil,L=T1;
N1<0,N2>=0,N is N2 ,L=nil,R=T2;
N1<0,N2<0,N1<N2,N is N2 ,L=nil,R=T2;
N1<0,N2<0,N1>N2,N is N1 ,L=T1,R=nil;
N1>0,N2=0,N is N1,(L=T1,R=nil;L=T1,R=T2);
N1=0,N2>0,N is N2,(R=T2,L=nil;L=T1,R=T2);
N1=0,N2=0,N is N1,(L=T1,R=nil;R=T2,L=T1;L=T1,R=T2)).
, wenn Sie anrufen:
max_sub_tree(t(t(t(nil, -5, nil), 4, t(t(nil, 15, nil), -20, t(nil, 10, nil))), 2, t(nil, -8, t(t(nil, 9, nil),12,t(nil, 10, nil)))),T,N).
es zurück:
T = t(t(nil, 4, t(t(nil, 15, nil), -20, t(nil, 10, nil))), 2, t(nil, -8, t(t(nil, 9, nil), 12, t(nil, 10, nil)))),
N = 34 ;
wobei T der max Unterbaum in Ihrem gegebenen Baum ist, die 34 Summe von Knoten hat (und nicht 31, wie in Ihr Beispiel).
Sorry aber ... 'max_sub_tree/3' im letzten Beispiel ist' sol_tree/3' im vorhergehenden Code? – max66
@ max66, Sie haben absolut Recht, ich änderte den Namen der letzten Minute, um beschreibender zu sein und vergaß, es weiter oben zu ändern, editierte ich meine Antwort, danke !!! – coder
überhaupt nicht. :-) – max66
Mmmmhhhh ... Nicht sicher unserstand, was Sie mit "max Summe subtree" bedeuten, aber ... hoffen, dass diese
maxSubTree(nil, 0, 0, nil).
maxSubTree(t(T1, V0, T2), Sum, Sum, t(T1, V0, T2)) :-
maxSubTree(T1, Sum1, MaxSum1, _),
maxSubTree(T2, Sum2, MaxSum2, _),
Sum is Sum1 + Sum2 + V0,
Sum >= MaxSum1,
Sum >= MaxSum2.
maxSubTree(t(T1, V0, T2), Sum, MaxSum1, MaxTree1) :-
maxSubTree(T1, Sum1, MaxSum1, MaxTree1),
maxSubTree(T2, Sum2, MaxSum2, _),
Sum is Sum1 + Sum2 + V0,
MaxSum1 >= Sum,
MaxSum1 >= MaxSum2.
maxSubTree(t(T1, V0, T2), Sum, MaxSum2, MaxTree2) :-
maxSubTree(T1, Sum1, MaxSum1, _),
maxSubTree(T2, Sum2, MaxSum2, MaxTree2),
Sum is Sum1 + Sum2 + V0,
MaxSum2 >= Sum,
MaxSum2 >= MaxSum1.
Mit
maxSubTree(t(t(t(nil,-5,nil),4,t(t(nil,15,nil),-20,t(nil,10,nil))),2,t(nil,-8,t(t(nil,9,nil),12,t(nil,10,nil)))), _, _, MT)
hilft I erhalten (variable MT
t(t(nil,9,nil),12,t(nil,10,nil))
Sie könnten mit dem Schreiben von Prolog beginnen, um das Problem zu lösen. Außerdem definieren Sie, wie Sie bestimmen, welcher Unterbaum maximal ist. –
@ScottHunter Ich wünschte, ich hätte gewusst, wie man eine Lösung für dieses Problem schreibt. Und wie ich geschrieben habe - der maximale * Summe * Unterbaum, wie kann ich es besser erklären? der Unterbaum, dessen Summe der Knoten größer ist als alle anderen Unterbäume im Baum – TomG
Sie erwähnen * max Unterbaum * 3 mal, nur einmal das Wort * sum * hinzufügen. Und wenn Sie nicht wissen, wie man etwas Prolog schreibt, sollten Sie damit beginnen, etwas über die Sprache zu lernen. –