如何不使用队列数据结构递归插入节点至完全二叉树？

你的代码之所以总是把新节点插入到左侧，是因为递归逻辑采用了深度优先遍历的顺序：只要左子树能找到插入位置，就优先往左侧子树插入，完全忽略了完全二叉树需要按层填充、先填满当前层所有节点再进入下一层的规则。完全二叉树的插入要求新节点必须放在最底层最左侧的空位，而非一直往左侧分支深插。

解决方案：利用节点编号特性实现递归插入 #

完全二叉树有个关键特性：节点按层序从1开始编号时，第k个节点的左孩子为2k，右孩子为2k+1。我们可以通过新节点的编号推导插入路径：

1. 计算新节点的编号为当前节点数+1
2. 将编号转为二进制，去掉最高位的1，剩余每一位对应路径：0走左子树，1走右子树
3. 递归按路径找到目标父节点，完成插入

修改后的代码 #

class TreeNode:
    def __init__(self, value=None) -> None:
        self.left = None
        self.value = value
        self.right = None

class Tree:
    def __init__(self, root=None) -> None:
        self.__root = TreeNode(root) if root is not None else None
        self.__len = 1 if root is not None else 0

    def append(self, data):
        # 处理空树
        if self.__root is None:
            self.__root = TreeNode(data)
            self.__len = 1
            return
        
        new_node_num = self.__len + 1
        # 转换为二进制并提取路径：去掉前缀'0b'和最高位的1
        path = bin(new_node_num)[2:][1:]
        self._insert_recursive(self.__root, path, data)
        self.__len = new_node_num

    def _insert_recursive(self, current_node, path, data):
        if not path:
            return
        
        # 拆分当前方向与剩余路径
        direction = path[0]
        remaining_path = path[1:]

        if not remaining_path:
            # 到达目标父节点，执行插入
            if direction == '0':
                current_node.left = TreeNode(data)
            else:
                current_node.right = TreeNode(data)
            return
        
        # 递归进入下一层节点
        if direction == '0':
            self._insert_recursive(current_node.left, remaining_path, data)
        else:
            self._insert_recursive(current_node.right, remaining_path, data)

代码说明 #

• append方法先处理空树场景，再通过新节点编号生成插入路径
• 辅助函数_insert_recursive根据路径递归遍历到目标父节点，最后根据路径末尾的方向插入左/右孩子
• 该逻辑严格遵循完全二叉树的插入规则，无需依赖队列数据结构

内容的提问来源于stack exchange，提问作者H_coder