序言 - 找到一个二叉树的最大总和子树

-1

让我们说这是树：

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(t(nil,9,nil),12,t(nil,10,nil))

如何，我觉得这在序言？

来源

2016-09-02 TomG

您可以先写一些序言来尝试解决问题。还要定义你如何确定哪个子树是最大的。 –

@ScottHunter我希望我知道如何开始写这个问题的解决方案。正如我写的 - 最大* sum *子树，我怎么能更好地解释它？树的总和大于树中所有其他子树的子树 – TomG

您提到* max子树* 3次，只添加一次* sum *一次。如果你不知道如何写任何序言，你应该从学习语言开始。 –

你可以这样写：

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)).

，当你拨打：

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).

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 ;

其中T是在给定树的最大子树，它具有节点和34（而不是31中你的例子）。

来源

2016-09-02 16:03:27 coder

对不起，但是......最后一个例子中的'max_sub_tree/3'是前面代码中的'sol_tree/3'？ – max66

@ max66，你有绝对的权利，我把最后一分钟的名字改成了更具描述性，并忘记将它更改，我编辑了我的答案，谢谢！ – coder

没有。 :-) – max66

Mmmmhhhh ... 不知道该unserstand你是什么意思与 “最大之树”，但是......希望这有助于

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.

随着

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)

我获得（可变MT ）

t(t(nil,9,nil),12,t(nil,10,nil))

来源

2016-09-02 15:02:57 max66

序言 - 找到一个二叉树的最大总和子树

回答

相关问题