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

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