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

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

说明

在此程序中，我们需要找出二叉树的最大宽度。二叉树的宽度是任何层上存在的节点数。因此，节点数最多的那层就是二叉树的最大宽度。要解决此问题，请逐层遍历树并计算每层的节点数。

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 属性。
1. Root 表示树的根节点，并将其初始化为 null。
findMaximumWidth() 将找出给定二叉树的最大宽度
1. 变量 maxWidth 将存储任何层上存在的最大节点数。
2. 队列用于逐层遍历二叉树。
3. 它检查根是否为空，这意味着树是空的。
4. 如果不是，则将根节点添加到队列。变量 nodesInLevel 用于跟踪每个层上的节点数。
5. 如果 nodesInLevel > 0，则从队列的前面移除节点，并将其左子节点和右子节点添加到队列中。在第一次迭代中，将移除节点 1，并将其子节点 2 和 3 添加到队列中。在第二次迭代中，将移除节点 2，其子节点 4 和 5 将添加到队列中，依此类推。
6. MaxWidth 将存储 max(maxWidth, nodesInLevel)。因此，在任何给定时间点，它将表示最大节点数。
7. 这将一直持续到遍历完树的所有层。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class BinaryTree:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
    
    #findMaximumWidth() will find out the maximum width of the given binary tree
    def findMaximumWidth(self):
        maxWidth = 0;
        #Variable nodesInLevel keep tracks of number of nodes in each level
        nodesInLevel = 0;
        #queue will be used to keep track of nodes of tree level-wise
        queue = [];
        
        #Check if root is null, then width will be 0
        if(self.root == None):
            print("Tree is empty");
            return 0;
        else:
            #Add root node to queue as it represents the first level
            queue.append(self.root);
            
            while(len(queue) != 0):
                
                #Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
                nodesInLevel = len(queue);
                #maxWidth will hold maximum width. 
                #If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel
                maxWidth = 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):
                    current = queue.pop(0);
                    if(current.left != None):
                        queue.append(current.left);
                    if(current.right != None):
                        queue.append(current.right);
                    nodesInLevel = nodesInLevel - 1;
        return maxWidth;
 
bt = BinaryTree();
#Add nodes to the binary tree
bt.root = Node(1);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(4);
bt.root.left.right = Node(5);
bt.root.right.left = Node(6);
bt.root.right.right = Node(7);
bt.root.left.left.left = Node(8);
 
#Display the maximum width of given tree
print("Maximum width of the binary tree: " + str(bt.findMaximumWidth()));

输出

Maximum width of the binary tree: 4

C

#include <stdio.h>
#include <stdlib.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root = NULL;
 
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//queue will be used to keep track of nodes of tree level-wise
struct node* queue[100];
int rear = 0,front = -1, size = 0;
 
//Adds new node to the queue
void enqueue(struct node* temp)
{
    queue[rear++]=temp;
    size++;
}
//Deletes a node from the queue
struct node* dequeue()
{
    size--;
    return queue[++front];
}
 
//findMaximumWidth() will find out the maximum width of the given binary tree
int findMaximumWidth() {
    int maxWidth = 0;
    
    //Variable nodesInLevel keep tracks of number of nodes in each level
    int nodesInLevel = 0;
    
    //Check if root is null, then width will be 0
    if(root == NULL) {
        printf("Tree is empty\n");
        return 0;
    }
    else {
        //Add root node to queue as it represents the first level
        enqueue(root);
        
        while(size != 0) {
            //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
            nodesInLevel = size;
            
            //maxWidth will hold maximum width. 
            //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel
            maxWidth = (maxWidth < nodesInLevel) ? nodesInLevel : maxWidth;
 
            //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) {
                    
                struct node *current = dequeue();
                if(current->left != NULL){
                    enqueue(current->left);    
                }
                
                if(current->right != NULL) {
                    enqueue(current->right);    
                }
                nodesInLevel--;
            }
        }
    return maxWidth;
    }
}
 
