判断一颗二叉树是不是完全二叉树
时间: 2024-08-12 07:06:00 浏览: 29
判断一颗二叉树是否为完全二叉树,可以按照以下步骤进行:
1. 完全二叉树的特点是除了最后一层外,每一层都是满的,并且所有节点都尽可能地向左靠拢。
2. 对于二叉树的每个节点,从根节点开始递归检查:
- 如果当前层为空,则直接继续下一层。
- 否则,如果该层最后一个节点的位置不是满的,或者存在一个比它小的节点在其右侧,那么这棵树就不是完全二叉树。
- 如果当前节点是满的并且其右孩子不存在,或者右孩子也满足完全二叉树的条件,那么继续检查下一个节点,直到遍历完当前层。
- 当前层遍历完成后,检查是否存在未访问过的非空节点。如果有,说明树不完整,否则树是完全二叉树。
3. 如果整个树都能通过上述规则检验,那么就是完全二叉树;反之则不是。
相关问题
Java代码实现判断一颗二叉树是否为完全二叉树
可以使用层次遍历的方式进行判断。具体步骤如下:
1. 对于一颗完全二叉树,如果节点i有左子树,那么节点i+1一定有左子树,如果节点i没有左子树了,那么节点i+1及以后的节点都没有左子树。
2. 对于一颗完全二叉树,如果节点i没有右子树,那么节点i+1及以后的节点都没有右子树。
3. 如果在遍历过程中出现了一个节点没有左子树或者右子树,但是后续节点却有子树,那么这棵树就不是完全二叉树。
下面是Java代码实现:
```java
import java.util.LinkedList;
import java.util.Queue;
public class CompleteBinaryTree {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public static boolean isCompleteBinaryTree(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leafNode = false;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 如果出现了一个节点没有左子树或者右子树,但是后续节点却有子树,那么这棵树就不是完全二叉树
if (node.left == null && node.right != null) {
return false;
}
// 如果此时已经出现过叶子节点,但是后续节点却有子树,那么这棵树就不是完全二叉树
if (leafNode && (node.left != null || node.right != null)) {
return false;
}
if (node.left != null) {
queue.offer(node.left);
} else {
// 如果此时已经出现了叶子节点,但是后续节点却没有子树,那么这棵树就不是完全二叉树
leafNode = true;
}
if (node.right != null) {
queue.offer(node.right);
} else {
// 如果此时已经出现了叶子节点,但是后续节点却没有子树,那么这棵树就不是完全二叉树
leafNode = true;
}
}
return true;
}
public static void main(String[] args) {
// 测试用例
// 完全二叉树
// 1
// / \
// 2 3
// / \ / \
// 4 5 6
TreeNode root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(4);
root1.left.right = new TreeNode(5);
root1.right.left = new TreeNode(6);
System.out.println(isCompleteBinaryTree(root1)); // true
// 非完全二叉树
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
TreeNode root2 = new TreeNode(1);
root2.left = new TreeNode(2);
root2.right = new TreeNode(3);
root2.left.left = new TreeNode(4);
root2.left.right = new TreeNode(5);
root2.right.left = new TreeNode(6);
root2.right.right = new TreeNode(7);
System.out.println(isCompleteBinaryTree(root2)); // false
}
}
```
编写函数,判断一颗二叉树是否是完全二叉树
可以使用递归的方式判断一棵二叉树是否是完全二叉树。对于一个节点,如果它的左子树为空但右子树不为空,或者它的左右子树个数不相等,那么它就不是完全二叉树。如果该节点是叶子节点,那么之后遍历的所有节点都必须是叶子节点,否则它就不是完全二叉树。遍历过程可以使用层次遍历或先序遍历等方式实现。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)