二叉树插入函数存入超10条数据失效，求排查解决

首先看你贴的addItemToTree代码，核心问题出在插入逻辑的局限性上：

你的代码目前只检查当前节点的左、右孩子是否为空，当当前节点的左右都被占满后，虽然尝试递归左子树，但代码没写完（node->left->lef...），就算写完，如果只递归左子树而没有遍历整个树的所有节点，当树的前几层（根+2子节点+4孙节点）被占满后，后续的插入就找不到可用的空位了——这就是为什么数据量超过一定数量（实际是7个节点后）就失效的原因。

修复方案：用广度优先搜索（BFS）实现层序插入 #

最稳妥的方式是用队列做层序遍历，找到树中第一个有空位（左/右孩子为空）的节点，插入新元素。这种方式符合完全二叉树的插入逻辑，能支持任意数量的节点插入。

先看修复后的完整代码：

#include <queue> // 记得引入队列头文件

// 你的节点结构保持不变
struct node { 
    int info; 
    node *left = NULL; 
    node *right = NULL; 
    node() {} 
    node(int data, node* ln = 0, node* rn = 0): info(data), left(ln), right(rn) {} 
};

bool addItemToTree(struct node* root, int item) {
    if (!root) {
        // 如果根节点为空，你可以选择返回false，或者改成传入node** root来创建根节点
        return false;
    }

    // 处理根节点未初始化的情况（比如用默认构造函数创建的根）
    if (root->left == nullptr && root->right == nullptr && root->info == 0) {
        root->info = item;
        return true;
    }

    std::queue<node*> nodeQueue;
    nodeQueue.push(root);

    while (!nodeQueue.empty()) {
        node* currentNode = nodeQueue.front();
        nodeQueue.pop();

        // 先尝试插入左孩子
        if (!currentNode->left) {
            currentNode->left = new node(item);
            return true;
        } else {
            nodeQueue.push(currentNode->left);
        }

        // 左孩子满了，尝试插入右孩子
        if (!currentNode->right) {
            currentNode->right = new node(item);
            return true;
        } else {
            nodeQueue.push(currentNode->right);
        }
    }

    // 理论上不会走到这里，因为二叉树可以无限扩展
    return false;
}

为什么这个方案能解决问题？ #

• 队列帮我们按层遍历所有节点，从根节点开始，依次检查每个节点的左、右孩子，确保我们找到第一个可用的空位，不会漏掉树中任何可能的插入位置。
• 不管你的树有多少层、多少节点，只要内存足够，就能持续插入新元素。

可选：递归实现（深度优先插入） #

如果你更倾向于递归写法，也可以这样实现（注意：这种方式是深度优先插入，和层序插入的节点顺序不同）：

bool addItemToTree(struct node* node, int item) {
    if (!node) return false;

    // 先插左孩子
    if (!node->left) {
        node->left = new node(item);
        return true;
    }
    // 左孩子满了插右孩子
    if (!node->right) {
        node->right = new node(item);
        return true;
    }
    // 当前节点满了，先递归左子树，左子树不行再递归右子树
    if (addItemToTree(node->left, item)) {
        return true;
    }
    return addItemToTree(node->right, item);
}

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