向二叉树中第一个未占用的叶添加元素

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;
        }
    }
}