java - 将元素添加到二叉树中的第一个未占用的叶子

Question

现在我正在尝试用 Java 编写一个通过二叉树结构实现的二叉堆，虽然我对如何在添加元素后“堆化”树有很好的了解，但找到第一个未占用叶子的逻辑在堆的底部躲避我。

我知道找到第一个未占用的叶子应该是广度优先遍历，但我仍然无法弄清楚广度优先遍历算法究竟是如何工作的。

Answer 1

这就是对第一个空分支（随后插入分支）进行广度优先搜索的样子。请注意，这与深度优先插入基本相同，只是它使用队列，而深度优先插入使用堆栈。

void breadthFirstInsert(Node root, Object obj) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
        Node temp = queue.poll();
        if(temp.left != null) {
            queue.offer(temp.left);
        } else {
            temp.left = new Node(obj);
            return;
        }
        if(temp.right != null) {
            queue.offer(temp.right);
        } else {
            temp.right = new Node(obj);
            return;
        }
    }
}