Java实现一个完全二叉树
时间: 2023-06-02 17:06:42 浏览: 62
的遍历算法,你可以回答这个问题。
答: 一个完全二叉树的遍历可以使用广度优先搜索(BFS)算法。遍历时逐层遍历,从根节点开始,先遍历左子节点,再遍历右子节点,将其加入到队列中,然后遍历队列中的节点,直到队列为空。具体实现可以使用队列来辅助遍历过程,同时记录遍历过程的值。
相关问题
帮我基于Java写一个完全二叉树,底层用数组实现
好的,我可以帮您实现一个基于Java的完全二叉树,底层使用数组实现。以下是示例代码:
```java
public class CompleteBinaryTree {
private int[] tree; // 存放完全二叉树的数组
private int size; // 完全二叉树的大小
/**
* 构造函数,传入完全二叉树的大小
*/
public CompleteBinaryTree(int size) {
tree = new int[size+1]; // 数组下标从1开始,所以长度要+1
this.size = size;
}
/**
* 将指定元素插入到完全二叉树底层的数组中
*/
public void insert(int element) {
if (isFull()) {
throw new RuntimeException("Binary tree is full!");
}
tree[++size] = element;
}
/**
* 判断完全二叉树是否已满
*/
public boolean isFull() {
return size >= tree.length - 1;
}
/**
* 获取完全二叉树的大小
*/
public int getSize() {
return size;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= size; i++) {
sb.append(tree[i]).append(" ");
}
return sb.toString();
}
}
```
上述代码中,我们定义了一个 `CompleteBinaryTree` 类,其中包含了一些方法,如 `insert`、`isFull`、`getSize` 和 `toString`。
其中, `insert` 方法用于在完全二叉树底层的数组中插入指定元素; `isFull` 方法用于判断完全二叉树是否已满; `getSize` 方法用于获取完全二叉树的大小; `toString` 方法用于将完全二叉树底层的数组转化为字符串形式。
希望这可以帮助您。如果您有其他问题或需要进一步的帮助,请随时告诉我。
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
}
}
```