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

时间:2021-03-29 17:30:12

创建于: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     }