将元素添加到二叉树中的第一个非占用叶-Java 学习之路

现在我正在尝试用二叉树结构在Java中编写二进制堆，虽然我对如何在添加元素后“堆积”树有很好的把握，但是找到第一个未占用的叶子的逻辑在堆的底部逃避了我 .

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

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

回复于 2024-04-23T18:14:16+08:00

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

1 回答

相关问题