二叉树的最大宽度

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

二叉树的最大宽度可以定义为二叉树中特定层级上存在的节点数的最大值。要计算二叉树的最大宽度，我们需要遍历树的层级，并找出特定层级上存在的节点数的最大值。

让我们通过一个例子来更好地理解二叉树最大宽度的概念。

在上图中所示的二叉树中，根节点的值为42，它有左子树和右子树。在本例中，让我们计算二叉树每个层级上存在的节点数。上图所示的二叉树的层级从0开始到4（共五层）。

在所示二叉树的第0层只有一个根节点，所以第0层的节点数为1。
在二叉树的第1层，根节点有两个子节点（右子节点和左子节点），值分别为29和89，所以二叉树的第1层有两个节点。
二叉树的第2层有三个节点（左子树根节点的两个子节点和一个右子树根节点的右子节点），所以二叉树的第2层有三个节点。
在二叉树的第3层，我们有两个节点，它们是值为99的子节点。
在最后一层，即二叉树的第4层，有两个节点。

所以，各层级的节点数分别为：

第0层：1个节点

第1层：2个节点

第2层：3个节点

第3层：2个节点

第4层：2个节点。

因此，第2层具有最多的节点数，为3个，分别是值为1、35和99的节点。由于第2层有3个节点，所以上图中所示二叉树的最大宽度为三。

并非所有情况下，最深的层级都应该具有二叉树的最大节点数（3个），并且该处找到二叉树的最大宽度。就像上面所示的二叉树一样，第2层并不是二叉树最深的层级，但它具有最多的节点数（3个节点）。

C++ 代码

让我们编写一段C++代码，以便更好地理解二叉树的最大宽度。

// A queue-based C++ program to create a binary tree and find the maximum width 
// of the created Binary Tree 

// stdc++ header file is included to use object of ostream and istream named cout and cin respectively to display and print data on the console
#include<bits/stdc++.h> 
using namespace std ; 
  
/* A binary tree node has data, a pointer to the left child 
   and a pointer to right child */
struct Node 
{ 

    // a variable named data of integer type is created that will hold the data that is present in that particular node of the complete binary tree
    int data ; 
    
    // two variables named right and left of the node type are created that will be used to hold the addresses of the right child node and the left child node of a parent node present on the complete binary tree
    struct Node * left ; 
    struct Node * right ; 
};//end of the struct Node 
  


// A Function named maxWidth is written to find the maximum width of the binary tree using level order traversal 
// And for the level order traversal of the binary tree, the data structure that is used is a queue

// The maxWidth() Function will traverse through the binary tree in level order and will keep on adding each node of the binary tree that is traversed into an object of the queue data structure
// The process of adding elements in the queue data structure is repeated until the maximum width of the binary tree is found 
// There is one parameter to the maxWidth() function of struct Node type named root that will represent the root node of the binary tree whose maximum width we need to find 
// The return type of the maxWidth() function is of Integer type that will represent the maximum width of the binary tree
int maxWidth(struct Node * root) 
{ 
    // First if root is NULL (that means there are no child nodes of the root node) is checked if true then zero value is returned
    if (root == NULL) 
        return 0; 
  
    // The result variable of the int type is initialised with zero
    int result = 0; 
  
    // The level order traversal of the binary tree begins, and the count of the number of nodes in each level of the tree is kept
    // and in the last, the maximum number of nodes in a particular level will represent the maximum width of the binary tree  
    
    // An object of the queue data structure named q is created to store the nodes of the binary tree
    queue<Node*> q; 
    q.push(root); 
    while (!q.empty()) 
    { 
        // Get the size of queue when the level order 
        // traversal for one level finishes 
        int count = q.size() ; 
  
        // Update the maximum node count value 
        result = max(count, result); 
  
        // Iterate for all the nodes in the queue currently 
        while (count--) 
        { 
            // Dequeue an node from queue 
            Node *temp = q.front(); 
            q.pop(); 
  
            // Enqueue left and right children of 
            // dequeued node 
            if (temp->left != NULL) 
                q.push(temp->left); 
            if (temp->right != NULL) 
                q.push(temp->right); 
        } 
    } 

    // in the end, the result variable is returned as the maximum width of the binary tree  
    return result; 
} 
  
/* A function named newNode that allocates a new node with the given data and NULL left and right pointers. */
// There is one parameter to the newNode function of integer type that will represent the data that a particular node is storing in it
struct Node * newNode(int data) 
{ 
    struct Node * node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return (node); 
} 


