C++实现泛型树时const node*&引用绑定编译报错排查

问题现象 #

实现泛型树时，getSizeRecursive函数第1行使用const node* &root作为形参触发编译错误，第2行遍历root->children时出现同类错误，报错信息如下：

graph.cpp: In function 'int getSizeRecursive(const node*&)':
graph.cpp:56:40: error: binding reference of type 'const node*&' to 'node* const' discards qualifiers
   56 |         for(const node* &child : root->children) // line 2
      |                                        ^~~~~~~~
graph.cpp: In function 'int main()':
graph.cpp:69:36: error: binding reference of type 'const node*&' to 'node*' discards qualifiers
   69 |         cout << getSizeRecursive(t.root) << endl;
      |                                  ~~^~~~
graph.cpp:51:35: note:   initializing argument 1 of 'int getSizeRecursive(const node*&)'
   51 | int getSizeRecursive(const node* &root){ // line 1
      |                      ~~~~~~~~~~~~~^~~~
[Finished in 2.9s]

复现代码如下：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class node{
public:
    int data;
    vector<node*> children;

    node(int val){
        data = val; // this->data = data
    }
    ~node(){
        for(int i = 0 ;i<children.size();i++){
            if(!children[i])
                delete children[i];
        }
    }
};
class GenericTree{
public:
    node* root; // line 3
    int size;
    
    GenericTree(vector<int> nums){
        stack<node*> st;
        size = 0;
        for(int i = 0;i<nums.size();i++){
            node *n = new node(nums[i]);
            if(i == 0){
                root = n;
                st.push(n);
                ++size;
            }else{
                if(n->data == -1){
                    st.pop();
                }else{
                    st.top()->children.push_back(n);
                    st.push(n);
                    ++size;
                }
            }
        }
    }
    int getSize(){
        return size;
    }
};
int getSizeRecursive(const node* &root){ // line 1
    if(root->children.size()==0)
        return 1;

    int size = 0;
    for(const node* &child : root->children) // line 2
        size  += getSizeRecursive(child);
    return size+1;
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("error.txt","w",stderr);
    #endif
    vector<int> v{10,20,-1,30,50,-1,60,-1,-1,40,-1,-1};
    GenericTree t(v);
    cout << t.size << endl;
    cout << getSizeRecursive(t.root) << endl;
    return 0;
}

核心疑问：

• 已知报错原因是无法将「指向const node的指针的引用」绑定到类型不匹配的指针对象，但t.root明确定义为node*类型，为何编译器会识别出const属性？
• 写const node* & root的初衷是避免传递root指针的拷贝，同时通过const限定保证引用仅可读、不会修改root指针本身。

错误根因 #

首先要明确C++中const修饰指针的规则，const的位置直接决定它限定的对象：

• const node* p：const修饰node，意思是指针p指向的node内容不可修改，但p本身存储的地址值可以改，也就是p可以重新指向其他node
• node* const p：const修饰指针p本身，意思是p存储的地址值不可修改（p不能重指向其他node），但p指向的node内容可以改
• const node* const p：指针p本身不能改指向，指向的node内容也不能通过p修改

你写的const node* &root是「绑定到const node*类型的引用」，也就是引用的是一个指向const node的可修改指针。这个类型和你实际要绑定的对象完全不匹配：

1. 传入的t.root类型是node*，是指向非const node的可修改指针。C++不允许将node*隐式转换为const node*后绑定到非const引用，否则会出现类型安全漏洞：如果允许这种绑定，就可以通过该引用把一个真正指向const node的指针赋值给t.root，后续通过t.root这个node*类型指针修改const node内容，会触发未定义行为，因此语法直接禁止。
2. 遍历root->children时报错提到的node* const，是因为形参root是const node*类型（指向const node），通过它访问成员children时，vector的元素访问会带上const属性，返回的是node* const类型（指针本身不可修改，指向的node是非const），自然也无法绑定到const node*&类型的引用上。

修复方案 #

你的需求是避免指针拷贝，同时保证函数内不会修改指针本身、也不会修改指向的node内容，只需要把const放到正确的位置，修饰指针本身即可：

// const写在*后面，修饰指针本身：引用绑定到「指向const node的const指针」
int getSizeRecursive(const node* const &root){
    if(root->children.size()==0)
        return 1;

    int size = 0;
    // 循环内的引用变量同理，给指针本身加const限定
    for(const node* const &child : root->children)
        size  += getSizeRecursive(child);
    return size+1;
}

额外说明：指针本身是非常小的标量类型（64位环境下仅占8字节），按值传递的开销和传引用完全没有区别，如果你不需要在函数内修改指针的指向，直接写int getSizeRecursive(const node* root)按值传递指向const node的指针，代码更简洁，也不会出现类型匹配问题，性能完全一致。

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