数据结构之二叉树是否为完全二叉树

笔者在数据结构实验时进行该实现，二叉树是否为完全二叉树判定方法，主要便是观察两者的差别，完全二叉树本质：具有插入限制性，即在二叉树的实现基础上，需要满足除了最后一层之外，每层均满，既二叉树的倒数第三层及之上，每层均有左右结点，倒数第二层，对于一个节点的延申，只有有左节点的时候才能有右节点，对于不同节点，后一个结点可以拥有左节点的条件是前面所有结点的毒均为二。故将此条件简化代码化，来进行完全二叉树的判断   

public boolean isCompleteTree() {

       LinkedQueue<BinaryNode<T>> a = new LinkedQueue<BinaryNode<T>>(); //选择按层次遍历依次判断是否满足完全二叉树的条件

       BinaryNode<T> b = this.root; 

       int haveright=0;  //表示是否拥有右结点，1表示拥有右结点

       while(b!=null) {

           if (b.left == null & b.right != null) {  //用于判断该结点是否满足只有有左孩子的时候才可以拥有右结点的条件，不满足肯定不为完全二叉树

              return false;

           }

           if(haveright==0&b.left!=null&b!=root) {  //除了根节点以外，haveright表示上一个队列的结点是否有右结点，上一个结点没有右结点这个结点有左结点不满足条件

              return false;

           }

           haveright = 0;  //默认该结点无右孩子

           if (b.left != null) {  

              a.add(b.left);

           }

           if (b.right != null) {

              a.add(b.right);

              haveright = 1;  //有右孩子改之为1

           }

           b = a.poll(); //取出队列的首元素

       }

       return true;  //如果遍历之后均和要求，则其为完全二叉树

    }

灵感来自二叉树的层次遍历

原文链接:https://www.cnblogs.com/dxy1493449304/p/11842920.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有