int main()
{
    //Add nodes to the binary tree
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    root->left->left->left = createNode(8);
    
    //Display the maximum width of the given tree
    printf("Maximum width of the binary tree: %d", findMaximumWidth());
    return 0;
}

输出

Maximum width of the binary tree: 4

JAVA

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

C#

using System;
using System.Collections.Generic;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class BinaryTree<T> where T : IComparable<T>{
            //Represent the root of binary tree
            public Node<T> root;
 
            public static Boolean flag = false;
 
            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<T>> queue = new Queue<Node<T>>();
            
            //Check if root is null, then width will be 0
            if(root == null) {
              Console.WriteLine("Tree is empty");
              return 0;
            }
            else {
              //Add root node to queue as it represents the first level
              queue.Enqueue(root);
              
              while(queue.Count != 0) {
                  
                  //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
                  nodesInLevel = queue.Count;
                  //maxWidth will hold maximum width. 
                  //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel
                  maxWidth = (maxWidth < nodesInLevel) ? nodesInLevel : maxWidth;
                  
                  //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<T> current = queue.Dequeue();
                     if(current.left != null) 
                         queue.Enqueue(current.left);
                     if(current.right != null) 
                         queue.Enqueue(current.right);
                     nodesInLevel = nodesInLevel - 1;
                  }
              }
            }
            return maxWidth;
      }
        }
        
        public static void Main()
        {
            BinaryTree<int> bt = new BinaryTree<int>();
            //Add nodes to the binary tree
              bt.root = new Node<int>(1);
              bt.root.left = new Node<int>(2);
              bt.root.right = new Node<int>(3);
              bt.root.left.left = new Node<int>(4);
              bt.root.left.right = new Node<int>(5);
              bt.root.right.left = new Node<int>(6);
              bt.root.right.right = new Node<int>(7);
              bt.root.left.left.left = new Node<int>(8);
          
              //Display the maximum width of given tree
              Console.WriteLine("Maximum width of the binary tree: " + bt.findMaximumWidth());                
        }    
    }
}

输出

Maximum width of the binary tree: 4

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinaryTree{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //findMaximumWidth() will find out the maximum width of the given binary tree
    function findMaximumWidth() {
      $maxWidth = 0;
      
      //Variable $nodesInLevel keep tracks of number of nodes in each level
      $nodesInLevel = 0;
      //$queue will be used to keep track of nodes of tree level-wise
      $queue = array();
      
      //Check if root is null, then width will be 0
      if($this->root == null) {
          print "Tree is empty <br>";
          return 0;
      }
      else {
          //Add root node to $queue as it represents the first level
          array_push($queue,$this->root);
          
          while(sizeof($queue) != 0) {
              
              //Variable $nodesInLevel will hold the size of queue i.e. number of elements in queue
              $nodesInLevel = sizeof($queue);
              //$maxWidth will hold maximum width. 
              //If $nodesInLevel is greater than $maxWidth then, $maxWidth will hold the value of $nodesInLevel
              $maxWidth = 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) {
                 $current = array_shift($queue);
                 if($current->left != NULL) 
                     array_push($queue, $current->left);
                 if($current->right != NULL) 
                     array_push($queue,$current->right);
                 $nodesInLevel--;
              }
          }
      }
      return $maxWidth;
    }
}
$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
print "Maximum width of the binary tree: " . $bt->findMaximumWidth();
?>
</body>
</html>

输出

Maximum width of the binary tree: 4

下一个主题程序列表

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

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

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

程序

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

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

右旋数组元素的程序

将英寸转换为毫米的程序

根据给定坐标查找三角形类型的程序

打印字母图案 11 的程序

查找给定矩阵的转置的程序

打印给定数字的组合 (nCr) 的程序

确定单向链表是否为回文串的程序

确定给定矩阵是否为稀疏矩阵的程序

查找半圆面积和周长的程序

在单链表中搜索元素的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器