写一个代码,实现Java中借助队列,使用层次法创建一个二叉树,
时间: 2024-12-11 18:20:21 浏览: 5
在Java中,我们可以使用数组列表作为队列,并利用迭代的方式实现层序遍历(即广度优先搜索,BFS),来构建二叉树。下面是一个简单的例子,假设我们有一个节点类`Node`,并且输入的是整数序列:
```java
import java.util.ArrayList;
import java.util.List;
class Node {
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
public class BinaryTreeBuilder {
private List<Node> queue = new ArrayList<>();
private int[] input = {1, 2, 3, 4, 5, 6, 7}; // 输入的二叉树节点值
public Node buildTree() {
if (input.isEmpty()) return null;
Node root = new Node(input[0]);
queue.add(root);
while (!queue.isEmpty()) {
Node current = queue.remove(0); // 取出队首元素
if (current.left != null) {
queue.add(current.left);
current.left = new Node(input.pop()); // 根据队列顺序填充左子树
}
if (current.right != null) {
queue.add(current.right);
current.right = new Node(input.pop()); // 根据队列顺序填充右子树
}
}
return root;
}
public static void main(String[] args) {
BinaryTreeBuilder builder = new BinaryTreeBuilder();
Node treeRoot = builder.buildTree();
// 打印二叉树结构
printInOrder(treeRoot);
}
// 中序打印函数,仅用于测试,实际应用中可以忽略
private static void printInOrder(Node node) {
if (node == null) return;
printInOrder(node.left);
System.out.print(node.val + " ");
printInOrder(node.right);
}
}
```
在这个示例中,我们首先创建根节点并添加到队列中。然后在循环中,每次从队列中取出第一个节点,为其左右子节点创建新的节点并添加到队列中,直到队列为空。这样就按照层次构造了二叉树。
阅读全文