Java - 如何計算和比較二叉樹

Question

一些作業問題： 我需要檢查二叉樹是否遵循此規則：每個節點有 有數字，我需要檢查這個數字是否大於或等於全部它下面的節點。

如果所有樹都遵循該規則，該方法應該返回true。 我寫了這個代碼：

public static boolean isSigma(Node n) 
{ 
    if (n == null) 
     return true; 
    if (n.getLeftSon() == null && n.getRightSon() == null) 
     return true; 
    else return n.getNumber() >= sumCalc(n) && isSigma(n.getLeftSon()) && isSigma(n.getRightSon()); 
} 

private static int sumCalc(Node n) // return the sum of specific Node plus other Node/s that are under it 
{ 
    if (n==null) 
     return 0; 
    else return n.getNumber() + sumCalc(n.getLeftSon()) + sumCalc(n.getRightSon()); 
} 

左樹將返回false，右邊的樹將返回true。

但由於某些原因代碼無法正常工作。 我檢查了幾棵樹，它給我總是假的。 順便說一句，我必須在遞歸方法中編寫它，並且不允許更改公共方法簽名。

Answer 1

難道不是更好嗎？ :)

private static int sumCalc(Node n) { 
    if (n == null) 
     return 0; 
    return n.getNumber() + sumCalc(n.getLeftSon()) + sumCalc(n.getRightSon()); 
} 

現在，你只需要使用它像sumCalc(rootNode);

您應該修改遞歸的想法。

...編輯

退房這一行：

return n.getNumber() >= sumCalc(n) && isSigma(n.getLeftSon()) && isSigma(n.getRightSon()); 

記住sumCalc（n）的統計，包括該從n個節點樹的所有值。你真正想要檢查的不是n.getNumber() >= sumCalc(n)，而是n.getNumber() >= sumCalc(n) - n.getNumber()，它等於n.getNumber() <<1>= sumCalc(n)。

Answer 2

問題是由一個子句中isSigma（）的其他情況下產生：

[A] n.getNumber() >= sumCalc(n) 

sumCalc（）的定義添加節點的權重/ n值及其所有的孩子和他們的孩子等。幹運行代碼。 sumCalc（n）將返回子節點的n.getNumber（）+ sumCalc（）。所以聲明[A]永遠是錯誤的。 （除非你是在處理負值）

修改方法sumCalc（）如下：

private static int sumCalc(Node n) 
    // return the sum of specific Node plus other Node/s that are under it 
    { 
    if (n==null) 
     return 0; 
    else 
     int childSum = n.getLeftSon().getNumber() + n.getRightSon().getNumber(); 
     return (childSum + sumCalc(n.getLeftSon()) + sumCalc(n.getRightSon())); 
    } 

Answer 3

改寫的問題：
如果節點的數目N大於或等於 isSigma(Node n)應返回true所有子女及其子女的總和也是西格瑪。

如果這是你要找的東西，這裏是您的解決方案：

public static boolean isSigma(Node n) 
{ 
    if (n == null) { 
     return true; 
    } else if (n.getLeftSon() == null && n.getRightSon() == null) { 
     return true; 
    } else if (n.getLeftSon() != null || n.getRightSon() != null) { 
     boolean leftIsSigma = isSigma(n.getLeftSon()); 
     boolean rightIsSigma = isSigma(n.getRightSon()); 
     int sumOfChildren = sumCalc(n.getLeftSon()) + sumCalc(n.getRightSon()); 

     return ((n.getNumber() >= sumOfChildren) && leftIsSigma && rightIsSigma); 
    } 
} 

private static int sumCalc(Node n) { 
    if (n == null) 
     return 0; 
    return n.getNumber() + sumCalc(n.getLeftSon()) + sumCalc(n.getRightSon()); 
}