vector<pointer>::insert插入垃圾值：BST同构排列递归函数异常

我正在编写一个递归函数，用于打印所有可构造出相同二叉搜索树（BST）的键的排列。思路是在每个节点处，将下一个可选节点存储在vector中（删除当前节点并添加其子节点），然后递归调用函数；当没有更多节点可添加时打印键值（我知道可以用vector替代stack，但我正在学习vector）。

当前遇到的问题是：代码能打印所有以18 12开头的排列，但在第二层递归的循环末尾（main::printPermute仅1次循环::printPermute的第1次循环末尾），执行LIST.insert(i,t)时，并未插入存储键12的节点地址，而是插入了垃圾值0x31，导致后续执行异常。奇怪的是，更高层级的递归并未出现该问题。

完整代码 #

#include<bits/stdc++.h>
#define child c
using namespace std;
typedef struct bstnode {
    bstnode *lc;
    int x;
    int data;
    bstnode *rc;
}* BSTPTR;
//Prints the inorder of a BST
void printIn(BSTPTR T) {
    if(T) {
        printIn(T->lc);
        cout<<T->data<<' ';
        printIn(T->rc);
    }
}
//adds an element to a BST
void add(BSTPTR &T,int k) {
    if(T) {
        if(k < T->data) add(T->lc,k);
        else add(T->rc,k);
    } else {
        BSTPTR t = new bstnode;
        t->data = k;
        t->lc=t->rc=NULL;
        T = t;
    }
}
//prints all the permutations in question
void printPermute(vector<BSTPTR> &LIST,BSTPTR T,stack<int> p) {
    if(LIST.size()==0) {
        stack<int> q;
        int n=p.size();
        while(!p.empty()) {
            q.push(p.top());
            p.pop();
        }
        int flag=1;
        int i=0,A[]={18,12,15,5,9,36,72,45,30};
        while(!q.empty()) {
            int x=q.top();
            if(A[i++]!=x) flag=0;
            cout<<x<<' ';
            q.pop();
            p.push(x);
        }
        if(flag) {
            int f=9;
            f++;
        }
        cout<<endl;
    } else {
        for(auto i=LIST.begin();i<LIST.end();++i) {
            BSTPTR t=*i;
            p.push(t->data);
            LIST.erase(i);
            if(t->lc) {
                LIST.push_back(t->lc);
                if(t->rc) {
                    LIST.push_back(t->rc);
                    printPermute(LIST,t,p);
                    LIST.pop_back();
                } else {
                    printPermute(LIST,t,p);
                }
                LIST.pop_back();
            } else {
                if(t->rc) {
                    LIST.push_back(t->rc);
                    printPermute(LIST,t,p);
                    LIST.pop_back();
                } else {
                    printPermute(LIST,t,p);
                }
            }
            p.pop();
            LIST.insert(i,t);
        }
    }
}
//this is a helping function to asitis(BSTPTR) assigns the value of x for each node
void assignX(BSTPTR T,int &x) {
    if(T) {
        if(T->lc == NULL) {
            T->x = x++;
            assignX(T->rc, x);
        } else {
            assignX(T->lc, x);
            T->x = x++;
            assignX(T->rc, x);
        }
    }
}
//prints the tree as it would look on paper. This is to give an intuitive idea of the tree's structure
void asItIs(BSTPTR T) {
    int prev;
    assignX(T,prev=1);
    prev=0;
    queue<BSTPTR> q;
    q.push(T);
    q.push(NULL);
    while(q.size()>1) {
        BSTPTR t = q.front();
        q.pop();
        if(t) {
            for(int i=0;i<t->x-1-prev;++i) cout<<' ';
            cout<<t->data;
            prev = t->x;
            if(t->lc) q.push(t->lc);
            if(t->rc) q.push(t->rc);
        } else {
            cout<<endl;
            prev = 0;
            q.push(t);
        }
    }
    cout<<endl;
}
int main() {
    BSTPTR T = NULL;
    cout<<"Enter the numbers in the tree:\n";
    int i=0,A[] = {18,12,36,5,15,30,72,9,45,-5};
    while(A[i]>=0) {
        add(T,A[i++]);
    }
    printIn(T);
    cout<<endl;
    asItIs(T);
    vector<BSTPTR> LIST;
    stack<int> p;
    LIST.push_back(T);
    // cout<<LIST.size();
    printPermute(LIST,T,p);
}

问题原因分析 #

核心问题出在vector迭代器失效上：

当你执行LIST.erase(i)时，vector会删除迭代器i指向的元素，并且将后面的所有元素向前移动一个位置来填补空缺。此时，原来的迭代器i就变成了无效迭代器——它不再指向vector中的任何有效位置，后续使用这个迭代器的操作（比如LIST.insert(i,t)）属于未定义行为，这就是为什么你会看到插入垃圾地址的原因。

更高层级递归没出问题只是巧合：比如当vector中只有一个元素时，erase(i)后i会等于LIST.end()，此时insert(end(), t)刚好是在末尾插入元素，结果看起来是正确的；但当vector中有多个元素时，erase后i失效，后续操作就会出错。

解决方案 #

修复的关键是利用vector::erase的返回值——它会返回一个指向删除元素之后位置的有效迭代器。我们可以保存这个有效迭代器，后续插入时使用它。

修改printPermute函数中的循环部分：

for(auto i=LIST.begin();i<LIST.end();/* 去掉原循环的++i，手动控制迭代器 */) {
    BSTPTR t=*i;
    p.push(t->data);
    // 保存erase返回的有效迭代器
    auto next_i = LIST.erase(i);
    if(t->lc) {
        LIST.push_back(t->lc);
        if(t->rc) {
            LIST.push_back(t->rc);
            printPermute(LIST,t,p);
            LIST.pop_back();
        } else {
            printPermute(LIST,t,p);
        }
        LIST.pop_back();
    } else {
        if(t->rc) {
            LIST.push_back(t->rc);
            printPermute(LIST,t,p);
            LIST.pop_back();
        } else {
            printPermute(LIST,t,p);
        }
    }
    p.pop();
    // 使用保存的有效迭代器插入，更新i为插入后的下一个位置
    i = LIST.insert(next_i, t);
    ++i;
}

这里需要注意：

1. 原for循环的++i要移除，因为我们需要通过erase和insert的返回值手动控制迭代器位置
2. LIST.insert(next_i, t)会返回指向插入元素的迭代器，我们需要将i设置为这个迭代器并自增，确保循环能正确遍历所有元素

这样修改后，迭代器始终保持有效，就不会再出现插入垃圾地址的问题了。

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