二叉树广度优先遍历(Java实现)

算法思路

1. 将根节点存入队列
2. 取出队列首元素，输出节点储存数据
3. 检查该节点是否有子节点，有则加入队列
4. 只要队列不为空则重复第二，三步

算法实现

二叉树的实现

1. 节点类
   • 左右子节点的引用Node<T> left Node<T> right
   • 保存的数据T data
   • 重写toString()方便查看输出结果

class Node<T> {
    T data;
    Node<T> left = null;
    Node<T> right = null;

    public Node(T data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "" + data;
    }
}

2. 二叉树类
   • 根节点Node<T> root
   • 判断是否为空的方法isEmpty()

public class CompleteBinaryTree<T> {
    Node<T> root;
     public boolean isEmpty() {
        return root == null;
    }
}

具体步骤

1. 声明一个队列保存待遍历的节点Queue<Node<T>> queue = new LinkedList<>();
2. 先把根节点加入队列
3. 只要队列非空则循环操作
   • 弹出队首queue.remove();并输出数据
   • 左右子节点非空则加入队列

    public void breadthFirstTravel() {
        if (isEmpty()) {
            System.out.println("树为空");
            return;
        }
        Queue<Node<T>> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node<T> cur = queue.remove();
            System.out.println(cur.data);
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

测试

测试放到https://www.jianshu.com/p/895b25409f89

完整代码

class Node<T> {
    T data;
    Node<T> left = null;
    Node<T> right = null;

    public Node(T data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "" + data;
    }
}
public class CompleteBinaryTree<T> {
    Node<T> root;
    public boolean isEmpty() {
        return root == null;
    }
    public void breadthFirstTravel() {
        if (isEmpty()) {
            System.out.println("树为空");
            return;
        }
        Queue<Node<T>> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node<T> cur = queue.remove();
            System.out.println(cur.data);
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }
}