//The main function is written to create a binary tree and find the maximum width of the binary tree
int main() 
{

  /* Construct the tree shown below in the comments
               10
             /   \
            /     \
           20       30
          /      /   \
         /      /     \
        40      50       60
              / \
             /   \
            70     80
    */
 

    // An object named root of the struct named Node is created that will act as a root node of the tree having value 10 
    struct Node *root = newNode(10);
    
    // add left and right child nodes to the root node of the tree having values 20 and 30 respectively
    root->left = newNode(20);
    root->right = newNode(30);

    // add left child node to the left node of the root node of the tree having value 40
    root->left->left = newNode(40);
    
    // add left and right child nodes to the right node of the root node of the tree having values 50 and 60 respectively
    root->right->left = newNode(50);
    root->right->right = newNode(60);

    // add left and right child nodes to the left node of the right node of the root node of the tree having values 70 and 80 respectively
    root->right->left->left = newNode(70);
    root->right->left->right = newNode(80);
    


    
    // * Once the tree is created and all the nodes of the tree are assigned their values, the maxWidth function is called to calculate the maximum width of the binary tree
    // * the root of the tree is passed as a parameter to the inorder function
    

    cout << "The Maximum width of the binary tree  is ";
    cout << maxWidth(root);
    cout << endl; 
    return 0; 
} // end of main fucntions

输出：运行上述代码，它会产生以下输出。

The Maximum width of the binary tree is 3.

Java 代码

为了理解二叉树的最大宽度，让我们编写一段Java代码。

// A queue-based Java program to create a binary tree and find the maximum width 
// of the created Binary Tree 

// The LinkedList class is imported from the util package to use the functionalities of the LinkedList data structure
import java.util.LinkedList; 
// The Queue class is imported from the util package to use the functionalities of the Queue data structure
import java.util.Queue; 
  



// A class named BinaryTree is created that has the static class named node that will be used to create a Binary Tree and the max-widththe() function to find the maximum width of the Binary Tree
public class BinaryTree  
{ 
    // A static class named node is created that will act as a single node of the binary tree 
    static class node  
    { 


         // a variable named data of integer type is created that will hold the data that is present in that particular node of the binary tree
        int data; 
        
        // two variables named right and left of the node type are created that will be used to hold the addresses of the right child node and the left child node of a parent node present on the complete binary tree
        node left, right; 
  

        // A constructor of the struct named node is written that will have one parameter of integer type that will set its value to the data variable of the static class
        public node(int data)  
        { 
            this.data = data; 
        } 
    } //end of the static class node
  


  
  // A Function named maxWidth is written to find the maximum width of the binary tree using level order traversal 
    // And for the level order traversal of the binary tree, the data structure that is used is a queue

    // The maxWidth() Function will traverse through the binary tree in level order and will keep on adding each node of the binary tree that is traversed into an object of the queue data structure
    // The process of adding elements in the queue data structure is repeated until the maximum width of the binary tree is found 
    // There is one parameter to the maxWidth() function of struct node type named root that will represent the root node of the binary tree whose maximum width we need to find 
    // The return type of the maxWidth() function is of Integer type that will represent the maximum width of the binary tree
    static int max-width node root)  
    { 
// First if root is NULL (that means there are no child nodes of the root node) is checked if true then zero value is returned
        if (root == null) 
            return 0; 
          
       // The result variable of the int type is initialised with zero
        int result = 0; 
        // The level order traversal of the binary tree begins, and the count of the number of nodes in each level of the tree is kept
        // and in the last, the maximum number of nodes in a particular level will represent the maximum width of the binary tree  
        
        // An object of the queue data structure named q is created to store the nodes of the binary tree
        Queue<node> q = new LinkedList<>(); 
        q.add(root); 
        while (!q.isEmpty())  
        { 
            // Get the size of queue when the level order 
            // traversal for one level finishes 
            int count = q.size(); 
              
            // Update the maximum node count value 
            result = Math.max(result, count); 
              
            // Iterate for all the nodes in  
            // the queue currently 
            while (count-- > 0)  
            { 
                // Dequeue an node from queue 
                node temp = q.remove(); 
              
                // Enqueue left and right children  
                // of dequeued node 
                if (temp.left != null)  
                { 
                    q.add(temp.left); 
                } 
                if (temp.right != null)  
                { 
                    q.add(temp.right); 
                } 
            } 
        } 

        // in the end, the result variable is returned as the maximum width of the binary tree  
        return result; 
    } 
  


    //The main fucntion is written to create a binary tree and find the maximum width of the binary tree
    public static void main(String[] args)  
    { 


          /* Construct the tree shown below in the comments
                   10
                 /   \
                /     \
               20       30
              /      /   \
             /      /     \
            40      50       60
                  / \
                 /   \
                70     80
        */
     

        // // An object named root of the struct named node is created that will act as a the root node of the tree having value 10 
        // node root = new node(1); 
        
        // // add left and right child nodes to the root node of the tree having values 20 and 30 respectively
        // root.left = new node(2); 
        // root.right = new node(3); 
        // root.left.left = new node(4); 
        // root.left.right = new node(5); 
        // root.right.right = new node(8); 
        // root.right.right.left = new node(6); 
        // root.right.right.right = new node(7); 
  
            

        // An object named root of the struct named node is created that will act as a root node of the tree having value 10 
        node root = new node(10);

        // add left and right child nodes to the root node of the tree having values 20 and 30 respectively
        root.left = new node(20);
        root.right = new node(30);

        // add left child node to the left node of the root node of the tree having value 40
        root.left.left = new node(40);

        // add left and right child nodes to the right node of the root node of the tree having values 50 and 60 respectively
        root.right.left = new node(50);
        root.right.right = new node(60);

        // add left and right child nodes to the left node of the right node of the root node of the tree having values 70 and 80 respectively
        root.right.left.left = new node(70);
        root.right.left.right = new node(80);
 


        // * Once the tree is created and all the nodes of the tree are assigned their values, the maxWidth function is called to calculate the maximum width of the binary tree
        // * the root of the tree is passed as a parameter to the inorder function
        
        // A integer variable named width is created that will hold the width of the Binary tree returned by the maxwidth() function.
        int width = maxwidth(root);

        System.out.println("The Maximum width of the binary tree = " + width); 
        System.out.println();
    } 
} // end of the BinaryTree class

