问题描述1完全二叉树是每一层（除最后一层）全部填满（即节点数达到maximum)，并且所有的节点都尽可能的集中在左边。例如：图1中的4棵二叉树都是完全二叉树。数据结构CBTInserter的实现方式有3种：CBTInserter->insert(val)向树中插入一个新节点，节点类型为TreeNode，值为val。保持树处于完全二叉树的状态，并返回插入的新节点的父节点的值；CBTInserter.get_root()将返回树的头节点。图1说明：将节点7加入(a)中的完全二叉树得到(b)；将节点8加入(b)中的完全二叉树得到(c)；将节点9添加到(c)get(d)中的完全二叉树中。什么是完全二叉树？看完题目，写代码前需要明白什么是完全二叉树？完全二叉树是从满二叉树派生出来的。若二叉树的深度为h，除第h层外，每层（1~h-1）的节点数达到最大数（即1~h-1层为满二叉树），并且第h层的所有节点都连续集中在最左边，就是完全二叉树2.总结：对于深度为h的二叉树，必须满足以下条件才能成为完全二叉树：1~h-1层是满二叉树（国内满二叉树3）。h层的所有节点都连续集中在最左边。文字描述有点抽象，看几个例子就知道了。图2中的（1）（2）（3）都是完全二叉树，而（4）（5）（6）则不是完全二叉树。(1)(2)(3)是完全二叉树，必须满足完全二叉树的定义。那么为什么不是(4)(5)(6)呢？我们一一分析：(4)是一棵深度为4的二叉树，第1~2层是满二叉树，但第三层不是。不满足1~4-1层是满二叉树的条件。(5)和(6)都是深度为3的二叉树。第1~2层是满二叉树，但第3层的所有节点并不连续集中在最左边。(5)第三层最左边没有节点，(6)的第三层所有节点都是不连续的。问题分析解决这个问题的关键是理解完全二叉树的特点和节点加入二叉树的顺序。完全二叉树的特点：1~h-1层是完全二叉树，h层最多有2h-1个节点。h层的所有节点都连续集中在最左边。添加顺序：如果最底层的节点数小于2h-1，则从左到右找到该层第一个空出的位置，添加一个新节点。例如在图（1）中的（c）中增加一个节点：图3如果底部节点的个数为2h-1，则向二叉树中增加一个新节点，就会为二叉树增加一个新的层，而新的该节点为新层的最左节点，即新节点的父节点为原底层的最左节点。例如在图(1)中的(b)中添加节点：图4完整二叉树中新节点添加的顺序表现为从上到下，从左到右逐层，这是典型的二叉树广度优先搜索的顺序。解题思路是在完全二叉树中按照广度优先搜索的顺序找出第一个还有空位的左子节点或右子节点。如果节点没有左孩子，则新节点将是该节点的左孩子；如果节点没有右孩子，则新节点将是该节点的右孩子。完整代码：root=$root;array_push($this->queue,$root);while($this->queuePeek($this->queue)->left!=null&&$this->queuePeek($this->queue)->right!=null){$node=array_shift($this->队列）;array_push($this->queue,$node->left);array_push($this->queue,$node->right);}}publicfunctionqueuePeek($queue){//帮助函数返回队列中的第一个元素。返回$队列[0]；}publicfunctioninsert($val){//添加子节点的发送$parent=$this->queuePeek($this->queue);$node=新节点($val);if($parent->left==null){$parent->left=$node;}else{$parent->right=$node;array_shift($this->队列);array_push($this->queue,$parent->left);array_push($this->queue,$parent->right);}返回$parent->data;}publicfunctiongetRoot(){return$this->root;}}//创建二叉树的类Node{public$left=NULL;公共$right=NULL;公共$数据=''；公共函数__construct($data){$this->data=$data;}publicfunctionbuildTree(Node$lchild=NULL,Node$rchild=NULL){if(!is_null($lchild)){$this->left=$lchild;}if(!is_null($rchild)){$this->right=$rchild;}}}//创建完全二叉树$a=newNode(1);$b=新节点（2）；$c=新节点（3）；$d=新节点（4）；$e=新节点（5）；$f=新节点(6);$a->buildTree($b,$c);$b->buildTree($d,$e);$c->buildTree($f);$GBTInserter=newGBTInserter($a);//添加节点$GBTInserter->insert(7);$GBTInserter->insert(8);$GBTInserter->insert(9);$re=$GBTInserter->insert(10);仿真过程以在图1(b)中添加一个节点为例。GBTInserter类的构造方法中的广度优先搜索算法是如何找到第一个缺少子节点的节点的？图5①。图5中的步骤(0)，将完全二叉树的根节点加入到队列中。②.根节点$a的左右子节点均为空，故$a出队，$a的左右子节点依次入队，如图5中步骤(1)所示.相关代码如下：publicfunction__construct($root){//将完全二叉树的根节点加入队列array_push($this->queue,$root);//队头节点的左右子节点都为空，继续执行。while($this->queuePeek($this->queue)->left!=null&&$this->queuePeek($this->queue)->right!=null){$node=array_shift($this->队列）;array_push($this->queue,$node->left);array_push($this->queue,$node->right);}}③。下一步是遍历节点$b和$c。由于$b和$c节点的左右子节点都不为空，其过程与处理$a节点类似，如图5中的步骤（2）和（3）所示。④．在步骤（3）之后，队列中的所有节点都是第3层节点。并且头节点$d没有子节点，循环终止。也就是说，第一个没有子节点的节点存储在队列的头部。GBTInserter类的insert()方法是如何添加子节点的：实例化GBTInserter类后，所有缺少子节点的节点都存入队列：$queue=[$d,$e,$f,$g]and队列头部的节点是第一个缺少子节点的节点。我们将向该节点添加子节点。①.使用queuePeek方法获取队列的头节点。②.实例化需要添加的节点。publicfunctioninsert($val){...$parent=$this->queuePeek($this->queue);$node=新节点($val);...}③。左子节点？如果不是，则加入左子节点，否则加入右子节点，一分为二出队。outone是指出队在队头的节点。添加右子节点后，该节点不再缺少子节点，队列记录缺少子节点的节点，自然要出队。入二是指将团队的头节点的左右子节点都加入到团队中。④.返回头节点的值。publicfunctioninsert($val){...if($parent->left==null){$parent->left=$node;}else{$parent->right=$node;array_shift($this->队列);array_push($this->queue,$parent->left);array_push($this->queue,$parent->right);}return$parent->data;}复杂度分析时间复杂度：GBTInserter的构造函数本质上是按照广度优先搜索的顺序找到二叉树中所有既有左子节点又有子节点的节点，所以时间复杂度是O(n)。在一棵完全二叉树中调用函数insert添加一个节点最多需要在队列中移除一个节点并添加两个节点。通常，队列中插入和删除的时间复杂度为O(1)。GBTInserter类需要一个队列来实现广度优先搜索算法来保存缺少左子节点或右子节点的节点，空间复杂度为O(n)。《剑指offer》?常用数据结构-完全二叉树（定义、特点、节点个数的判断及C++简单实现）?完全二叉树?
