Добавление элемента в первый незанятый лист в двоичном дереве

Question

Прямо сейчас я пытаюсь написать двоичную кучу в Java, реализованную по двоичной древовидной структуре, и хотя у меня есть очень хорошее представление о том, как " heapify "дерево после добавления элемента, логика поиска первого незанятого листа в нижней части кучи ускользает от меня.

Я знаю, что поиск первого незанятого листа, как предполагается, является обходным путем, но я все еще не могу понять, как будет работать алгоритм обхода ширины в первом порядке.

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