软考完全二叉树：先看缺位在哪里，再算父子结点编号-知英教育

软考数据结构复习中，“层数差不多”“左右看着均匀”都不足以判断一棵树是否完全。完全二叉树最后一层靠左，说的是结点占据的位置，而不是图形画在纸张左边。可以先结合知英教育的软考学习与方向指南梳理基础，再用位置和编号核对自己的判断。

先约定：根算第一层，左孩子和右孩子有区别

下文只讨论非空二叉树，把根记为第一层。每个结点最多有两个孩子，左、右位置不能随意互换。完全二叉树的要求有两部分：最后一层以前的层全部填满；最后一层从最左位置开始连续放置结点，后面的空位只能集中在右侧。

因此，不要求每棵完全二叉树的最后一层都填满。若最后一层没有空位，当然也满足条件；如果有空位，则要检查前面是否已经出现空缺，却又在它右边放了结点。

设根在位置1，第二层是位置2、3，第三层是4、5、6、7，第四层放8、9、10，后面的11至15空着。前三层都满，第四层三个结点连续占据最左侧位置，这棵树符合完全二叉树的定义。

这里列出的数字是按完整层位置安排的编号：每一层从左向右，而且不挪动孩子原有的左右位置。为了读图方便，写出潜在空位并不代表那些位置真的有结点。

并不是。对上述10结点树，位置5的结点有左孩子10，却没有右孩子11。由于最后一层到10为止连续占位，缺掉的都是右侧位置，因此仍符合条件。

反过来，如果一个结点只有右孩子而没有左孩子，就会先空出左侧位置，再在它右边出现结点，不符合完全二叉树的要求。同样，有了一个只含左孩子的结点，也不能据此判整棵树完全，还要继续检查其他位置。

采用根为1的编号时，位置i的左孩子在2i，右孩子在2i+1；除根以外，位置i的父结点在⌊i/2⌋，即除以2后向下取整。对具有n个结点的完全二叉树，若孩子位置超过n，表示该孩子不存在。

在n=10的例子里，位置5的左孩子是10，存在；右孩子是11，超过10，不存在。位置6的两个孩子位置为12和13，都超过10，所以它没有孩子。位置10的父结点为⌊10/2⌋=5，回到位置5。

若资料采用0起始数组下标，根的位置与父子公式都会改变。不要把0起始公式与1起始编号混在同一道计算里。先写清根从哪里开始编号，再代入公式，比记住一组数字更可靠。

仍看第四层。若位置8存在、9为空、10又存在，左侧空位右边仍有结点，就不满足完全二叉树最后一层靠左的要求。即使总结点数不多，树也可能显得很整齐，仍不能忽略这个缺位。

尤其要注意：对任意一棵稀疏二叉树，只把现有结点按层次访问顺序重新写成1、2、3……，这些标签当然可以连续，但这不能证明树完全。判断所需的是保留左右孩子关系的层位置，不能先删掉空位，再把右边结点整体向左挪。

在知英教育整理树结构问题时，可以先把每层的空位也画出来，再标记第一次出现空位之后是否还有结点。这样更容易区分“访问顺序连续”与“位置占用连续”。

不同教材对full、perfect等英文名称的使用存在差异。NIST词典把full binary tree定义为每个结点有0个或2个孩子，把perfect binary tree定义为所有叶子同深、内部结点均有两个孩子，同时提示其他作者可能采用不同名称。

因此，复习时应先看指定资料给出的定义，不凭一个“满”字替换整套条件。本文判断完全二叉树，只使用“此前各层填满、最后一层连续靠左”的标准，不讨论堆序大小，也不把完全与左右子树高度相近混为一谈。

理解完全二叉树最后一层靠左后，再做父子编号运算，能减少把图形判断与下标计算混在一起的错误。如需安排数据结构学习，可在咨询软考学习安排时说明目标资格、已有编程基础和具体疑问。知英教育可帮助梳理阅读与练习顺序；当期考试范围仍须核对官方资料。