算法思路
将根节点存入队列
取出队列首元素，输出节点储存数据
检查该节点是否有子节点，有则加入队列
只要队列不为空则重复第二，三步
算法实现
二叉树的实现
节点类
左右子节点的引用Node left Node right
保存的数据T data
重写toString()方便查看输出结果
class Node {
T data;
Node left = null;
Node right = null;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return "" + data;
}
}
二叉树类
根节点Node root
判断是否为空的方法isEmpty()
public class CompleteBinaryTree {
Node root;
public boolean isEmpty() {
return root == null;
}
}
具体步骤
声明一个队列保存待遍历的节点Queue> queue = new LinkedList<>();
先把根节点加入队列
只要队列非空则循环操作
弹出队首queue.remove();并输出数据
左右子节点非空则加入队列
public void breadthFirstTravel() {
if (isEmpty()) {
System.out.println("树为空");
return;
}
Queue> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node cur = queue.remove();
System.out.println(cur.data);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
测试
完整代码
class Node {
T data;
Node left = null;
Node right = null;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return "" + data;
}
}
public class CompleteBinaryTree {
Node root;
public boolean isEmpty() {
return root == null;
}
public void breadthFirstTravel() {
if (isEmpty()) {
System.out.println("树为空");
return;
}
Queue> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node cur = queue.remove();
System.out.println(cur.data);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
}