查找二叉树的所有节点总和的Java程序

1 简介

在此程序中，我们需要计算二叉树中存在的节点总数。首先，我们将遍历左侧子树并计算左侧子树中存在的节点总数。同样，我们计算右子树中存在的节点的总和，并通过添加根的数据来计算总和。

对于给定的树，二叉树的节点总数为1 + 2 + 5 + 8 + 6 + 9 = 31。

2 算法思路

• 定义具有三个属性的Node类，即：左和右数据。在此，左代表节点的左子节点，右代表节点的右子节点。
• 创建节点时，数据将传递到该节点的data属性，并且左右都将设置为null。
• 定义另一个具有属性根的类。
  • 根代表树的根节点，并将其初始化为null。
• 它检查根是否为null，这表示树为空。
• 如果树不为空，请遍历左子树，计算节点的总和并将其存储在sumLeft中。
• 然后，遍历右边的子树，计算节点的总和并将其存储在sumRight中。
• 最后，计算总和= temp.data + sumLeft + sumRight。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class SumOfNodes {  
  
      //Represent the node of binary tree  
        public static class Node{  
        int data;  
        Node left;  
        Node right;  
  
        public Node(int data){  
            //Assign data to the new node, set left and right children to null  
            this.data = data;  
            this.left = null;  
            this.right = null;  
        }  
      }  
  
      //Represent the root of binary tree  
      public Node root;  
  
      public SumOfNodes(){  
        root = null;  
      }  
  
      //calculateSum() will calculate the sum of all the nodes present in the binary tree  
      public int calculateSum(Node temp){  
        int sum, sumLeft, sumRight;  
        sum = sumRight = sumLeft = 0;  
  
        //Check whether tree is empty  
        if(root == null) {  
            System.out.println("Tree is empty");  
            return 0;  
        }  
        else {  
            //Calculate the sum of nodes present in left subtree  
            if(temp.left != null)  
                sumLeft = calculateSum(temp.left);  
  
            //Calculate the sum of nodes present in right subtree  
            if(temp.right != null)  
                sumRight = calculateSum(temp.right);  
  
            //Calculate the sum of all nodes by adding sumLeft, sumRight and root node's data  
            sum = temp.data + sumLeft + sumRight;  
            return sum;  
        }  
      }  
  
      public static void main(String[] args) {  
  
        SumOfNodes bt = new SumOfNodes();  
        //Add nodes to the binary tree  
        bt.root = new Node(5);  
        bt.root.left = new Node(2);  
        bt.root.right = new Node(9);  
        bt.root.left.left = new Node(1);  
        bt.root.right.left = new Node(8);  
        bt.root.right.right = new Node(6);  
  
        //Display the sum of all the nodes in the given binary tree  
        System.out.println("Sum of all nodes of binary tree: " + bt.calculateSum(bt.root));  
      }  
    }  

输出结果为：

um of all nodes of binary tree: 31