二叉树的广度优先搜索

问题描述

给定一棵二叉树，要求计算其最大宽度。
二叉树中某一层的宽度定义为该层中最右侧节点与最左侧节点之间所包含的节点数量（若中间存在空节点，也需计入总数）。

分析

设计一个函数，输入一个已初始化的二叉树，输出其最大宽度。
如何确定该二叉树的最大宽度？一种可行的思路是逐层遍历所有节点，并统计每层节点的数量。然而，由于题目要求即使某些节点不存在也需视作存在，这可能需要对原始二叉树结构进行调整，操作上较为复杂。
为简化处理过程，可以为每个节点赋予特定的数值。依据完全二叉树的特性，根节点编号设为1，其左子节点编号为2，右子节点编号为3，依此类推。
对于任意一个节点（编号为k），其左子节点的编号可表示为2k，而右子节点的编号则为2k+1。
最大宽度等于该层最右侧节点编号减去最左侧节点编号后加1的结果。

引入双端队列这一数据结构以辅助实现。
将原二叉树视为满二叉树处理，并将缺失的节点也纳入考虑范围。每个实际存在的二叉树结点被赋予其在遍历过程中所对应的顺序编号。根结点首先被访问，随后依次访问其左、右子结点。
若某一结点的序号为