Java计算二叉树的奇数级和偶数级节点之和
在此程序中，我们需要计算总和之间的差在奇数级存在的节点总数和在偶数级存在的节点总数之和。假设，如果一棵树包含5个级别，那么
Difference = (L1 + L 3 + L5) - (L2 + L4)
在上图中，奇数级用蓝色虚线表示，偶数用绿色表示。
OddLevelSum = 1 + 4 + 5 + 6 = 16
EvenLevelSum = 2 + 3 = 5
Difference = |16 - 5| = 11
算法
定义Node类，它具有三个属性，即: data，left和right。在这里，左代表节点的左子节点，右代表节点的右子节点。
创建节点后，为节点的数据部分分配一个适当的值，其左，右子级为NULL。
定义另一个具有属性根的类。 Root代表树的根节点最初具有空值。
a.Difference()将计算奇数级和偶数级的节点总数之差:
使用"队列"遍历二叉树级别。
使用变量currentLevel跟踪当前水平。
如果currentLevel被2整除，则将currentLevel中存在的节点的所有值添加到变量evenLevel。否则，将节点的所有值添加到变量oddLevel。
通过从oddLevel中减去evenLevel中存在的值来计算差异。
程序:
import java.util.LinkedList;
import java.util.Queue;
public class DiffOddEven {
//Represent a 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 DiffOddEven(){
root = null;
}
//difference() will calculate the difference between sum of odd and even levels of binary tree
public int difference() {
int oddLevel = 0, evenLevel = 0, diffOddEven = 0;
//Variable nodesInLevel keep tracks of number of nodes in each level
int nodesInLevel = 0;
//Variable currentLevel keep track of level in binary tree
int currentLevel = 0;
//Queue will be used to keep track of nodes of tree level-wise
Queue<
Node>
queue = new LinkedList<
Node>
();
//Check if root is null
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else {
//Add root node to queue as it represents the first level
queue.add(root);
currentLevel++;
while(queue.size() != 0) {
//Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
nodesInLevel = queue.size();
while(nodesInLevel > 0) {
Node current = queue.remove();
//Checks if currentLevel is even or not.
if(currentLevel % 2 == 0)
//if level is even, add nodes's to variable evenLevel
evenLevel += current.data;
else
//if level is odd, add nodes's to variable oddLevel
oddLevel += current.data;
//Adds left child to queue
if(current.left != null)
queue.add(current.left);
//Adds right child to queue
if(current.right != null)
queue.add(current.right);
nodesInLevel--;
}
currentLevel++;
}
//Calculates difference between oddLevel and evenLevel
diffOddEven = Math.abs(oddLevel - evenLevel);
}
return diffOddEven;
}
public static void main (String[] args) {
DiffOddEven bt = new DiffOddEven();
//Add nodes to the binary tree
bt.root = new Node(1);
bt.root.left = new Node(2);
bt.root.right = new Node(3);
bt.root.left.left = new Node(4);
bt.root.right.left = new Node(5);
bt.root.right.right = new Node(6);
//Display the difference between sum of odd level and even level nodes
System.out.println("Difference between sum of odd level and even level nodes: " + bt.difference());
}
}
输出:
Difference between sum of odd level and even level nodes: 11
