查找二叉树最大宽度的 Java 程序

2025年3月17日 | 阅读 3 分钟

在此程序中，我们需要找出二叉树的最大宽度。二叉树的宽度是指任何层级存在的节点数。因此，节点数最多的层级将是二叉树的最大宽度。为了解决这个问题，我们按层级遍历树并计算每个层级的节点数。

Java program to find maximum width of a binary tree

在给定的二叉树中，

第 1 层有 1 个节点，所以 maxWidth = 1。
第 2 层有 2 个节点，所以 maxWidth = 2（因为 2 > 1）。
第 3 层有 4 个节点，所以 maxWidth = 4（因为 4 > 2）。
第 4 层有 1 个节点，所以 maxWidth = 4（因为 1 < 4）。

因此，上面二叉树的最大宽度为 4，用白色椭圆表示。

算法

定义 Node 类，该类包含三个属性：data、left 和 right。这里，left 表示节点的左子节点，right 表示节点的右子节点。
创建节点时，数据将传递到节点的 data 属性，left 和 right 都将设置为 null。
定义另一个类，该类有一个 root 属性。
- Root 表示树的根节点，并将其初始化为 null。

a. findMaximumWidth() 将找出给定二叉树的最大宽度

变量 maxWidth 将存储任何层上存在的最大节点数。
队列用于逐层遍历二叉树。
它检查 root 是否为 null，这意味着树是空的。
如果不是，则将根节点添加到队列。变量 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, we'll 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

下一个主题Java 程序

查找二叉树最大宽度的 Java 程序

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

查找二叉树最大宽度的 Java 程序

算法

程序

相关帖子

Java 从双向链表中删除重复元素的程序

Java 矩阵减法程序

How to Generate Random Number in Java

Java 中的糖果分配问题

Tech Number in Java

Java 中检查 n 及其两倍是否存在

打印数组中重复元素的 Java 程序

Java 在循环链表中插入新节点到中间的程序

Java 中的最小激活灯泡问题

Java Program to Find GCD of Two Numbers

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器