C++二叉搜索树（BST）添加节点后find函数深度计算异常及节点有效性排查

让我们一步步拆解你的问题：

1. 为什么find(45)返回深度0？ #

你的find辅助函数里的lastNode是局部变量，每次递归调用find时，都会重新初始化这个变量为0。举个具体的执行流程：

• 第一次调用find时，根节点是1，45比1大，你把lastNode加1变成1，然后递归调用find(c, n->rightChild)
• 进入新的递归层后，lastNode又被重新设为0，之前的递增操作完全不会传递到这里
• 以此类推，直到找到45的那一层递归，lastNode还是初始值0，所以输出结果自然是0

这是递归中使用局部变量的典型陷阱——每个递归调用都拥有独立的变量副本，修改操作无法跨层生效。

2. 树是否正确添加了？ #

放心，教授提供的add函数是完全没问题的！你添加1到100时，每个新数字都比当前节点值大，所以会一直被追加到右子树上，最终形成一条右斜的链状树。isEmpty返回false也验证了树确实被填充完成，这部分不需要怀疑。

修复方案：传递深度参数 #

要正确追踪节点深度，我们需要把深度作为参数在递归调用中传递，而不是依赖局部变量。具体修改如下：

第一步：修改find辅助函数的签名与实现 #

// 新增depth参数，用于传递当前节点的深度
bool find(const Comparable& c, BinaryNode* n, int depth) const { 
    if (n == nullptr) { 
        // 找不到目标时，最后访问的节点深度为当前depth-1
        std::cout << "Depth of last node visited: " << depth - 1; 
        return false; 
    } 
    if (c < n->value) { 
        // 往左子树递归，深度+1
        return find(c, n->leftChild, depth + 1); 
    } 
    if (n->value < c) { 
        // 往右子树递归，深度+1
        return find(c, n->rightChild, depth + 1); 
    } 
    // 找到目标节点，输出当前深度
    std::cout << "Depth of target value: " << depth; 
    return true; 
}

第二步：修改对外的find调用入口 #

假设你的类中有一个对外暴露的find函数，需要让它调用辅助函数并传入初始深度0（根节点的深度为0）：

bool find(const Comparable& c) const {
    // 从根节点开始，初始深度为0
    return find(c, root, 0);
}

验证结果 #

修改完成后，调用find(45)应该会输出Depth of target value: 44——因为根节点1的深度是0，45是第45个节点，深度正好是44，完全符合预期。

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