求二叉树的宽度

Dear 丶 2022-04-13 14:37 180阅读 0赞

二叉树的宽度是指二叉树各层结点个数的最大值。求二叉树的宽度可以依据与二叉树的层次遍历，我们知道，二叉树的层次遍历借助于deque实现，每次打印当前结点后将其左子树右子树入队，此时队列中既包含当前层的结点，也包含下一层的结点，若我们将当前层的结点全部出队，剩余的就是下一层的结点个数。所以，我们可以使用maxWidth来表示最大宽度，若下一层的结点个数大于maxWidth，则更新maxWidth，最终队列为空，得到的maxWidth即为二叉树的宽度。

以下是C++实现的源代码：

//求二叉树的宽度  
int WidthOfBiTree(BiTree root)  
\{  
if(root == NULL)  
return 0;

int maxWidth = 0;
    deque<BiTree> d;
    d.push_back(root);
    
    while(true)
    {
        int len = d.size();
        if(len == 0)
            break;
        while(len > 0)
        {
            BiTree temp = d.front();
            d.pop_front();
            len--;
            if(temp->Lchild)
                d.push_back(temp->Lchild);
            if(temp->Rchild)
                d.push_back(temp->Rchild);
        }
        maxWidth = maxWidth > d.size() ? maxWidth : d.size();
    
    }
    return maxWidth;

## \} ##

作者：ColiYin  
来源：CSDN  
原文：[https://blog.csdn.net/sinat\_20177327/article/details/78289905][https_blog.csdn.net_sinat_20177327_article_details_78289905]  
版权声明：本文为博主原创文章，转载请附上博文链接！

/\* 二叉树的宽度 在上一层遍历完成后，下一层的所有节点已经放到队列中，此时队列中的元素个数就是下一层的宽度\*/  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**/  
int WidthOfBinaryTree(BinaryTreeNodepNode)\{  
if (pNode == NULL)  
\{  
return 0;  
\}  
std::deque<BinaryTreeNode*> dequeTreeNode;//双端队列  
int maxWidth = 1;//最大的宽度,用于当只有一个节点时候返回1  
dequeTreeNode.push\_back(pNode);//头结点入队  
while (true)  
\{

int length = dequeTreeNode.size();//当前层节点的个数
    	if (length == 0)//当前层没有节点，跳出循环
    	{
    		break;
    	}
    	while (length > 0)//如果当前层还有节点
    	{
    		BinaryTreeNode* pTemp = dequeTreeNode.front();
    		dequeTreeNode.pop_front();//出队
    		length--;//长度减一
    		if (pTemp->m_pLeft)
    		{
    			dequeTreeNode.push_back(pTemp->m_pLeft);//下一层节点入队
    		}
    		if (pTemp->m_pRight)
    		{
    			dequeTreeNode.push_back(pTemp->m_pRight);//下一层节点入队
    		}
    	}
    	maxWidth = maxWidth > dequeTreeNode.size() ? maxWidth : dequeTreeNode.size();//得到最大宽度
    }
    return maxWidth;

[https_blog.csdn.net_sinat_20177327_article_details_78289905]: https://blog.csdn.net/sinat_20177327/article/details/78289905