如何在树形图中找到总和？ Java的

Question

import java.util.Scanner; 

public class BinaryTree { 

private int info; 
private BinaryTree left; 
private BinaryTree right; 
private int sum; 

public BinaryTree() 
{ 
    left = null; 
    right = null; 
} 
// This is a second constructor. 
// It can tell the difference by parameter. 
public BinaryTree(int theInfo) 
{ 
    Scanner sc = new Scanner(System.in); 
    int intNum; 
    String s; 

    info = theInfo; 

    System.out.print("Does the node " + info + " have a left child (y or n)? "); 
    s = sc.next(); 
    if (s.equals("y")) 
    { 
     System.out.print ("What value should go in the left child node? "); 
     intNum = sc.nextInt(); 
     left = new BinaryTree(intNum); 
    } 
    System.out.print("Does the node " + info + " have a right child (y or n)? "); 
    s = sc.next(); 
    if (s.equals("y")) 
    { 
     System.out.print ("What value should go in the right child node? "); 
     intNum = sc.nextInt(); 
     right = new BinaryTree(intNum); 
    } 
} 

public void TraverseNLR() 
{ 

    System.out.print(info + " "); 
    if (left != null) 
    { 
     left.TraverseNLR(); 
    } 
    if (right != null) 
    { 
     right.TraverseNLR(); 
    } 
} 

public void TraverseLNR() 
{ 
    if (left != null) 
    { 
     left.TraverseLNR(); 
    } 
    System.out.print(info + " "); 
    if (right != null) 
    { 
     right.TraverseLNR(); 
    } 
} 

public void TraverseLRN() 
{ 

    if (left != null) 
    { 
     left.TraverseLRN(); 
    } 
    if (right != null) 
    { 
     right.TraverseLRN(); 
    } 
    System.out.print(info + " "); 
} 
/* QUESTION FUNCTION HERE */ 
public int sumValues() 
{ 
    System.out.print(info + " "); 
    sum += info; 
    if (left != null) 
    { 
     sum += info; 
     left.TraverseNLR(); 
    } 

    if (right != null) 
    { 
     sum += info; 
     right.TraverseNLR(); 
    } 
    return sum; 
} 
} 

---

import java.util.Scanner; 

public class BinaryTester { 

public static void main(String[] args) 
{ 
    BinaryTree myTree; 
    Scanner sc = new Scanner(System.in); 
    int intNum; 

    System.out.print("What value should go in the root? "); 
    intNum = sc.nextInt(); 
    myTree = new BinaryTree(intNum); 
    //myTree.TraverseNLR(); 
    //System.out.println(); 
    //myTree.TraverseLNR(); 
    //System.out.println(); 
    //myTree.TraverseLRN(); 
    //System.out.println(); 
    System.out.println("Sum is " + myTree.sumValues()); 
    //myTree.sumValues(); 
    } 
} 

我无法找到一个树图的总和。例如，我会输入：

What value should go in the root? 400 
Does the node 400 have a left child (y or n)? y 
What value should go in the left child node? 100 
Does the node 100 have a left child (y or n)? n 
Does the node 100 have a right child (y or n)? y 
What value should go in the right child node? 300 
Does the node 300 have a left child (y or n)? n 
Does the node 300 have a right child (y or n)? n 
Does the node 400 have a right child (y or n)? y 
What value should go in the right child node? 500 
Does the node 500 have a left child (y or n)? n 
Does the node 500 have a right child (y or n)? n 
400 100 300 500 Sum is 1200 

，并得到总和为1200，而不是真正的答案1300一定有什么事情，我不是递归理解。怎么可能从总数中跳过100个？我在全球范围内创建了总和变量，以记住我分配的所有内容。有没有人有任何提示或指向我总结整个Treemap的方向？

Answer 1

我不明白什么TraverseXXX的目的（）函数。你应该能够只是摆脱他们，并重写你的sumValues（）函数使用递归：

public int sumValues() { 
    System.out.println(info + " "); 
    int sum = info; // account for current node 

    if (left != null) 
     sum += left.sumValues(); // add sum of left subtree 

    if (right != null) 
     sum += right.sumValues(); // add sum of right subtree 

    return sum; 
} 

使用此代码为sumValues()我得到了1300的正确的输出：

What value should go in the root? 400 
Does the node 400 have a left child (y or n)? y 
What value should go in the left child node? 100 
Does the node 100 have a left child (y or n)? n 
Does the node 100 have a right child (y or n)? y 
What value should go in the right child node? 300 
Does the node 300 have a left child (y or n)? n 
Does the node 300 have a right child (y or n)? n 
Does the node 400 have a right child (y or n)? y 
What value should go in the right child node? 500 
Does the node 500 have a left child (y or n)? n 
Does the node 500 have a right child (y or n)? n 
400 
100 
300 
500 
Sum is 1300