实现：往完全二叉树中添加一个节点，使得添加之后这棵树依旧是一棵完全二叉树

class Node:
    def __init__(self, val):
        self.val = val  # 数据域
        self.left = None  # 左指针域
        self.right = None  # 右指针域


class Tree:
    def __init__(self):
        self.root = None  # 树的根节点

    def add(self, val):
        # 层次遍历, 广度优先遍历
        # val 要添加的节点的值
        # 往树中添加一个节点,并保证添加之后这棵树依旧是一棵完全二叉树
        node = Node(val)
        # 判断树是否为空,如果为空,直接将node设置为根节点
        if not self.root:
            self.root = node
            return
        # 从上往下,从左往右的去遍历整棵树,然后找到第一个空位
        # 把节点添加进去
        queue = [self.root]  # 存每一层的节点
        while True:
            # 第一次 queue = [root]
            # 第二次 queue = [root.left, root.right]
            # queue = [root.right, root.left.left, root.left.right]
            # queue = [root.left.left, root.left.right, root.right.left, root.right.right]
            cur_node = queue.pop(0)
            # 先找左边,看有没有空位
            if not cur_node.left:
                cur_node.left = node
                return
            # 左边没有空位,就找右边
            elif not cur_node.right:
                cur_node.right = node
                return
            # 如果都没有空位,那就把左边节点与右边节点都加到之后要判断的节点中
            queue.extend((cur_node.left, cur_node.right))

    def show(self):
        # 展示树
        if not self.root:
            return
        # 从上往下,从左往右的去遍历整棵树,然后找到第一个空位
        # 把节点添加进去
        queue = [self.root]  # 存每一层的节点
        i = 1
        while queue:
            size = len(queue)  # 当前层的元素个数
            print(f'第{i}层', end='\t')
            for _ in range(size):
                node = queue.pop(0)  # 队列中的第一个元素抛出来
                print(node.val, end=' ')  # 对当前元素进行操作
                # 节点的左孩子与右孩子添加到队列里
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            print()
            i += 1
if __name__ == '__main__':
    tree = Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.show()

执行结果：