输出：上述代码的输出是

The Maximum width of the binary tree = 3.

Python 代码

为了理解二叉树的最大宽度，让我们编写一段Python代码来找出给定二叉树的宽度。

# A queue-based Python program to create a binary tree and find the maximum width 
# of the created Binary Tree 
  
# A  class named node is created that will act as a single node of the binary tree 
class Node: 
      
    #a variable named data of integer type is created that will hold the data that is present in that particular node of the binary tree
 

    #two variables named right and left of the node type are created that will be used to hold the addresses of the right child node and the left child node of a parent node present on the complete binary tree
    #A constructor of the struct named node is written that will have one parameter of integer type that will set its value to the data variable of the static class
    
    def __init__(self, data): 
        self.data = data  
        self.left = None
        self.right = None
  
 
# A Function named getMaxWidth is written to find the maximum width of the binary tree using level order traversal 
# And for the level order traversal of the binary tree, the data structure that is used is the queue
# The getMaxWidth() Function will traverse through the binary tree in level order and will keep on adding each node of the binary tree that is traversed into an object of the queue data structure
# The process of adding elements in the queue data structure is repeated until the maximum width of the binary tree is found 
# There is one parameter to the getMaxWidth() fucntion of struct node type named root that will represent the root node of the binary tree whose maximum width we need to find 
# The return type of the getMaxWidth() fucntion is of Integer type that will represent the maximum width of the binary tree
def getMaxWidth(root): 
    # First, if the root is NULL (that means there are no child nodes of the root node) is checked if true, then zero value is returned 
    if root is None: 
        return 0
    
    # Thse level order traversal of the binary tree begins, and the count of the number of nodes in each level of the tree is kept
    # and in the last, the maximum number of nodes in a particular level will represent the maximum width of the binary tree  
    # An object of the queue data structure named q is created to store the nodes of the binary tree
    q = [] 


    # The maxWidth variable of the int type is initialized with zero
    maxWidth = 0
      
    q.insert(0,root) 
      
    while (q != []): 
        # Get the size of queue when the level order 
        # traversal for one level finishes 
        count = len(q) 
          
        # Update the maximum node count value 
        maxWidth = max(count,maxWidth) 
          
        while count != 0 : 
            count = count-1
            temp = q[-1]   
            q.pop() ; 
            if temp.left is not None: 
                q.insert(0,temp.left) 
   
            if temp.right is not None: 
                q.insert(0,temp.right) 
  
    # in the end, the result variable is returned as the maximum width of the binary tree  
    return maxWidth 
  
# Driver program to test above function 


# The main fucntion is written to create a binary tree and find the maximum width of the binary tree
def main():

    '''Construct the tree shown below in the comments
                   10
                 /   \
                /     \
               20       30
              /      /   \
             /      /     \
            40      50       60
                  / \
                 /   \
                70     80
    
    '''
     
            

    # An object named root is created that will act as the root node of the tree having the value of 10 
    root = Node(10);

    # add left and right child nodes to the root node of the tree having values 20 and 30 respectively
    root.left = Node(20);
    root.right = Node(30);

    # add left child node to the left node of the root node of the tree having the value of 40
    root.left.left = Node(40);

    # add left and right child nodes to the right node of the root node of the tree having values 50 and 60 respectively
    root.right.left = Node(50);
    root.right.right = Node(60);

    # add left and right child nodes to the left node of the right node of the root node of the tree having values 70 and 80 respectively
    root.right.left.left = Node(70);
    root.right.left.right = Node(80);



    # Once the tree is created and all the nodes of the tree are assigned their values, the maxWidth function is called to calculate the maximum width of the binary tree
    # the root of the tree is passed as a parameter to the inorder function
    width = getMaxWidth(root)
    print("The Maximum width of the binary tree is ", width) 


# main function is called
main()

输出：上述代码的输出是

The Maximum width of the binary tree is 3.

下一主题数据结构中的图的类型

二叉树的最大宽度

C++ 代码

Java 代码

Python 代码

联系信息

关注我们

教程

面试题

在线编译器

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

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

二叉树的最大宽度

C++ 代码

Java 代码

Python 代码

相关帖子

B 树性质

SIP 栈

排序算法的应用、优点和缺点

为什么二叉堆比 BST 更适合优先队列

查找范围 L 到 R 中大于 K 的元素数量 (离线查询)

如何在未排序数组中搜索、插入和删除

二叉树的层序遍历

二叉搜索树中的中序前驱和后继

JavaScript 中的冒泡排序

设计一款国际象棋游戏

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器