【数据结构——二叉树】判断二叉树是否为完全二叉树

系统管理员 2021-12-03 22:57 345阅读 0赞

创建于：2019.5.25

*    方一

思路：

得到一棵二叉树的 带有空子树标识的层序遍历序列；

从前往后逐个遍历元素，直到找到 空标识；

看 空标识 后的元素是否全是 空标识，全是空标识 则是完全二叉树，不全是空标识则是完全二叉树

问题（待解决）：

无法实现 得到带有空子树标识的层序遍历序列 的算法，没想到如何将空标识加入到list的适当位置

*  （网上查的）方二：

思路：

非递归层序遍历的应用：判断二叉树是否是完全二叉树

入队列的时候不用判断节点是否为空，直接入队列；出队列的时候如果front==NULL,停止入队列，判断队列里的元素是否全为NULL,若是则是完全二叉树。

问题：

queue.add(null)不合法

\* null值不会真的入队

代码：

1 public boolean isCompleteBinaryTree() {
     2         if(this.root==null) {          //空树是完全二叉树
     3             return true;
     4         }
     5         
     6         LinkedQueue<BinaryNode<T>> queue = new LinkedQueue<>();// 空队列
     7         BinaryNode<T> p = this.root; // 根结点不入队
     8         int count = 1;// 已经出队的元素个数
     9         ArrayList preList=this.getPrelist(this.root);//带空标识的前序序列
    10 
    11         while (p != null) { // 当出队元素为null时，停止继续入队
    12             queue.add(p.left);// p的左孩子入队
    13             queue.add(p.right);// p的右孩子入队
    14 
    15             p = queue.poll();
    16             count++;
    17             System.out.println(p);
    18         }
    19         System.out.println(count);
    20         while (count<preList.size()) {
    21             p = queue.poll();
    22             count++;
    23             if (p != null)
    24                 return false;
    25         }
    26         return true;
    27         
    28     }

修改：（已测试）

1 /**
     2      * @title: isCompleteBinaryTree
     3      * @description: judge a tree is complete tree or not; use que
     4      * @author: Navis
     5      * @date: May 25, 2019 11:00:31 PM
     6      * @return boolean
     7      */
     8     public boolean isCompleteBinaryTree() {
     9         if (this.root == null) { // 空树是完全二叉树
    10             return true;
    11         }
    12 
    13         LinkedQueue<BinaryNode<T>> queue = new LinkedQueue<>();// 空队列
    14         queue.add(root); // 根结点入队
    15         BinaryNode<T> p = null;
    16 
    17         while (!queue.isEmpty()) { // 队列不空时
    18             p = queue.poll();
    19             if (p.left != null) {
    20                 queue.add(p.left);// p的左孩子入队
    21                 if (p.right != null) {
    22                     queue.add(p.right);// p的右孩子入队
    23                 } else
    24                     break;
    25             } else {
    26                 if (p.right != null)
    27                     return false;
    28                 else
    29                     break;
    30             }
    31         }
    32         while (!queue.isEmpty()) {
    33             p = queue.poll();
    34             if (p.left != null || p.right != null)
    35                 return false;
    36         }
    37         return true;
    38     }

转载于:https://www.cnblogs.com/musecho/p/11201130.html