当前位置：首页 > news >正文

网站怎么做跳转/百度2023免费下载

news 2025/8/4 19:35:42

网站怎么做跳转,百度2023免费下载,女生学java好吗,网站按钮样式创建于：2019.5.25 方一思路： 得到一棵二叉树的带有空子树标识的层序遍历序列； 从前往后逐个遍历元素，直到找到空标识； 看空标识后的元素是否全是空标识，全是空标识则是完全二叉树，不全是空…

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