java - 二分木の最初の占有されていない葉への要素の追加

Question

現在、バイナリ ツリー構造上に実装された Java でバイナリ ヒープを作成しようとしています。要素を追加した後にツリーを「ヒープ化」する方法をよく理解していますが、占有されていない最初のリーフを見つけるためのロジックはヒープの一番下で私を逃れます。

占有されていない最初のリーフを見つけることは、幅優先のトラバーサルであると想定されていることは承知していますが、幅優先のトラバーサル アルゴリズムがどのように機能するかはまだわかりません。

Answer 1

これは、最初の null ブランチ (ブランチへの挿入が続く) の幅優先検索がどのように見えるかです。これは、深さ優先の挿入がスタックを使用するキューを使用することを除いて、基本的に深さ優先の挿入と同じであることに注意してください。

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