Java查找二叉树的最大宽度
在此程序中，我们需要找出二进制树的最大宽度。二叉树的宽度是任何级别中存在的节点数。因此，具有最大节点数的级别将是二叉树的最大宽度。要解决此问题，请逐级遍历树并计算每个级别中的节点。
在给定的二进制树中，
级别1有一个节点，因此maxWidth =1。
级别2有两个节点，因此maxWidth = 2为(2> 1)。
级别3有四个节点，因此maxWidth = 4为(4> 2)。 br>级别4有一个节点，因此maxWidth = 4为(1 <4)。
因此，上述二叉树的最大宽度为4，用白色椭圆表示。
算法
定义Node类，它具有三个属性，即: 左和右数据。在这里，左代表节点的左子节点，右代表节点的右子节点。
创建节点后，数据将传递到该节点的data属性，并且左右都将设置为null。
定义另一个具有属性根的类。 Root表示树的根节点，并将其初始化为null。
a.findMaximumWidth()将找出给定二叉树的最大宽度:
变量maxWidth将存储任何级别中存在的最大节点数。
该队列用于逐级遍历二叉树。
它检查根是否为空，这意味着树为空。
如果不是，则将根节点添加到队列中。变量nodesInLevel跟踪每个级别中的节点数。
如果nodesInLevel> 0，请从队列的最前面删除该节点，并将其左右子节点添加到队列中。对于第一次迭代，将删除节点1并将其子节点2和3添加到队列中。在第二次迭代中，将删除节点2，将其子节点4和5添加到队列中，依此类推。
MaxWidth将存储max(maxWidth，nodesInLevel)。因此，在任何给定的时间点，它将代表最大的节点数。
这将一直持续到遍历树的所有级别为止。
程序:
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree {
//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 BinaryTree(){
root = null;
}
//findMaximumWidth() will find out the maximum width of the given binary tree
public int findMaximumWidth() {
int maxWidth = 0;
//Variable nodesInLevel keep tracks of number of nodes in each level
int nodesInLevel = 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, then width will be 0
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);
while(queue.size() != 0) {
//Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
nodesInLevel = queue.size();
//maxWidth will hold maximum width.
//if nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel
maxWidth = Math.max(maxWidth, nodesInLevel);
//if variable nodesInLevel contains more than one node
//then, for each node, well add left and right child of the node to the queue
while(nodesInLevel > 0) {
Node current = queue.remove();
if(current.left != null)
queue.add(current.left);
if(current.right != null)
queue.add(current.right);
nodesInLevel--;
}
}
}
return maxWidth;
}
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
//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.left.right = new Node(5);
bt.root.right.left = new Node(6);
bt.root.right.right = new Node(7);
bt.root.left.left.left = new Node(8);
//Display the maximum width of given tree
System.out.println("Maximum width of the binary tree: " + bt.findMaximumWidth());
}
}
输出:
Maximum width of the binary tree: 4
