C++递归函数使用static变量致BST插入失效问题排查

你遇到的Bug完全来自C++static局部变量的固有特性，和递归逻辑无关：

• 函数内部声明的static局部变量，仅会在程序首次运行到该变量的初始化语句时执行一次初始化，后续所有对该函数的调用（包含递归层级的内部调用、外部主动发起的新调用），都会直接跳过初始化步骤，复用该变量第一次初始化后的值、对应的内存空间。
• 你代码中写的static struct node *n = newnode(key);，只会在第一次调用insertionbst(root,30)时执行：此时会创建key为30的节点，让n指向这个节点。之后你第二次调用insertionbst(root,35)时，这行初始化代码根本不会运行，n仍然指向最开始存储30的那个节点，自然不会生成key为35的新节点，反而会把已经存在的30节点重复挂载到树的其他位置，和你观察到的现象完全一致。

你原本想靠static避免递归栈上生成变量副本的思路完全没必要：n只是一个指针，占8字节（64位环境），递归每一层的副本开销可以忽略不计，完全不需要为了这点开销用static引入跨调用的状态污染。

除了static变量的误用，你的代码还有两个会导致插入逻辑失效的问题：

• 空指针判断顺序错误：第一行判断if(root->data!=key)会在root为NULL时（比如空树第一次插入的场景）直接访问空指针的成员，触发内存访问错误。必须先判断root是否为空，再访问root的成员字段。
• 根指针为值传递：函数参数里的root是外部传入指针的临时副本，你在函数内写root = n;只会修改这个临时副本，不会改动外部的真实根指针，空树场景下根节点永远无法正确插入。如果要支持空树插入，需要把参数改为二级指针或者指针引用。

去掉static修饰，在找到空的插入位置时再创建新节点，就可以解决你遇到的重复插入问题，核心逻辑参考：

void insertionbst(struct node* root, int key){  
    // 先判空，避免空指针访问
    if(root == NULL){
        // 注意：此处如果要修改外部根指针，需要将入参改为struct node*& root（指针引用）或者struct node** root
        return;
    }
    if(root->data == key){
        cout<<"element already exists"<<endl;
        return;
    }
    if(key < root->data){
        if(root->left == NULL){
            // 找到插入位置时再创建对应key的新节点，不需要static
            root->left = newnode(key);
            return;
        }
        insertionbst(root->left, key);
    } else {
        if(root->right == NULL){
            root->right = newnode(key);
            return;
        }
        insertionbst(root->right, key);
    }
}

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